En un post anterior, veíamos un ejemplo de acceso indexado en el que no ordenábamos los datos, lo que nos obligaba a tener la dirección de registro para todos los valores posibles de la clave. Si el usuario introdujera un valor que no tuviéramos registrado en la estructura de índices, sería imposible acceder al registro. Esto podemos solucionarlo con la indexación por acceso secuencial.

Si ordenamos tanto los datos del fichero como los de la estructura de claves, por los valores del campo indexado, cuando no tengamos uno de esos valores en la tabla de índice, podemos usar el índice del valor anterior más cercano, que nos dirigirá a un registro en el fichero anterior y cercano al que buscamos, y comenzar una búsqueda secuencial desde ese registro en lugar desde el principio del fichero.

Cuando en nuestra estructura tengamos un registro de índice para cada valor del campo indexado, tendremos un índice denso. Por el contrario, si hay valores del campo indexado que no tienen registro en la estructura de claves, tendríamos un índice escaso.

Al tener los datos ordenados, podemos trabajar con índices escasos, que en la practica nos van a permitir ubicarnos en un registro cercano al que buscamos, a partir del cual, llegar al registro que buscamos con una búsqueda secuencial corta. Todo esto lo veremos en más detalle en el próximo post.

Ejemplo de indexación por acceso secuencial

Para realmente entender la indexación por acceso secuencial, conviene verlo en la práctica. Para ello podemos seguir el siguiente ejercicio, con nuestro ya viejo conocido Antonio y su supermercado Gades.

Paso 1: El fichero de partida.

Seguimos con Antonio y con su fichero de proveedores. Si ordenamos ahora tanto la tabla de claves como los datos, tendríamos lo siguiente:

Fichero de partida con la información de proveedores

Recordemos que el fichero de proveedores tiene mil registros y que estamos usando como clave el campo nombre de proveedor.

A primera vista, puede parecer que no ganamos mucho definiendo la estructura de índices/claves en paralelo, a fin de cuentas tendríamos el mismo número de registros con únicamente un campo menos. La realidad es que el fichero de proveedores tendría muchos más campos que no pinto en este ejercicio por un tema de practicidad, por mantenerlo sencillo y didáctico. Sin embargo, imaginaros que el fichero de proveedores también tiene el email, la dirección, la fecha de inicio de relaciones, etc. En este caso, la diferencia de tamaños ya empezaría a ser significativa.

Paso 2: Acceso con índice denso

Recordemos que teníamos un índice denso cuando para cada valor del campo indexado, teníamos un registro de índice. En nuestro ejemplo, cuando para cada valor del campo “nombre del proveedor” tenemos una clave, tendríamos un índice denso. Por el contrario, basta con que exista un “nombre de proveedor” que no tenga una clave en la tabla de índices, para tener un índice escaso.

Recordemos también, que la tabla de índices se carga en la memoria del sistema, la RAM, y por tanto el acceso a ella será mucho más rápido que el acceso al fichero de proveedores, que reside en la memoria secundaria, en el disco duro.

Con un índice denso, recorreríamos la tabla de índices hasta encontrar la clave buscada, y empleando la dirección para dicha clave, iríamos a buscar el registro correspondiente al fichero de proveedores. Minimizamos al máximo nuestro recorrido en memoria secundaría, yendo directamente al registro deseado.

Acceso con indice denso

Paso 3: Introduciendo y eliminando datos

Hasta este punto hemos visto como creando una estructura de índices podemos mejorar sensiblemente la eficiencia en el acceso a los datos, pero hay otras dos tareas que también hay que realizar: el registro y el borrado de datos.

Cada vez que introduzcamos un proveedor nuevo en nuestro archivo, tendremos que introducir su nombre y dirección en la tabla de índices, asegurándonos que estos están ordenados, es decir hay que insertar los datos donde corresponda según estén ordenados.

Para la eliminación de un dato nos ocurre algo parecido al registro, tenemos que actuar tanto en el archivo de datos como en la estructura de índices.

Paso 4: Acceso con índice escaso, acceso por bloques

Si trabajamos con índices escasos, tendremos valores del campo indexado que no estarán registrados en la tabla de índices. En este caso, vamos a tener un acceso secuencial por bloques, accederemos al registro más cercano al buscado, y desde este recorreremos secuencialmente el archivo hasta dar con el registro que buscamos.

Veámoslo con un ejemplo en el fichero proveedores. Para ello, he añadido algunos registros que hay entre “Frutas Gutierrez” y “Hortalizas del Sur”

Acceso con indice escaso

Si quisiéramos acceder a los datos del proveedor “Gallos de Corral”, empleando la tabla de índices, nos colocaríamos sobre el registro más cercano (Frutas Gutierrez) en la tabla de proveedores, y desde ahí, iríamos recorriendo los registros de forma secuencial hasta dar con el que estamos buscando: “Gallos de Corral”.

Con este ejemplo, creo que resulta sencillo entender porque se habla de acceso por bloques. Al no tener una clave para todos los registros, cada clave pasa a direccionar un grupo de registros, un bloque que empieza por el registro direccionado por la clave e incluye todos los registros consecutivos que no tienen clave hasta llegar a un registro que si tiene clave en la tabla de índices.

Paso 5: ¿Índice escaso o denso?

Normalmente emplearíamos un índice denso si hay pocas actualizaciones e inserciones de datos. En esta situación, no tendríamos que estar actualizando con demasiada frecuencia la tabla de índices.

Los índices escasos los emplearíamos cuando las consultas son pocos frecuentes y no tenemos una necesidad grande de velocidad de recuperación de datos. Dejaríamos crecer el fichero proveedores, vigilando el tamaño que van cogiendo los bloques, y actualizaríamos la tabla de índices de forma periódica, según fueran apareciendo bloques de gran tamaño que habría que segmentar.

NOTA:

Este post es parte de la colección “Arquitectura de Datos” que reproduce los apuntes de la clase que imparto sobre el tema en ESIC. Puedes ver el índice de esta colección aquí.