Indexación y asociatividad (hashing).
Muchas consultas hacen referencia a sólo una pequeña parte de los registros de un archivo. Es
ineficiente que elsistema tenga que leer todos los registros. Lo ideal es que el sistema pueda
localizar directamente estos registros. Parapermitir estas formas de acceso diseñamos estructuras
adicionales que asociamos con archivos. Consideraremos dosformas generales de atacar éste
problema: la construcción de índices y la construcción de funciones de asociatividad(hash).
Conceptos básicos.
Un índice de un archivo funciona de manera similar a un catálogo en una biblioteca. Si estamos
buscando un libro por un autor determinado, buscamos en autores y una tarjeta de catálogo nos dice
dónde encontrar el libro. Parafacilitarnos la búsqueda, las tarjetas se guardan en orden alfabético, de
forma que no tenemos que comprobar todas paraencontrar la que queremos.En las BD es posible
que estos tipos de índices sean demasiado grandes para manejarse eficientemente. En vezde ello,
pueden utilizarse técnicas de indexación más sofisticadas. Como alternativa a la indexación se
utilizan funcionesde asociatividad. Consideraremos varias técnicas tanto de asociatividad como de
indexación. Ninguna de ellas es lamejor, sino que cada una es más apropiada para una aplicación
específica de BD. Cada técnica debe evaluarse en base a:
Tiempo de acceso. El tiempo que se tarda en encontrar un dato determinado.
Tiempo de inserción. El tiempo que se tarda en insertar un dato nuevo. Esto incluye el tiempo que se
tardaen encontrar el lugar correcto, así como el que se tarda en actualizar la estructura de indexación.
Tiempo de eliminación. El tiempo que se tarda en eliminar un dato. Esto incluye el tiempo que se
tarda enencontrar el dato, así como el que se tarda en actualizar la estructura de indexación.
Espacio extra. El espacio adicional que ocupa la estructura de indexación. Siempre que este espacio
no seamuy grande, merece la pena sacrificar el espacio por una mejora en el rendimiento.Muchas
veces queremos tener más de un índice o función de aosciatividad para un archivo. El atributo o
conjunto de atributos que se usa para buscar registros en un archivo se llama
clave de búsqueda
OJO no hay que confundir índice con clave o llave de búsqueda, el índice es el archivo que contiene
las claves de búsqueda y el apuntador al registro correspondiente.
Indexación.
Para pemitir el acceso aleatorio rápido a los registros de un archivo se utiliza una estructura de
índice. Cadaestructura de índice está asociada con una clave de búsqueda determinada. Si el archivo
está ordenado secuencialmente y elegimos incluir varios índices en diferentes claves de busqueda, el
índice cuya clave de búsqueda especifíca el ordensecuencial del archivo es el índice primario
Los demás se llaman
índices secundarios
La clave de búsqueda de un índice primario es normalmente la clave primaria. En esta sección
suponemos que todos los archivos están ordenados secuencialmente y, por tanto, tienen una clave
de búsqueda primaria. Dichos archivos, junto con un índice primario, se llaman archivos de índices
secuenciales. Se encuentran entre los esquemas de indexación más antiguos usados en los BDMS.
, Están diseñados para aplicaciones que requieren tanto un procesamiento secuencial del archivo
completo como un acceso aleatorio a registros individuales. Hay dos tipos de índices que pueden
usarse;
Índice denso. Aparece un registro índice para cada valor de la clave de búsqueda en el archivo. El
registro contiene el valor de la clave de búsqueda y un puntero al registro.
Índice escaso. Se crean registros índices solamente para algunos de los registros. Para localizar un
registro, encontramos el registro índice con el valor de la clave de búsqueda más grande que sea
menor o igual que el valor que estamos buscando. Empezamos en el registro al que apunta el registro
índice y seguimos los punteros del archivo hasta encontrar el registro deseado.
Índice primario.
Generalmente es más rápido localizar un registro con un índice denso que con uno escaso. Sin
embargo, los índices escasos requieren menos espacio e imponen menos mantenimiento adicional
para inserciones y eliminaciones.
Bases de Datos
El diseñador del sistema debe lograr un equilibrio entre el tiempo de acceso y el espacio extra. Un
buen compromiso es tener un índice escaso con una entrada de índice por bloque.Para que esta
técnica sea completamente general, debemos considerar el caso en el que los registros para un valor
de la clave de búsqueda ocupan varios bloques. Es fácil modificar el esquema para manejar esta
situación. Aún cuando utilizamos un índice escaso, el índice puede llegar a ser demasiado grande
para un procesamiento eficiente. En la práctica, no es raro tener un archivo con 100.000 registros.
Con 10 registros por bloque. Si tenemos un registro índice por bloque, el índice tiene 10.000 registros.
Los registros índice son más pequeños que los de datos, por lo que podemos suponer que entran 100
por bloque, así pues el índice ocupa 100 bloques. Si un índice es lo bastante pequeño como para
guardarlo en memoria, el tiempo de búsqueda es corto. Sin embargo, si le índice es tan grande que
debe guardarse en disco, una búsqueda puede ser costosa. Para resolver este problema, tratamos el
índice como cualquier otro archivo secuencial, y construimos un índice escaso sobre el índice
primario, que puede almacenarse en memoria. Utilizando los dos niveles de indexación, hemos leído
únicamente un bloque de índices en vez de 100. Si suponemos que el índice externo ya está en la
memoria. Si el fichero es extremadamente grande, es posible que ni siquiera el índice exterior quepa
en memoria principal, en este caso, podemos crear otro nivel de indexación. En la práctica, lo normal
es que basten dos niveles. Frecuentemente, cada nivel de índice corresponde a una unidad de
almacenamiento físico. Así, podemos tener índices en los niveles de pista, cilindro y disco. Sin
importar cual sea la forma de índice que se utilice, se deben actualizar todos los índices cada vez que
seinserta o elimina un registro del archivo. A continuación describimos algoritmos para actualizar
índices de un sólo nivel:
Eliminación. Para eliminar un registro, es necesario buscar el registro que se va a eliminar. Si el
registro eliminado era el último que quedaba con ese valor particular de la clave de búsqueda,
entonces eliminamos el valor de la clave de búsqueda del índice. Para índices densos, eliminamos un
valor de la clave de búsqueda de la misma manera que se suprime en un archivo. Para índices
escasos, eliminamos un valor de clave sustituyendo su entrada en el índice por el siguiente valor de la
clave de búsqueda. Si el siguiente valor ya tiene una entrada de índice, eliminamos la entrada.
Muchas consultas hacen referencia a sólo una pequeña parte de los registros de un archivo. Es
ineficiente que elsistema tenga que leer todos los registros. Lo ideal es que el sistema pueda
localizar directamente estos registros. Parapermitir estas formas de acceso diseñamos estructuras
adicionales que asociamos con archivos. Consideraremos dosformas generales de atacar éste
problema: la construcción de índices y la construcción de funciones de asociatividad(hash).
Conceptos básicos.
Un índice de un archivo funciona de manera similar a un catálogo en una biblioteca. Si estamos
buscando un libro por un autor determinado, buscamos en autores y una tarjeta de catálogo nos dice
dónde encontrar el libro. Parafacilitarnos la búsqueda, las tarjetas se guardan en orden alfabético, de
forma que no tenemos que comprobar todas paraencontrar la que queremos.En las BD es posible
que estos tipos de índices sean demasiado grandes para manejarse eficientemente. En vezde ello,
pueden utilizarse técnicas de indexación más sofisticadas. Como alternativa a la indexación se
utilizan funcionesde asociatividad. Consideraremos varias técnicas tanto de asociatividad como de
indexación. Ninguna de ellas es lamejor, sino que cada una es más apropiada para una aplicación
específica de BD. Cada técnica debe evaluarse en base a:
Tiempo de acceso. El tiempo que se tarda en encontrar un dato determinado.
Tiempo de inserción. El tiempo que se tarda en insertar un dato nuevo. Esto incluye el tiempo que se
tardaen encontrar el lugar correcto, así como el que se tarda en actualizar la estructura de indexación.
Tiempo de eliminación. El tiempo que se tarda en eliminar un dato. Esto incluye el tiempo que se
tarda enencontrar el dato, así como el que se tarda en actualizar la estructura de indexación.
Espacio extra. El espacio adicional que ocupa la estructura de indexación. Siempre que este espacio
no seamuy grande, merece la pena sacrificar el espacio por una mejora en el rendimiento.Muchas
veces queremos tener más de un índice o función de aosciatividad para un archivo. El atributo o
conjunto de atributos que se usa para buscar registros en un archivo se llama
clave de búsqueda
OJO no hay que confundir índice con clave o llave de búsqueda, el índice es el archivo que contiene
las claves de búsqueda y el apuntador al registro correspondiente.
Indexación.
Para pemitir el acceso aleatorio rápido a los registros de un archivo se utiliza una estructura de
índice. Cadaestructura de índice está asociada con una clave de búsqueda determinada. Si el archivo
está ordenado secuencialmente y elegimos incluir varios índices en diferentes claves de busqueda, el
índice cuya clave de búsqueda especifíca el ordensecuencial del archivo es el índice primario
Los demás se llaman
índices secundarios
La clave de búsqueda de un índice primario es normalmente la clave primaria. En esta sección
suponemos que todos los archivos están ordenados secuencialmente y, por tanto, tienen una clave
de búsqueda primaria. Dichos archivos, junto con un índice primario, se llaman archivos de índices
secuenciales. Se encuentran entre los esquemas de indexación más antiguos usados en los BDMS.
, Están diseñados para aplicaciones que requieren tanto un procesamiento secuencial del archivo
completo como un acceso aleatorio a registros individuales. Hay dos tipos de índices que pueden
usarse;
Índice denso. Aparece un registro índice para cada valor de la clave de búsqueda en el archivo. El
registro contiene el valor de la clave de búsqueda y un puntero al registro.
Índice escaso. Se crean registros índices solamente para algunos de los registros. Para localizar un
registro, encontramos el registro índice con el valor de la clave de búsqueda más grande que sea
menor o igual que el valor que estamos buscando. Empezamos en el registro al que apunta el registro
índice y seguimos los punteros del archivo hasta encontrar el registro deseado.
Índice primario.
Generalmente es más rápido localizar un registro con un índice denso que con uno escaso. Sin
embargo, los índices escasos requieren menos espacio e imponen menos mantenimiento adicional
para inserciones y eliminaciones.
Bases de Datos
El diseñador del sistema debe lograr un equilibrio entre el tiempo de acceso y el espacio extra. Un
buen compromiso es tener un índice escaso con una entrada de índice por bloque.Para que esta
técnica sea completamente general, debemos considerar el caso en el que los registros para un valor
de la clave de búsqueda ocupan varios bloques. Es fácil modificar el esquema para manejar esta
situación. Aún cuando utilizamos un índice escaso, el índice puede llegar a ser demasiado grande
para un procesamiento eficiente. En la práctica, no es raro tener un archivo con 100.000 registros.
Con 10 registros por bloque. Si tenemos un registro índice por bloque, el índice tiene 10.000 registros.
Los registros índice son más pequeños que los de datos, por lo que podemos suponer que entran 100
por bloque, así pues el índice ocupa 100 bloques. Si un índice es lo bastante pequeño como para
guardarlo en memoria, el tiempo de búsqueda es corto. Sin embargo, si le índice es tan grande que
debe guardarse en disco, una búsqueda puede ser costosa. Para resolver este problema, tratamos el
índice como cualquier otro archivo secuencial, y construimos un índice escaso sobre el índice
primario, que puede almacenarse en memoria. Utilizando los dos niveles de indexación, hemos leído
únicamente un bloque de índices en vez de 100. Si suponemos que el índice externo ya está en la
memoria. Si el fichero es extremadamente grande, es posible que ni siquiera el índice exterior quepa
en memoria principal, en este caso, podemos crear otro nivel de indexación. En la práctica, lo normal
es que basten dos niveles. Frecuentemente, cada nivel de índice corresponde a una unidad de
almacenamiento físico. Así, podemos tener índices en los niveles de pista, cilindro y disco. Sin
importar cual sea la forma de índice que se utilice, se deben actualizar todos los índices cada vez que
seinserta o elimina un registro del archivo. A continuación describimos algoritmos para actualizar
índices de un sólo nivel:
Eliminación. Para eliminar un registro, es necesario buscar el registro que se va a eliminar. Si el
registro eliminado era el último que quedaba con ese valor particular de la clave de búsqueda,
entonces eliminamos el valor de la clave de búsqueda del índice. Para índices densos, eliminamos un
valor de la clave de búsqueda de la misma manera que se suprime en un archivo. Para índices
escasos, eliminamos un valor de clave sustituyendo su entrada en el índice por el siguiente valor de la
clave de búsqueda. Si el siguiente valor ya tiene una entrada de índice, eliminamos la entrada.
