Dispersión de Registros - Archivos de Acceso Directo Organización de Datos Curso Servetto

Dispersión de Registros - Archivos de
Acceso Directo
Organización de Datos
Curso Servetto

Antecedentes
 Costos promedio de acceso en un archivo de N (p.e. 10.000)

registros:
 Secuencial desordenado: N/2 (p.e. 5.000)
 Secuencial ordenado: log2N (p.e. 12)
 Árboles balanceados de orden d (carga promedio de nodos

2/3*d-1): menos de log3/4*d(N/(3/4*d-1)) (p.e. para
d=16,menos de 3)

 ¿Es posible reducir aún más el costo de acceso?
 ¿Y si se prueba con una función de mapeo de claves de

registros a direcciones?
2

Dispersión de Registros

OAA

Dispersión (hashing)
 Técnica para generar una dirección base única para una clave

dada. La dispersión se usa cuando se requiere acceso rápido a
un registro.

 Técnica que convierte la clave delregistro en un número

aleatorio, el que sirve después para determinar dónde se
almacena el registro.

 Técnica de almacenamiento y recuperación que usa una función

de hash para mapear registros en direcciones de
almacenamiento.

3

Dispersión de Registros

OAA

Organización de Registros
•

Para registros de longitud fija se pueden usar bloques con capacidad para
uno o muchosregistros
– Un registro: ranura (slot)‫‏‬o compartimiento individual. Cuando se intenta

insertar un nuevo registro en una ranura ocupada se produce una colisión.
– Muchos registros: cubeta (bucket)‫‏‬o compartimiento múltiple. Cuando se intenta
insertar un nuevo registro en una ranura que está llena se produce un desborde.

Para registros de longitud variable se deben usar cubetas con capacidadpara
varios registros para evitar la fragmentación interna.
• Las ranuras deben tener un campo de control que indique si tienen
contenido válido cuando se acceden.
• Las cubetas deben tener un campo de control que indique la cantidad de
registros que contienen, si son para registros de longitud fija, o el espacio
libre que les queda, si son para registros de longitud variable
•

4Dispersión de Registros

OAA

Funciones de Dispersión
• Transforman la clave de un registro en una dirección de ranura (sólo

registros de longitud fija) o en una dirección de cubeta (registros de
longitud fija o variable)‫‏‬
• Pueden transformar claves distintas en una misma dirección:
sinónimos
• Para claves alfanuméricas deben transformar los caracteres a un
número, y luego calcularel resto de dividir al número entre la
cantidad total de unidades del archivo (usualmente se aplican
transformaciones a los valores ASCII de todos o algunos de los
caracteres)
• Para claves numéricas pueden aplicar una transformación para
aleatorizar resultados y luego calcular el resto de la división entre la
cantidad total de unidades del archivo
5

Dispersión de Registros

OAAFunciones de Dispersión
 Resto de División o Módulo: la

clave se divide entre el número de
direcciones (debe tratarse de que sea
número primo, pues tiende a distribuir
residuos en forma más eficiente)
 Centros cuadrados: la clave se
multiplica por si misma y se toman los
dígitos centrales del resultado;
posteriormente se ajusta al espacio
disponible
 Desplazamiento y suma: los dígitosexternos de ambos extremos se corren
hacia adentro, se suman y se ajusta al
espacio disponible
 Plegado y suma: los dígitos externos
se pliegan y suman y el resultado se
ajusta al espacio de direcciones

6

Dispersión de Registros

 Análisis de dígitos: se obtiene un

número a ajustar a las direcciones
disponibles seleccionando dígitos de la
clave original en posiciones donde noaparezcan repeticiones.
 Conversión de base: la base del
número se modifica y en la serie de
dígitos resultante se reemplazan dígitos
no decimales por su equivalente
decimal. Ej: para direcciones entre 0 y
99, se ingresa la clave 757:
(757)10=(2E5)16; 2145 mod 100= 45
 División polinómica: cada dígito de
la clave se toma como coeficiente de un
polinomio, que se divide por un...