DBMS - Hash

Para una estructura de base de datos enorme, puede ser casi imposible buscar todos los valores de índice en todo su nivel y luego llegar al bloque de datos de destino para recuperar los datos deseados. El hash es una técnica eficaz para calcular la ubicación directa de un registro de datos en el disco sin utilizar la estructura de índice.

El hash usa funciones hash con claves de búsqueda como parámetros para generar la dirección de un registro de datos.

Organización hash

  • Bucket- Un archivo hash almacena datos en formato de cubo. El balde se considera una unidad de almacenamiento. Un depósito suele almacenar un bloque de disco completo, que a su vez puede almacenar uno o más registros.

  • Hash Function - Una función hash, h, es una función de mapeo que mapea todo el conjunto de claves de búsqueda Ka la dirección donde se colocan los registros reales. Es una función desde claves de búsqueda hasta direcciones de depósito.

Hash estático

En el hash estático, cuando se proporciona un valor de clave de búsqueda, la función hash siempre calcula la misma dirección. Por ejemplo, si se utiliza la función hash mod-4, generará solo 5 valores. La dirección de salida siempre será la misma para esa función. El número de depósitos proporcionados permanece sin cambios en todo momento.

Operación

  • Insertion - Cuando se requiere ingresar un registro usando hash estático, la función hash h calcula la dirección del depósito para la clave de búsqueda K, donde se almacenará el registro.

    Dirección del depósito = h (K)

  • Search - Cuando es necesario recuperar un registro, se puede utilizar la misma función hash para recuperar la dirección del depósito donde se almacenan los datos.

  • Delete - Esto es simplemente una búsqueda seguida de una operación de eliminación.

Desbordamiento del cucharón

La condición de desbordamiento del cubo se conoce como collision. Este es un estado fatal para cualquier función hash estática. En este caso, se puede utilizar el encadenamiento de desbordamiento.

  • Overflow Chaining- Cuando los depósitos están llenos, se asigna un nuevo depósito para el mismo resultado de hash y se vincula después del anterior. Este mecanismo se llamaClosed Hashing.

  • Linear Probing- Cuando una función hash genera una dirección en la que los datos ya están almacenados, se le asigna el siguiente depósito libre. Este mecanismo se llamaOpen Hashing.

Hashing dinámico

El problema con el hash estático es que no se expande ni se contrae dinámicamente a medida que el tamaño de la base de datos aumenta o disminuye. El hash dinámico proporciona un mecanismo en el que los depósitos de datos se agregan y eliminan de forma dinámica y bajo demanda. El hash dinámico también se conoce comoextended hashing.

La función hash, en hash dinámico, está hecha para producir una gran cantidad de valores y inicialmente solo se usan unos pocos.

Organización

El prefijo de un valor hash completo se toma como índice hash. Solo una parte del valor hash se usa para calcular las direcciones de depósito. Cada índice hash tiene un valor de profundidad para indicar cuántos bits se utilizan para calcular una función hash. Estos bits pueden direccionar 2n cubos. Cuando se consumen todos estos bits, es decir, cuando todos los depósitos están llenos, el valor de profundidad aumenta linealmente y se asignan el doble de depósitos.

Operación

  • Querying - Mire el valor de profundidad del índice hash y use esos bits para calcular la dirección del depósito.

  • Update - Realice una consulta como arriba y actualice los datos.

  • Deletion - Realizar una consulta para localizar los datos deseados y eliminarlos.

  • Insertion - Calcular la dirección del depósito.

    • Si el cubo ya está lleno.
      • Agrega más cubos.
      • Agregue bits adicionales al valor hash.
      • Vuelva a calcular la función hash.
    • Más
      • Agrega datos al depósito,
    • Si todos los depósitos están llenos, realice las soluciones del hash estático.

El hash no es favorable cuando los datos están organizados en algún orden y las consultas requieren un rango de datos. Cuando los datos son discretos y aleatorios, el hash funciona mejor.

Los algoritmos de hash tienen una mayor complejidad que la indexación. Todas las operaciones hash se realizan en tiempo constante.