Direccionamiento directo e indirecto

El direccionamiento de dos registros puede darse en forma directa e indirecta. Se dice que es directa cuando es posible determinar la dirección mediante una relación natural con la llave. Es indirecta cuando la llave debe ser alterada o se le deben de aplicar operaciones para determinar la dirección del registro.

Un método ampliamente utilizado para generar direcciones físicas de los registros es aquel que realiza una descomposición de la llave y aplica a cada fragmento o a estos en su conjunto una serie de operaciones que darán como resultado un numero relativamente grande (en proporción al tamaño del archivo sumado) y del cual será generado un numero en un intervalo determinado, el cual se utilizara como dirección en el esqueleto, Este método es mejor conocido como Hashing.

Existen diversas formas de generar el numero final a partir del numero «grande», las mas utilizadas son:

Método del residuo

Es el de mayor aceptación y consiste en la determinación de un numero primo (inmediatamente menor al total de registros esperados) que será utilizado como divisor del numero grande. El residuo de esta división será el numero hash buscado.

Método del centro de los cuadrados

Consiste en obtener el cuadrado del numero «grande»; del valor resultante se rescatan los dígitos centrales tantos como se requieran para direccionar el esqueleto y se multiplican por un factor de ajuste para colocar el resultado en el rango deseado.

Método del desplazamiento

En este caso se consideran los dígitos mas externos del numero «grande». De cada extremo se toman tantos dígitos como se requieran para el direccionamiento. Estos se suman y se aplica un factor de ajuste.

Método del plegado

Es similar al anterior salvo que los dígitos de los extremos se suman en forma encontrada, semejando que el numero total se encontrara escrito en una hoja y esta fuera doblada por la mitad.

Método de conversión de base

Se asume que el numero «grande» se encuentra en una base determinada diferente de 10 al suprimirle los dígitos fuera de base. El valor resultante es convertido a base 10 y se le aplica el factor de ajuste. Tomar los tres últimos dígitos.

Método del análisis de dígitos

Se obtiene una muestra de gran tamaño de llaves posibles y sus números hash correspondientes, se analiza la frecuencia de repetición para cada una de las columnas y se van descartando aquellos que presentan mayor repetición. Finalmente, se toman las columnas con mayor variación y tantas como dígitos se requieren. Se aplica factor de ajuste.

Una vez que se ha determinado la dirección hash por cualquiera de los métodos anteriores, se implementara sobre una estructura que soporte tal direccionamiento. Estos pueden ser:

Esqueleto con desborde

Archivo Intermedio para direccionamiento

Como puede verse, el modelo del Redireccionamiento ofrece la ventaja de que el desperdicio provocado por una distribución inadecuada en el esqueleto no afecta al archivo principal; para este modelo se afecta al archivo de Redireccionamiento donde el tamaño de los registros es mucho menor y el archivo principal crece conforma ocurren el arribo de los registros.