indexacion hashing


















Indexación Hashing
Un índice para un archivo del sistema funciona como el índice de un libro. Si se va a buscar un tema (especificado por una palabra o una frase) en un libro, se puede buscar en el índice al final del libro, encontrar las páginas en las que aparece y después leer esas páginas para encontrar la información que estamos buscando. Las palabras deíndice están ordenadas, lo que hace fácil la búsqueda del término que se esté buscando. Además, el índice es mucho más pequeño que el libro, con lo que se reduce aún más el esfuerzo necesario para encontrar las palabras en cuestión.
Los índices de los sistemas de bases de datos juegan el mismo papel que los índices de los libros o los catálogos de fichas de las bibliotecas. Por ejemplo, pararecuperar un registro cuenta dado su número de cuenta, el sistema de bases de datos buscaría en un índice para encontrar el bloque de disco en que se encuentra el registro correspondiente, y entonces extraería ese bloque de disco para obtener el registro cuenta. Almacenar una lista ordenada de números de cuenta no funcionaría bien en bases de datos muy grandes con millones de cuentas, ya que elpropio índice sería muy grande; más aún, incluso al mantener ordenado el índice se reduce el tiempo de búsqueda, encontrar una cuenta puede consumir mucho tiempo. En su lugar se usan técnicas más sofisticadas de indexación. Algunas de estas técnicas se discutirán más adelante. Hay dos tipos básicos de índices:
 Índices ordenados: Estos índices están basados en una disposición ordenada de los valores. Índices asociativos (hash índices): Estos índices están basados en una distribución uniforme de los valores a través de una serie de cajones (buckets). El valor asignado a cada cajón está determinado por una función, llamada función de asociación (hash function).




Cada técnica debe ser valorada según los siguientes criterios:
 Tipos de acceso. Los tipos de acceso que se soportaneficazmente. Estos tipos podrían incluir la búsqueda de registros con un valor concreto en un atributo, o buscar los registros cuyos atributos contengan valores en un rango especificado.
 Tiempo de acceso. El tiempo que se tarda en buscar un determinado elemento de datos, o conjunto de elementos, usando la técnica en cuestión.
 Tiempo de inserción. El tiempo empleado en insertar un nuevo elementode datos. Este valor incluye el tiempo utilizado en buscar el lugar apropiado donde insertar el nuevo elemento de datos, así como el tiempo empleado en actualizar la estructura del índice.
 Tiempo de borrado. El tiempo empleado en borrar un elemento de datos. Este valor incluye el tiempo utilizado en buscar el elemento a borrar, así como el tiempo empleado en actualizar la estructura del índice. Espacio adicional requerido: El espacio adicional ocupado por la estructura del índice. Como normalmente la cantidad necesaria de espacio adicional suele ser moderada, es razonable sacrificar el espacio para alcanzar un rendimiento mejor.
Índices Ordenados
Para permitir un acceso directo rápido a los registros de un archivo se puede usar una estructura de índice. Cada estructura de índiceestá asociada con una clave de búsqueda concreta. Al igual que en el catálogo de una biblioteca, un índice almacena de manera ordenada los valores de las claves de búsqueda, y asocia a cada clave los registros que contienen esa clave de búsqueda.
Índice primario
En este apartado se asume que todos los archivos están ordenados secuencialmente según alguna clave de búsqueda. Estos archivos coníndice primario según una clave de búsqueda se llaman archivos secuenciales indexados. Representan uno de los esquemas de índices más antiguos usados por los sistemas de bases de datos. Se emplean en aquellas aplicaciones que demandan un procesamiento secuencial del archivo completo así como un acceso directo a sus registros.


Hay dos clases de índices ordenados que se pueden emplear:

...