Acceso Indexado

Después de los archivos de acceso aleatorio que explicaba en otro post, aparece el acceso indexado para corregir los principales inconvenientes de aquellos. Los archivos de acceso aleatorio suponían una reducción considerable en el tiempo de búsqueda de un dato sobre los archivos de acceso secuencial. Sin embargo, había que conocer exactamente el número de registro del dato que querías buscar, lo cual es muy poco práctico, ya que normalmente querremos buscar por valores en los distintos campos.

Veámoslo con nuestro personaje Antonio, que cambio de los archivos de acceso secuencial a los archivos de acceso aleatorio. Resulta que al buscar un proveedor por el número de registro, se equivoca muchísimas veces, a él le gustaría poder buscar los datos del proveedor por el nombre del proveedor o por el nombre del contacto. Pero al tener que hacerlo por el número de registro, en no pocas ocasiones no consigue recordar este dato.

Para solucionar este tema, se comenzó a trabajar con índices. Un índice no es más que un campo que se emplea como clave para agilizar la búsqueda de registros. En los archivos de acceso aleatorio, el índice era el número de registro y ahora queremos que el índice sea un campo del registro por el que poder buscar.

Básicamente, lo que hacemos es construir una estructura adicional que, para los valores del campo escogido como índice, recoge todas las direcciones de comienzo de los registros que tienen dicho valor. Tendremos que crear una estructura para cada índice que escojamos, en el caso que nos ocupa, dos estructuras: para el campo nombre del proveedor y para el campo contacto del proveedor.

Lo bueno es que estas estructuras se cargan en la RAM y por tanto el acceso es mucho más rápido que con los ficheros secuenciales que íbamos a la memoria secundaria (discos duros).

Cuando un campo es utilizado como índice, se dice que dicho campo está indexado. De similar forma, hablamos de acceso indexado cuando trabajamos con estas estructuras de índices para acceder a los datos más rápidamente.

Ejemplo de acceso indexado

Tras explicar los archivos de acceso secuencial y los de acceso aleatorio, le toca el turno al acceso indexado. Recordemos que, aunque el acceso aleatorio supuso una mejora de la velocidad de acceso a datos, estábamos obligados a conocer el número de registro que estábamos buscando, ya que era a través de este parámetro como nos situábamos en la zona de memoria donde estaban los datos que buscábamos. Esta manera de trabajar, aunque fuera rápida, era bastante engorrosa, en la práctica lo que se necesitaba era poder buscar por los valores de un parámetro, no por el número de registro.

Para entenderlo mejor, veámoslo con el ejemplo de nuestro ya viejo conocido Antonio y su supermercado Gades.

Paso 1: El fichero de partida

Vamos a modificar ligeramente el fichero de proveedores que habíamos venido utilizando, para poder explicar mejor las estructuras de índices. Para ello, represento el fichero por registros, como si fuera una tabla, en lugar de por líneas en el archivo. Creo que se entenderá mejor con esta representación.

El fichero proveedores quedaría:

Datos de proveedores
Datos de proveedores

El número de registro no vamos a usarlo, pero lo mantengo para que se entienda la estructura y se aprecie que partimos del fichero ordenado por número de registro.

Paso 2: Indexamos por el campo nombre de Proveedor

En este caso estamos hablando de un índice sin duplicados, asumimos que no puede haber dos proveedores con el mismo nombre, es decir, no puede haber dos registros que tengan el mismo valor para el campo de nombre de proveedor.

Se crearía una estructura que para cada valor del campo nombre de proveedor guardaríamos la dirección del registro que tiene dicho valor:

Tabla con las claves y direcciónes
Clave – Dirección dirección de registros

La relación entre esta estructura de índices y los registros de nuestro archivo sería:

Indices y registros
Índices y registros

Donde básicamente quiero representar que cada dirección asociada a una clave en la estructura que hemos creado, apunta a la dirección de memoria del registro cuyo valor en el campo indexado es igual a la clave.

Paso 3: Empleando la estructura de índices para las búsquedas

Con la estructura de índices creada, Antonio ya puede buscar un proveedor por su nombre. Como esta estructura está en la memoria del sistema, la consulta será rápida, y obtendremos la dirección en memoria secundaria donde ir a buscar el registro con el nombre de proveedor seleccionado.

De momento, estamos recorriendo la estructura de claves de forma secuencial, pero veremos más adelante que existen maneras más eficientes de hacerlo.

Paso 4: Indexando por el campo contacto del proveedor

La principal diferencia de este campo con respecto al nombre de proveedor, que hemos usado en el paso 2 como índice, es que contacto de proveedor admite duplicados. En la práctica esto significa que para una clave podemos tener varios registros que tengan la clave en el campo indexado, luego necesitaremos la dirección en memoria de cada uno de esos registros.

En el ejemplo que venimos manejando, el contacto de los proveedores “Azucarera Sevillana” y “Espárragos Cojonudos” tiene el mismo nombre, da la casualidad que se llaman los dos Rodrigo Mendez, aunque son contactos diferentes.

Índice que admite duplicados
Índice que admite duplicados

Puede observarse como la clave “Rodrigo Mendez” tiene dos direcciones, cada una apunta a un registro de los que contienen dicha clave en el campo indexado: contacto proveedor. En este caso, estamos utilizando un índice que admite duplicados.

Indexación por acceso secuencial

En ejemplo anterior de acceso indexado, 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.

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:

Datos de partida
Datos de partida

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.

Índice denso
´Índice 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”

Índice escaso
Índice 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 “Sistemas de acceso y almacenamiento de datos”. Puedes ver el índice de esta colección aquí.