6. Indexamiento

6.1 Definición de índice (index)

Tomemos como analogía el índice de los libros.

"Es una tabla que contiene una lista de elementos (llaves)  y números de referencia donde dichos elementos se encuentran (campos de referencia)".

Qué nos permite un índice ??

a) Imponer un orden en un archivo sin tener que reordenarlo
 

 

b) Proveer múltiples caminos de acceso a un archivo
 

 

 

---

Indices para búsquedas, no se requiere acceso secuencial a los datos
(Non indexed sequential access)

6.2 Simple index

Recordemos que el objetivo inicial para usar índices era poder hacer búsquedas binarias en los archivos de manera que encontráramos más rápidamente los registros deseados

Dichas búsquedas se realizan en base a la "llave primaria" o "primary key" que identifica de manera única a nuestro registo. Dicha llave puede estar compuesta por varios campos, como se muestra en el ejemplo siguiente.
 

 

 

---

6.3 Operaciones para el mantenimiento de un archivo indexado.

-Asumiendo que todo el índice cabe en memoria

Crear los archivos

• Alguna vez deberán crearse ambos archivos, el index file y el data file
• Al principio estarán vacíos

Cargar el índice en memoria

• Leer los registros del archivo de datos, crear el índice en memoria y ordenarlo bajo el criterio de la llave primaria
• Puede existir previamente un archivo índice, en este caso habría que cargarlo en memoria y solo actualizarlo con los nuevos datos

Reescribir el archivo índice (index file) de memoria

• Bajar el índice a disco para usarlo posteriormente
• Nota:  debemos asegurarnos de que esta operación tenga algunas medidas contra desastres
• Como se está destruyendo el archivo índice una solución sería poner una bandera, de modo que si el proceso no se completa, la próxima vez se sabe que quedo pendiente esa tarea y hay que ejecutarla de nuevo.

Agregar Registros

• Al insertar un registro nuevo recordar agregarlo en ambos lados, el archivo de datos (no importa el orden) y en el índice en memoria (manteniendo ordenado el índice)
• Nota: aquí estamos asumiendo que el índice puede manejarse "todo" en memoria, posteriormente trataremos el caso en que no.

Eliminar Registros

• Compactación y Reutilización de Espacio
• Aqui podríamos hacer una mezcla de ambos, los registros de datos al estar en disco podríamos reutilizarlos (colocándoles una marca y agregándolos a la pila de disponibles, se conocen como "pinned records"), pero el índice como está en memoria podemos compactarlo sin mayor dificultad (usando memoria dinámica)

Actualizar Registros
Existen 2 posibilidades

• La actualización cambia el valor de la "llave" : en este caso debemos reordenar el índice y quizás (debido al cambio de tamaño) mover el registro en el archivo de datos. La mejor opción sería eliminar e insertar de nuevo.
• La actualización NO afecta el valor de la "llave": en este caso sólo habría que ver si es necesario reacomodar el archivo de datos por el cambio de tamaño, aquí la solución de eliminar e insertar es opcional pero en ocasiones conveniente.

---

6.4 Indices en relación con su tamaño

6.4.1 Indices Densos e Indices Esparcidos

Cuando hablamos de índices podemos hacer una división de acuerdo al número de elementos que posee en relación con el archivo de datos
De manera que tenermos 2 categorías:
Indices densos: aquellos que poseen un número de elementos igual al de registros en el archivo de datos
Indices esparcidos: aquellos que son más reducidos que su respectivo archivo de datos

Ventajas:
Indice denso: poder encontrar cualquier registro rápidamente o bien determinar su inexistencia, además de poder accesar a la infomación en O(1) .
Indice esparcido: su tamaño hace que pueda ser mantenido en memoria ram sin ningún problema

Desventajas:
Indice denso: su gran tamaño; aunque en realidad no es tan significante y de ahi que sean los más utilizados
Indice esparcido: por lo general, forzosamente tiene que accesar al archivo original para determinar la existencia de algun registro, o bien hacer algunos accesos secuenciales para recuperarlo.

Archivo Indice denso                       Key                          Posición 10 1 20 2 30 3 40 4 50 k

Archivo      Posición                         Registro 1 10 | Itaca | Chicago 2 20 | Kellog | New York 3 30 |Harris |  California 4   40 |  Williams | Portland k 50 | Bell |  Denver

 

Archivo Indice esparcido                       Key                          Posición 10 1 30 3 50 k 70 l 90 m

Archivo      Posición                         Registro 1 10 | Itaca |  Chicago 2 20 | Kellog |  New York 3 30 | Harris | California 4  40 |  Williams | Portland k 50 | Bell |  32 | Denver

 

 

---

6.4.2 Indices que son demasiado grandes para procesarse en memoria

Lo que se ha mencionado hasta el momento, y desafortunadamente muchas de las ventajas que presenta es que estamos asumiendo que el índice tiene un cierto tamaño que puede ser almacenado y procesado en memoria RAM. En caso de que suceda lo contrario lo que se debe hacer es procesar directamente el índice en disco (almacenamiento secundario) lo cual presenta ciertas desventajas:
 

• Búsqueda Binaria en disco requiere muchos "seeks", lo cual hace que el procedimiento sea más lento
• El reacomodamiento de los índices (por alguna de las operaciones de mantenimiento) requiere el recorrer u ordenar ciertos registros, esto es millones de veces más lento que hacerlo en memoria primaria.

Soluciones:

• Una organización basada en Hash, si la velocidad es prioridad
• Una estructura de árbol , índices multinivel , ej B-Tree, para mejorar el acceso y el reacomodamiento.

Importante:
El hecho de que existan estas desventajas no quiere decir que no se use este método, en realidad presenta ventajas:

• El posible usar un índice simple (cuya longitud generalmente es fija) para encontrar registros de longitud variable
• Aún cuando se pueden tener muchos elementos en el índice, éste es más pequeño que procesar el archivo de datos.
• Reutilizar el espacio con los "pinned records"

---

 

6.5 Múltiples Llaves

6.5.1  Indexado para acceso por Múltiples llaves

En el ejemplo 6.2 indexamos los registros por su Label y su ID, pero en la práctica únicamente nos interesaría búsquedas por estas llaves ??

No, es lógico pensar en búsquedas por otros campos, por ejemplo todos los registros cuyo autor sea "Beethoven" o bien todas las canciones cuyo título sea "Symphony No. 9", de modo que pudieramos obtener alguna referencia (primary key) hacia todos los registros que cumplan con nuestro criterio de búsqueda.

De manera que lo primero que se nos viene a la mente es crear otros "índices" basados en estos campos que son de interés, a estos campos se les conoce como "llaves secundarias" o "secondary keys".

Una diferencia de estos índices de llaves secundarias es que debemos obtener primero la llave primaria  para entonces poder recuperar la posición (ubicación) de dicho registro, a esto se le conoce como "entry sequenced" .
Pensemos en un registro de una licencia de manejo, llegamos a hacer nuestro examen y nos piden nuestro nombre, nos buscan y obtienen el número de licencia y gracias a éste se pueden recuperar todos los demás datos y aplicar el examen correspondiente.
 
 

Es claro notar que a simple vista resultaría mejor tener directamente la posición del registro en lugar del primary key, pero analizando las operaciones relacionadas con dichos archivos descubriremos el motivo.

Agregación de Registros

• Cuando se inserta un registro nuevo el proceso es muy similar al de agregar el índice primario, se debe hacer un reordenamiento de los registros, si éstos caben en memoria estonces no hay mucho problema y se hará rápidamente.
• Es importarte notar que las llaves secundarias se almacenan en forma "canónica", es decir:
  • En mayúsculas para facilitar las búsquedas y comparaciones
  • Con longitud fija y quizás de un tamaño mucho menor que la del campo, de manera que algunos datos se "truncan"
• Otra característica importante es que aquí el índice secundario puede contener duplicados ( a diferencia del primary key donde cada llave identifica de manera única el registro). Estos duplicados se colocan juntos a manera de grupo y se orden de acuerdo al primary key.

Eliminación de Registros

• Aquí tiene sentido el no usar la posición real del registro en el índice secundario y en su lugar usar la llave primaria.
• Si tuvieramos en todos los índices las posiciones entonces al eliminar tendríamos que actualizar todos esos archivos (índices secundarios) lo cual consumiría demasiado tiempo, pero de otra forma tendríamos referencias a registros que ya no existen o bien ya son reutilizados y contienen otra información.
• Teniendo la referencia al primary key lo único que debemos hacer es eliminar el registro del archivo de datos y eliminarlo del índice primario. Aquí podemos ver que la ventaja es que no se afectan tantos archivos y cuando necesitamos hacer una búsqueda solo "validamos" si el registro sigue existiendo o no, lo cual es más rápido.
• Es conveniente en muchos casos realizar una compactación periódica de todos los archivos para aprovechar el espacio "basura" que se genera en los archivos índice.

Actualización de Registros

• Nuevamente el hecho de no utilizar la posición del registro en cada uno de los índices nos evita el tener que actualizar muchos archivos cuando en realidad solo tenemos que actualizar el índice primario.
• Pero existen 3  posibilidades de cambios:
  • Actualizar alguna llave secundaria:  entonces debemos reordenar únicamente el índice secundario.
  • Actualizar la llave primaria: debemos actualizar el índice primario y cambiar las referencias que teníamos desde los índices secundarios (tener cuidado que para esto último se puede requerir reordenar, debido a los registros duplicados que cambiarían de orden)
  • Actualizar otros campos: únicamente actualizar el archivo de datos, esto puede convertirse en una acción de eliminar e insertar.

---

6.5.2 Recuperación usando combinaciones de llaves secundarias

Por lo general lo que se necesita es "restringir" o "delimitar" las búsquedas, de manera que utilizamos varios criterios para definir lo que estamos buscando.
Esto no es nada nuevo, lo hemos usado en buscadores tradicionales "udla and biblioteca", solo que aquí estamos definiendo qué buscar en qué llave secundaria:
"universidad=udla and departamento=biblioteca".

Para el ejemplo que estamos presentando sería algo como:

Encuentra todos los datos de los registros con:
composer='BEETHOVEN' and title='SYMPHONY NO. 9'   .

Buscando en el índice secundario por "composer" obtenemos:
 

Y del índice secundario por "title":
 

de manera que :
 
 

Buscando el Match en el índice primario:

ANG3795 nos da la posición :  152
            ANG | 3795 | Symphony No. 9 | Beethoven

DG18807 nos da la posición: 241
            DG | 18807 | Symphony No. 9 | Beethoven

---

6.6 Archivos Invertidos (Listas Invertidas)

Los índices secundarios que hemos manejado hasta el momento presentan algunas dificultades:
 

• Tenemos que reorganizar el archivo índice cada vez que un nuevo registro es agregado.
• Si existen llaves secundarias duplicadas, el campo de dicha llave se repite muchas veces y desperdiciamos espacio (unos de los motivos por el cual no es posible almacenarlo en memoria).

Alguna solución que ha surgido

Colocar un arreglo de índices dentro del mismo registro
 
 

Las ventajas de este esquema, o lo que se espera de él:

• No requiere reordenar el archivo cuando hay  nuevos elementos o al eliminarlos
• Permitir muchas referencias (llaves primarias) asociadas a cada llave secundaria (no únicamente 4)
• Elimina el desperdicio de espacio debido a fragmentaciones.

El  planteamiento anterior suena muy bien, pero....como se implementaría ??
El problema:
No podemos tener un registro infinito que nos permita almacenar N número de referencias.

Nuevamente las estructuras de datos van a solucionar este problema.
Utilizaremos algo que se conoce como "listas invertidas" o "archivos invertidos", las cuales son listas ligadas que nos permiten agregar o eliminar referencias.
El término de "invertida" únicamente se refiere al procedimiento que tenemos que seguir porque primero buscamos en el índice secundario y posteriormente la primaria.
 
 

Ya implementado sería:
 
 

Los archivos invertidos tienen algunas ventajas:

• El único reacomodamiento  necesario en el índice secundario es cuando agregamos nuevas llaves secundarias
• En el caso de reacomodar el índice secundario la tarea es menor y mucho más rápida  debido a que tiene menos registros
• Debido a que ahora tenemos menos elementos que ordenar, el hecho de que el índice se guarde en disco y no en memoria no tiene trascendencia.
• La lista ligada (en el ejemplo Label ID List file ) nunca requiere ordenarse, es "entry sequenced"
• El espacio en dicha lista ligada se puede reutilizar fácilmente puesto que los registros son de longitud fija.

---