Almacenamiento de datos

3.- TÉCNICAS DE INDEXACIÓN

Se llama índice a aquel archivo usado para agilizar la recuperación de los registros, en respuesta a ciertas condiciones de búsqueda.
Un índice es redundante, con respecto a los datos del archivo, puesto que la información que guarda se encuentra presente en éste, lo cual implica un mayor gasto en el espacio en disco; sin embargo, se compensa por el hecho de quea través de él, es posible encontrar los datos buscados más rápidamente.

Tipos de Índices

Existen diversos criterios para poder identificar los distintos tipos de índices; algunos de éstos son:
• Campo de Indexación: según el campo usado para construir, el índice se llama primario, de grupos o secundario.
a) Índice Primario (Principal): Índice especificado sobre el campoclave de ordenamiento de un archivo ordenado de registros.
b) Índice Agrupado (Clusterizado): Índice construido sobre un campo de ordenamiento que abarca varios registros con el mismo valor, dentro de un archivo ordenado de registros.
c) Índice Secundario: Índice especificado sobre un campo que no es usado para ordenar un archivo.

• Número de Referencias: si el índice tiene unaentrada por cada registro del archivo, el índice se denomina denso; en caso contrario, dicho índice toma el nombre de índice no denso o disperso.

• Tipo de Referencia: si la entrada del índice contiene una referencia al archivo de datos que consiste en un puntero físico que especifica la dirección del registro físico sobre el disco, mediante una combinación del tipo (número de bloque, offset),el índice se llama índice físico. Si cada entrada del índice tiene como referencia al archivo de datos el valor de otro campo, entonces se denomina índice lógico (un índice lógico es usado cuando las direcciones de los registros físicos continuamente están cambiando. El costo adicional es la búsqueda extra basada sobre la organización del archivo de datos).

• Estructura de las Referencias: lasreferencias al área de datos se pueden estructurar como:
a) Tener una entrada de largo fijo, con un puntero al archivo de datos, ya sea como puntero a un bloque de disco o como puntero a un registro.
b) Tener registros de largo variable en el índice, con un campo repetitivo para que permita almacenar un puntero a cada bloque del disco que contiene un registro. A este esquema se le acostumbrallamar archivo o lista invertida.
c) Mantener las entradas del índice de largo fijo y tener una única entrada por cada valor del campo de indexación, pero creando un nivel extra de indirección para manipular los múltiples punteros.
d) Mantener las entradas del índice de largo fijo y tener un bitmap asociada a cada una de ellas, el cual tenga un bit por cada bloque del archivo de datos; elbitmap guarda un valor 1 en los bits de los bloques que contiene un registro con el valor de la entrada, y un valor 0 en caso contrario.

3.1 Índices Ordenados

3.1.1 Índices de un Nivel

Índice Primario (Principal)

Un índice primario se caracteriza por:
1. Archivo ordenado, cuyos registros son de largo fijo.
2. Cada entrada del archivo tiene 2 campos:
1. Una del mismo tipodel campo clave de ordenamiento del archivo de datos.
Un puntero a un bloque del disco.
3. El número total de entradas del índice es igual al número de bloques de disco presentes en el archivo de datos.
4. Índice no denso.
5. Ocupa menos bloques que el archivo de datos, pues:
6. Por cada bloque de datos guarda sólo una entrada.
7. Cada entrada es más pequeña que un registro dedatos, pues sólo guarda dos datos.

Operaciones

8. Búsqueda: Binaria si se hace sobre el campo de indexación. Sino, lineal.
9. Inserción: Compleja, pues implica corrimientos en el archivo de datos (además de las posibles modificaciones en el ancho de los bloques) y cambios en las entradas del índice.
10. Eliminación: Uso de marcas de borrado.

Índice de Grupos

Un índice de...