Hashing extensible (enfoque dinámico de DBMS)

Hashing extensible es un método hash dinámico en el que se utilizan directorios y cubos para cifrar datos. Es un método agresivamente flexible en el que la función hash también experimenta cambios dinámicos. 

Principales características de Extendible Hashing : Las principales características de esta técnica de hashing son: 

• Directorios: Los directorios almacenan las direcciones de los cubos en punteros. Se asigna una identificación a cada directorio que puede cambiar cada vez que se lleva a cabo la expansión del directorio.
• Cubos: los cubos se utilizan para codificar los datos reales.

Estructura básica de hashing extensible : 
 

Términos de uso frecuente en Extendible Hashing : 
 

• Directorios: estos contenedores almacenan punteros a cubos. Cada directorio recibe una identificación única que puede cambiar cada vez que se lleva a cabo la expansión. La función hash devuelve esta identificación de directorio que se usa para navegar al depósito apropiado. Número de directorios = 2^Profundidad global.
• Cubos: Almacenan las claves hash. Los directorios apuntan a cubos. Un depósito puede contener más de un indicador si su profundidad local es menor que la profundidad global.
• Profundidad Global: Se asocia a los Directorios. Denotan el número de bits que utiliza la función hash para categorizar las claves. Profundidad global = Número de bits en la identificación del directorio.
• Profundidad Local: Es igual que la Profundidad Global excepto que la Profundidad Local está asociada a los cubos y no a los directorios. La profundidad local de acuerdo con la profundidad global se utiliza para decidir la acción a realizar en caso de que se produzca un desbordamiento. La profundidad local siempre es menor o igual que la profundidad global.
• División del depósito : cuando el número de elementos en un depósito supera un tamaño determinado, el depósito se divide en dos partes.
• Expansión de directorio: La expansión de directorio tiene lugar cuando se desborda un depósito. La expansión de directorio se realiza cuando la profundidad local del cubo desbordado es igual a la profundidad global.

Funcionamiento básico de hashing extensible : 
 

• Paso 1: analizar los elementos de datos: los elementos de datos pueden existir en varias formas, por ejemplo. Entero, String, Flotante, etc. Actualmente, consideremos elementos de datos de tipo entero. por ejemplo: 49.
• Paso 2: convertir a formato binario: convertir el elemento de datos en formato binario. Para los elementos de string, considere el entero equivalente ASCII del carácter inicial y luego convierta el entero en forma binaria. Dado que tenemos 49 como nuestro elemento de datos, su forma binaria es 110001.
• Paso 3: compruebe la profundidad global del directorio. Suponga que la profundidad global del directorio Hash es 3.
• Paso 4: identifique el directorio: considere el número de LSB de ‘profundidad global’ en el número binario y conéctelo con la identificación del directorio. 
  P.ej. El binario obtenido es: 110001 y la profundidad global es 3. Entonces, la función hash devolverá 3 LSB de 110 001 a saber. 001.
• Paso 5 – Navegación: Ahora, navegue hasta el depósito señalado por el directorio con ID de directorio 001.
• Paso 6 – Comprobación de inserción y desbordamiento: inserte el elemento y compruebe si el cubo se desborda. Si se encuentra un desbordamiento, vaya al paso 7 seguido del paso 8 , de lo contrario, vaya al paso 9 .
• Paso 7: abordar la condición de desbordamiento durante la inserción de datos: muchas veces, al insertar datos en los cubos, puede suceder que el cubo se desborde. En tales casos, debemos seguir un procedimiento adecuado para evitar el mal manejo de los datos. 
  Primero, compruebe si la profundidad local es menor o igual que la profundidad global. A continuación, elija uno de los casos a continuación. 
  • Caso 1: si la profundidad local del depósito desbordado es igual a la profundidad global, entonces se debe realizar la expansión del directorio, así como la división del depósito. Luego incremente la profundidad global y el valor de profundidad local en 1. Y asigne los punteros apropiados. 
    La expansión de directorios duplicará el número de directorios presentes en la estructura hash.
  • Caso 2: en caso de que la profundidad local sea menor que la profundidad global, solo se lleva a cabo la división del cubo. Luego incremente solo el valor de profundidad local en 1. Y asigne los punteros apropiados. 
     

• Paso 8: refrito de los elementos del cubo dividido: los elementos presentes en el cubo desbordado que se divide se repiten con la nueva profundidad global del directorio.
• Paso 9: el elemento se codifica con éxito.

Ejemplo basado en hashing extensible: ahora, consideremos un ejemplo destacado de hashing de los siguientes elementos: 16,4,6,22,24,10,31,7,9,20,26.  
Tamaño del cubo: 3 (suponga) 
Función hash: suponga que la profundidad global es X. Luego, la función hash devuelve X LSB. 
 

• Solución: Primero, calcula las formas binarias de cada uno de los números dados. 
  16- 10000 
  4- 00100 
  6- 00110 
  22- 10110 
  24- 11000 
  10- 01010 
  31- 11111 
  7- 00111 
  9- 01001 
  20- 10100 
  26- 11010
• Inicialmente, la profundidad global y la profundidad local siempre son 1. Por lo tanto, el marco hash se ve así: 
   

• Inserción de 16: 
  el formato binario de 16 es 10000 y la profundidad global es 1. La función hash devuelve 1 LSB de 1000 0 , que es 0. Por lo tanto, 16 se asigna al directorio con id=0. 
   

• Insertando 4 y 6: 
  Tanto 4(10 0 ) como 6(11 0 ) tienen 0 en su LSB. Por lo tanto, se codifican de la siguiente manera: 
   

• Insertando 22: La forma binaria de 22 es 1011 0 . Su LSB es 0. El depósito al que apunta el directorio 0 ya está lleno. Por lo tanto, se produce Over Flow. 
   

• Como se indica en el Paso 7-Caso 1 , dado que Profundidad local = Profundidad global, la cubeta se divide y se produce la expansión del directorio. Además, el refrito de los números presentes en el cubo desbordado se lleva a cabo después de la división. Y, dado que la profundidad global se incrementa en 1, ahora la profundidad global es 2. Por lo tanto, 16,4,6,22 ahora se repiten con 2 LSB.[ 16(100 00 ),4(1 00 ),6( 1 10 ),22(101 10 ) ] 

   

•  

*Observe que el balde que se desbordó no se ha tocado. Pero, dado que la cantidad de directorios se ha duplicado, ahora tenemos 2 directorios 01 y 11 que apuntan al mismo contenedor. Esto se debe a que la profundidad local del cubo se ha mantenido en 1. Y, cualquier cubo que tenga una profundidad local menor que la profundidad global es señalado por más de un directorio.

• Insertar 24 y 10: 24 (110 00 ) y 10 (10 10 ) se pueden codificar según los directorios con id 00 y 10. Aquí, no encontramos una condición de desbordamiento. 
   

• Insertar 31,7,9: Todos estos elementos [ 31(111 11 ), 7(1 11 ), 9(10 01 ) ] tienen 01 u 11 en sus LSB. Por lo tanto, están mapeados en el balde señalado por 01 y 11. Aquí no encontramos ninguna condición de desbordamiento. 
   

• Inserción de 20: la inserción del elemento de datos 20 (101 00 ) volverá a provocar el problema de desbordamiento. 
   

• 20 se inserta en el depósito señalado por 00. Como se indica en el Paso 7-Caso 1 , dado que la profundidad local del depósito = profundidad global , la expansión del directorio (duplicación) se lleva a cabo junto con la división del depósito. Los elementos presentes en el cubo desbordante se repiten con la nueva profundidad global. Ahora, la nueva tabla Hash se ve así: 
   

• Insertando 26: la profundidad global es 3. Por lo tanto, se consideran 3 LSB de 26 (11 010 ). Por lo tanto, 26 encaja mejor en el cubo señalado por el directorio 010. 
   

• El cubo se desborda y, como se indica en el Paso 7-Caso 2, dado que la profundidad local del cubo < Profundidad global (2<3) , los directorios no se duplican, sino que solo se divide el cubo y se repiten los elementos. 
  Finalmente, se obtiene el resultado del hash de la lista de números dada. 

   

• El hashing de 11 números está así completado.

Observaciones clave: 
 

1. Un Cubo tendrá más de un puntero apuntándolo si su profundidad local es menor que la profundidad global.
2. Cuando se produce una condición de desbordamiento en una cubeta, todas las entradas de la cubeta se repiten con una nueva profundidad local.
3. Si profundidad local del balde desbordante
4. El tamaño de un depósito no se puede cambiar una vez que comienza el proceso de inserción de datos.

ventajas: 
 

1. La recuperación de datos es menos costosa (en términos de computación).
2. No hay problema de pérdida de datos ya que la capacidad de almacenamiento aumenta dinámicamente.
3. Con cambios dinámicos en la función hash, los valores antiguos asociados se repiten con la nueva función hash.

Limitaciones del hashing extensible: 
 

1. El tamaño del directorio puede aumentar significativamente si se codifican varios registros en el mismo directorio mientras se mantiene la distribución de registros no uniforme.
2. El tamaño de cada cubeta es fijo.
3. La memoria se desperdicia en punteros cuando la diferencia entre la profundidad global y la profundidad local se vuelve drástica.
4. Este método es complicado de codificar.

Estructuras de datos utilizadas para la implementación:  

1. Árboles B+
2. Formación
3. Lista enlazada