Estructura de Datos : Indices Enlazados ( Linked Indexes )

Definiciones

Indices Enlazados ( Linked Indexes ) :
Los Indices Enlazados son índices que usan campos de enlaces para llevar a cabo la busqueda de un valor de una clave.

Indices Densos :
En los Indices Densos todas las claves de búsqueda están en el índice.

Indices No Densos :
En los Indices No Densos todas las claves de búsqueda no están en el índice. Solo estarán algunas de ellas. Las que están depende de la arquitectura del índice.

Indice Enlazado Simple

Este tipo de índice es no denso. O sea, todos los valores de claves presentes en el archivo no son una entrada en el índice. Unos pocos valores de clave están presentes en el índice. Existe un arreglo de rangos de valores de clave, desde donde nace la lista enlazada que nos permite navegar por todos los registros que tengan un valor de clave comprendido en el rango. La busqueda del valor de una clave se ejecuta accediendo al arreglo en forma secuencial hasta ubicar el rango especifico del valor de la clave para continuar navegando la lista que se inicia en el elemento del arreglo seleccionado. Cada entrada del índice, la que representa al rango, tiene el valor máximo que tiene el rango, permitiendo de esta manera la determinación del rango que le corresponde a cada valor de clave en el proceso de búsqueda. En el siguiente ejemplo los valores de clave solo pueden ser mayores a 500 y menores a 1101 y se proporcionan rangos que van de 501 a 700, 701 a 900 y 901 a 1100.


   Rango    Enlace
+---------+--------+
|         |        |    +------------+       +------------+
|   700   |    -------->|   601  | *-|------>|   698  | 0 |
|         |        |    +------------+       +------------+
+---------+--------+
|         |        |    +------------+       +------------+                  +------------+
|   900   |    -------->|   800  | *-|------>|   900  | 0 |                  |  Clave | * |
|         |        |    +------------+       +------------+                  +----------|-+
+---------+--------+                                                                    |
|         |        |    +------------+                                                  +--> Enlace
|  1100   |    -------->|  1007  | 0 |
|         |        |    +------------+
+---------+--------+

Observar que los registros deben contener un campo para enlazar los demas registros que estan presentes en el mismo rango.

Indice Enlazado Multiple

Este tipo de índice es no denso. O sea, todos los valores de claves presentes en el archivo no son una entrada en el índice. Unos pocos valores de clave estan presentes en el índice. Existen varios arreglos de rangos de valores de clave, cada uno para una clave distinta. Lo dicho para la organización anterior ahora se aplica a cada clave en particular. En este caso es útil llevar la cuenta de los registros que estan enlazados en cada rango. En el siguiente ejemplo estamos en presencia de cuatro claves :

Una clave numerica cuyos valores solo pueden ser mayores a 500 y menores a 1101 y se proporcionan rangos que van de 501 a 700, 701 a 900 y 901 a 1100.

Una clave alfabetica con dos rangos, los valores que van hasta " analista " y los valores que van hasta " programador ".

Una clave alfabetica con dos rangos, los valores que van hasta " femenino " y los valores que van hasta " masculino ".

Una clave numerica cuyos valores solo pueden ser mayores a 0 y menores a 15001 y se proporcionan rangos que van de 1 a 9000, 9001 a 12000 y 12001 a 15000.

+---------+---------+---------+                                                  +-------------+-------------+
|   700   |   900   |  1100   | Máximo Valor del Rango                           |  analista   | programador | Máximo Valor del Rango
+---------+---------+---------+                                                  +-------------+-------------+
|    2    |    2    |    1    | Longitud de la Lista                             |      2      |      3      | Longitud de la Lista
+---------+---------+---------+                                                  +-------------+-------------+
|    B    |    D    |    C    | Enlace al primer nodo                            |      B      |      E      | Enlace al primer nodo
+---------+---------+---------+                                                  +-------------+-------------+




           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           |   Datos   |      |   Datos   |      |   Datos   |      |   Datos   |      |   Datos   |
           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           |           |      |           |      |           |      |           |      |           |    Enlaces Clave Codigo_Empleado
           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           |           |      |           |      |           |      |           |      |           |    Enlaces Clave Codigo_Ocupacion
           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           |           |      |           |      |           |      |           |      |           |    Enlaces Clave Codigo_Sexo
           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           |           |      |           |      |           |      |           |      |           |    Enlaces Clave Valor_Salario
           +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
            Registro  B        Registro  E        Registro  D        Registro  A        Registro  C


+-------------+-------------+                                                    +---------+---------+---------+
|  femenino   |  masculino  | Máximo Valor del Rango                             |   9000  |  12000  |  15000  | Máximo Valor del Rango
+-------------+-------------+                                                    +---------+---------+---------+
|      3      |      2      | Longitud de la Lista                               |    1    |    3    |    1    | Longitud de la Lista
+-------------+-------------+                                                    +---------+---------+---------+
|      B      |      E      | Enlace al primer nodo                              |    E    |    A    |    B    | Enlace al primer nodo
+-------------+-------------+                                                    +---------+---------+---------+

Observar que los registros deben contener un campo para enlazar los demas registros que están presentes en el mismo rango, y esto para cada una de las claves que se estan indexando.

Indice Invertido

Este tipo de índice es denso. O sea, todos los valores de claves presentes en el archivo son una entrada en el índice. Todos los valores de clave estan presentes en el índice. Existen varios arreglos de valores de clave, cada uno para una clave distinta. En el siguiente ejemplo estamos en presencia de cuatro claves :

Una clave numérica cuyos valores son 510, 620, 750, 800 y 950.

Una clave alfabética cuyos valores son analista y programador.

Una clave alfabética cuyos valores son femenino y masculino.

Una clave numérica cuyos valores son 9000, 10000, 12000 y 15000.

+---------+---------+---------+---------+---------+                              +-------------+-------------+
|   510   |   620   |   750   |   800   |   950   |                              |  analista   | programador |
+---------+---------+---------+---------+---------+                              +-------------+-------------+
|    1    |    1    |    1    |    1    |    1    |                              |      2      |      3      |
+---------+---------+---------+---------+---------+                              +-------------+-------------+
|    B    |    E    |    D    |    C    |    A    |                              |      B      |      A      |
+---------+---------+---------+---------+---------+                              +-------------+-------------+
                                                                                 |      C      |      D      |
                                                                                 +-------------+-------------+
                                                                                               |      E      |
                                                                                               +-------------+


          +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
          |   Datos   |      |   Datos   |      |   Datos   |      |   Datos   |      |   Datos   |
          +-----------+      +-----------+      +-----------+      +-----------+      +-----------+
           Registro  B        Registro  E        Registro  D        Registro  A        Registro  C


+-------------+-------------+                                                    +---------+---------+---------+---------+
|  femenino   |  masculino  |                                                    |   9000  |  10000  |  12000  |  15000  |
+-------------+-------------+                                                    +---------+---------+---------+---------+
|      3      |      2      |                                                    |    1    |    1    |    2    |    1    |
+-------------+-------------+                                                    +---------+---------+---------+---------+
|      B      |      A      |                                                    |    E    |    A    |    C    |    B    |
+-------------+-------------+                                                    +---------+---------+---------+---------+
|      C      |      E      |                                                                        |    D    |
+-------------+-------------+                                                                        +---------+
|      D      |
+-------------+

Observar que los registros ahora solo continen los datos. Los enlaces estan presentes en el índice. Si bien este ejemplo es para índices densos, muy poco hay que cambiar para trabajar con índices no densos y por lo tanto con el concepto de rango.

Indice Celular

Este tipo de índice es denso. O sea, todos los valores de claves presentes en el archivo son una entrada en el índice. Todos los valores de clave estan presentes en el índice. Existe un índice global e índices en cada celula. Ejemplos de celula puede ser una pila de discos, un cilindro, etc.. En el siguiente ejemplo estamos en presencia de una clave :

Una clave alfabética cuyos valores son femenino y masculino.

                                *-----------*      *-----------*      *-----------*                                            *-----------*
                                | Lista  en |      | Lista  en |      | Lista  en |                                            | Lista  en |
                                | la Celula |      | la Celula |      | la Celula |                                            | la Celula |
                                *-----------*      *-----------*      *-----------*                                            *-----------*
                                      A                  A                  A                                                        A
                                      |                  |                  |                                                        |
                                      |                  |                  |                                                        |
                                      |                  |                  |                                                        |
                                      |                  |                  |                                                        |
+-------------+------+            +---|--+------+    +---|--+------+    +---|--+------+                                          +---|--+------+                                 +---------+---------+---------+---------+
|  femenino   |   --------------->|   *  |   ------->|   *  |   ------->|   *  |   -------> .................................... |   *  |      |                                 |   9000  |  10000  |  12000  |  15000  |
+-------------+------+            +------+------+    +------+------+    +------+------+                                          +------+------+                                 +---------+---------+---------+---------+
|  masculino  |   --------------->|   *  |   ------->|   0  |   ------->|   *  |   -------> .................................... |   *  |      |                                 |    1    |    1    |    2    |    1    |
+-------------+------+            +---|--+------+    +------+------+    +---|--+------+                                          +---|--+------+                                 +---------+---------+---------+---------+
                                      |                                     |                                                        |
    Indice Global                     |   Celula             Celula         |   Celula                                               |   Celula
                                      |      1                  2           |      3                                                 |      n
                                      |                                     |                                                        |
                                      V                                     V                                                        V
                                *-----------*                         *-----------*                                            *-----------*
                                | Lista  en |                         | Lista  en |                                            | Lista  en |
                                | la Celula |                         | la Celula |                                            | la Celula |
                                *-----------*                         *-----------*                                            *-----------*

Observar que no en todos los cilindros hay claves. Observar que los registros ahora solo continen los datos. Los enlaces estan presentes en el índice global y en los índices de las celulas. Si bien este ejemplo es para índices densos, muy poco hay que cambiar para trabajar con índices no densos y por lo tanto con el concepto de rango.

Invertir Archivos de Texto

              +---------------------------------------------------+
   Archivo 1  |xxxxxxx xxx xxxxx xxxxx xxxx xxxxxx xxxxxx xxxxx xx|
              +---------------------------------------------------+

              +---------------------------------------------------------------------------+
   Archivo 2  |xxxxxxx xxx xxxxx xxxxx xxxx xxxxxx xxxx xxxxxx xxxx xxxxxx xxxxxx xxxxx xx|
              +---------------------------------------------------------------------------+

              +---------------------------------------------------------------+
   Archivo 3  |xxxxxxx xxx xxxxx xxxxx xxxx xxxxxx xxxx xxxxxx xxxxxx xxxxx xx|
              +---------------------------------------------------------------+
      .
      .
      .
      .
              +---------------------------------------------------------------------------------------+
   Archivo n  |xxxxxxx xxx xxxxx xxxxx xxxx xxxxxx xxxx xxxxxx xxxx xxxxxx xxxx xxxxxx xxxxxx xxxxx xx|
              +---------------------------------------------------------------------------------------+

               xxxxxxx = Palabras



   Proceso Batch para Invertir los Archivos

     Palabras
   +---------------+         +----------------------------+      +----------------------------+
   | Palabra a | *-|-------->| Archivo 1 - Posicion l | *-|----->| Archivo 3 - Posicion m | *-|
   +---------------+         +------------------------+---+      +------------------------+---+
   +---------------+         +----------------------------+      +----------------------------+      +----------------------------+
   | Palabra b | *-|-------->| Archivo 2 - Posicion n | *-|----->| Archivo 3 - Posicion o | *-|----->| Archivo n - Posicion p | 0 |
   +---------------+         +------------------------+---+      +------------------------+---+      +------------------------+---+
   +---------------+         +----------------------------+      +----------------------------+
   | Palabra c | *-|-------->| Archivo 1 - Posicion q | *-|----->| Archivo 3 - Posicion r | 0 |
   +---------------+         +------------------------+---+      +------------------------+---+
   +---------------+         +----------------------------+      +----------------------------+      +----------------------------+
   | Palabra d | *-|-------->| Archivo 3 - Posicion s | *-|----->| Archivo 3 - Posicion t | *-|----->| Archivo n - Posicion u | 0 |
   +---------------+         +------------------------+---+      +------------------------+---+      +------------------------+---+
          .
          .
          .
          .
          .
   +---------------+         +----------------------------+
   | Palabra e | *-|-------->| Archivo 1 - Posicion v | 0 |
   +---------------+         +------------------------+---+

Index Techniques ( Técnicas de Indexación )

Indice = Colección de pares de valores, el valor de la clave y el valor de la dirección en disco

( 510, t34 ); ( 620, t44 ); ( 750; t54 ); ( 800; t64 ); ( 900; t74 )

Cylinder-Surface Indexing ( Indexado Cilindro-Superficie )

fig. 4 : Archivo de algunos aviones utilizados en la 2da. Guerra Mundial

fig. 5 : Indice de Cilindros para el Archivo de la fig. 4

fig. 6 : Indice de Superficie, para el Cilindro 5 del Archivo de la fig. 4

fig. 7 : Valores de Claves de Ancho Variable

Hashed Indexes ( )

fig. 8 : Hash Tables con s = 1 y s = 2

fig. 9 : Número Promedio de Buckets recuperados vrs. Factor de Carga

fig. 10 : Número Promedio de Buckets recuperados para distintas técnicas de hashing

Tree Indexing - B-Trees ( )

fig. 11 : Ejemplo de un 3-way Search Tree

fig. 12 : Mejor AVL Tree para los datos de la fig. 11

fig. 13 : Search Tree de la fig. 11 con nodos de falla

fig. 14 : B-Tree de orden 3 para los datos de la fig. 11

fig. 15 : Tiempo de busqueda máximo total vrs. orden del arbol

fig. 16 : Inserciones en un B-Tree

fig. 17 : Eliminaciones en un B-Tree

Trie Indexing ( )

fig. 18 : Trie creado usando caracteres de la clave, de isquierda a derecha, uno a la vez

fig : 19 : Trie monstrando la necesidad de un caracter terminal ( blanco en este caso )

fig. 20 : Trie construido para los datos de la fig. 18, un caracter a la vez, de derecha a isquierda

fig. 21 : Un Trie óptimo para los datos de la fig. 18, usando el cuarto caracter de la clave

fig. 22 : Trie para los datos de la fig. 18 cuando el número de niveles está limitado a 3

fig. 23 : Sección del Trie de la fig. 18 mostrando las adiciones de bobwhite y bluejay