Indices asociativos

Índices asociativos
Bases de datos II
Universidad del Cauca
Ing. Wilson Ortega

Introducción
Asociación estática:
 Un inconveniente de la organización de archivos secuenciales es que hay queacceder a una estructura de índices para localizar los datos o utilizar una
búsqueda binaria y, como resultado, más operaciones de E/S. La organización de
archivos basada en la técnica de asociación(hashing) permite evitar el acceso a
la estructura de índice
Organización de archivos por asociación
 En una organización de archivos por asociación se obtiene la dirección del
bloque de disco quecontiene el registro deseado mediante el cálculo directo de
una función sobre el valor de la clave búsqueda del registro
Se usa el término cajón (bucket) para indicar una unidad de almacenamiento que

puedeguardar uno o más registros. Un cajón es normalmente un bloque de disco.
Formalmente, sea K el conjunto de todos los valores de clave de búsqueda y sea B

el conjunto de todas las direcciones decajón. Una función de asociación h es
una función de K a B. Sea h una función asociación.

Funciones de asociación
La peor función posible de asociación asigna todos los valores de la clave de búsquedaal mismo cajón.
Una función de asociación ideal distribuye las claves almacenadas uniformemente a

través de los cajones para que cada uno de ellos tenga el mismo número de registros
Lo ideal estener una función de asociación que permita:
 Distribución uniforme: Cada cajón tiene asignado el mismo número de valores de la clave
de búsqueda dentro del conjunto de todos los valores posibles de laclave de búsqueda.


Distribución aleatoria: En el caso promedio, cada cajón tendrá casi el mismo número de
valores asignados a él, sin tener en cuenta la distribución actual de los valores de laclave de
búsqueda

Las funciones de asociación típicas realizan cálculos sobre la representación binaria

interna de la máquina para los caracteres de la clave de búsqueda.
Una función bien...