Hashing en DBMS: técnicas de hashing estáticas y dinámicas

¿Qué es el hash en DBMS?

En DBMS, el hashing es una técnica para buscar directamente la ubicación de los datos deseados en el disco sin utilizar una estructura de índice. El método hash se utiliza para indexar y recuperar elementos en una base de datos, ya que es más rápido buscar ese elemento específico usando la clave hash más corta en lugar de usar su valor original. Los datos se almacenan en forma de bloques de datos cuya dirección se genera aplicando una función hash en la ubicación de la memoria donde se almacenan estos registros conocida como bloque de datos o depósito de datos.

¿Por qué necesitamos Hashing?

Estas son las situaciones en el DBMS en las que es necesario aplicar el método Hashing:

  • Para una estructura de base de datos enorme, es difícil buscar todos los valores del índice en todo su nivel y luego es necesario llegar al bloque de datos de destino para obtener los datos deseados.
  • El método hash se utiliza para indexar y recuperar elementos en una base de datos, ya que es más rápido buscar ese elemento específico usando la clave hash más corta en lugar de usar su valor original.
  • El hash es un método ideal para calcular la ubicación directa de un registro de datos en el disco sin utilizar una estructura de índice.
  • También es una técnica útil para implementar diccionarios.

Terminologías importantes en hash

A continuación, se muestran terminologías importantes que se utilizan en Hashing:

  • depósito de datos – Los depósitos de datos son ubicaciones de memoria donde se almacenan los registros. También se le conoce como Unidad de Almacenamiento.
  • Teclado: Un clave del sistema de gestión de bases de datos es un atributo o conjunto de atributos que le ayuda a identificar una fila (tupla) en una relación (tabla). Esto le permite encontrar la relación entre dos tablas.
  • Función hash: Una función hash es una función de mapeo que asigna todo el conjunto de claves de búsqueda a la dirección donde se colocan los registros reales.
  • Palpado lineal – El sondeo lineal es un intervalo fijo entre sondeos. En este método, se utiliza el siguiente bloque de datos disponible para ingresar el nuevo registro, en lugar de sobrescribir el registro anterior.
  • Sondeo cuadrático– Le ayuda a determinar la nueva dirección del depósito. Le ayuda a agregar intervalo entre sondas agregando la salida consecutiva del polinomio cuadrático al valor inicial dado por el cálculo original.
  • Índice hash – Es una dirección del bloque de datos. Una función hash podría ser una función matemática simple incluso para una com.plex función matemática.
  • Double Hashing –Double El hash es un método de programación informática que se utiliza en tablas hash para resolver problemas de colisión.
  • Desbordamiento del cucharón: La condición de desbordamiento del depósito se llama colisión. Esta es una etapa fatal para que cualquier estática tenga que funcionar.

Tipos de técnicas de hashing

Existen principalmente dos tipos de métodos/técnicas de hashing SQL:

  1. Hash estático
  2. Hashing dinámico

hash estático

En el hash estático, la dirección del depósito de datos resultante siempre será la misma.

Por lo tanto, si genera una dirección para decir ID_estudiante = 10 usando la función hash mod(3), la dirección del depósito resultante siempre será 1. Por lo tanto, no verá ningún cambio en la dirección del depósito.

Por lo tanto, en este método de hash estático, la cantidad de depósitos de datos en la memoria siempre permanece constante.

Funciones hash estáticas

  • Insertar un registro: Cuando es necesario insertar un nuevo registro en la tabla, puede generar una dirección para el nuevo registro utilizando su clave hash. Cuando se genera la dirección, el registro se almacena automáticamente en esa ubicación.
  • Searching: Cuando necesite recuperar el registro, la misma función hash debería ser útil para recuperar la dirección del depósito donde se deben almacenar los datos.
  • Eliminar un registro: Usando la función hash, primero puede recuperar el registro que desea eliminar. Luego puede eliminar los registros de esa dirección en la memoria.

El hash estático se divide a su vez en

  1. hash abierto
  2. Cerrar hash.

Hashing abierto

En el método de hash abierto, en lugar de sobrescribir el anterior, se utiliza el siguiente bloque de datos disponible para ingresar el nuevo registro. Este método también se conoce como sondeo lineal.

Por ejemplo, A2 es un registro nuevo que desea insertar. La función hash genera la dirección 222. Pero ya está ocupada por algún otro valor. Es por eso que el sistema busca el siguiente depósito de datos 501 y le asigna A2.

Hashing abierto
Cómo funciona el hash abierto

Cerrar hash

En el método de hash de cierre, cuando los depósitos están llenos, se asigna un nuevo depósito para el mismo hash y el resultado se vincula después del anterior.

Hashing dinámico

El hashing dinámico ofrece un mecanismo en el que los depósitos de datos se agregan y eliminan de forma dinámica y bajo demanda. En este hash, la función hash le ayuda a crear una gran cantidad de valores.

Diferencia entre indexación ordenada y hash

A continuación se detallan las diferencias clave entre indexación y hash.

parámetros Indexación de pedidos Hashing
Almacenamiento de dirección Las direcciones en la memoria se ordenan según un valor de clave llamado clave primaria. Las direcciones siempre se generan utilizando una función hash en el valor clave.
Rendimiento Puede disminuir cuando los datos aumentan en el archivo hash. Ya que almacena los datos en forma ordenada cuando se realiza alguna operación (insertar/eliminar/actualizar) que disminuye su rendimiento. El rendimiento del hash será mejor cuando se agreguen y eliminen datos constantemente. Sin embargo, cuando la base de datos es enorme, la organización del archivo hash y su mantenimiento serán más costosos.
Uso Preferido para la recuperación de datos de rango, lo que significa que siempre que haya datos de recuperación para un rango en particular, este método es una opción ideal. Este es un método ideal cuando desea recuperar un registro particular según la clave de búsqueda. Sin embargo, sólo funcionará bien cuando la función hash esté en la clave de búsqueda.
Gestión de la memoria Habrá muchos bloques de datos no utilizados debido a la operación de eliminación/actualización. Estos bloques de datos no se pueden liberar para su reutilización. Por eso es necesario un mantenimiento regular de la memoria. En los métodos hash estáticos y dinámicos, la memoria siempre se gestiona. El desbordamiento del depósito también se maneja perfectamente para extender el hash estático.

¿Qué es una colisión?

La colisión de hash es un estado en el que los hash resultantes de dos o más datos en el conjunto de datos asignan erróneamente el mismo lugar en el tabla de picadillo.

¿Cómo lidiar con la colisión de hash?

Hay dos técnicas que puedes utilizar para evitar una colisión de hash:

  1. Refrito: Este método invoca una función hash secundaria, que se aplica continuamente hasta que se encuentra una ranura vacía, donde se debe colocar un registro.
  2. Encadenamiento: El método de encadenamiento crea una lista vinculada de elementos cuya clave tiene el mismo valor. Este método requiere un campo de enlace adicional para cada posición de la tabla.

Resumen

  • In DBMS, el hash es una técnica para buscar directamente la ubicación de los datos deseados en el disco sin utilizar una estructura de índice.
  • El método hash se utiliza para indexar y recuperar elementos en una base de datos, ya que es más rápido buscar ese elemento específico usando la clave hash más corta en lugar de usar su valor original.
  • Depósito de datos, clave, función hash, sondeo lineal, sondeo cuadrático, índice hash, Double Hashing y Bucket Overflow son terminologías importantes utilizadas en hash
  • Dos tipos de métodos de hash son 1) hash estático 2) hash dinámico
  • En el hash estático, la dirección del depósito de datos resultante siempre será la misma.
  • El hashing dinámico ofrece un mecanismo en el que los depósitos de datos se agregan y eliminan de forma dinámica y bajo demanda.
  • En orden, las direcciones de indexación en la memoria se ordenan de acuerdo con un valor crítico, mientras que en el hash, las direcciones siempre se generan utilizando una función hash en el valor clave.
  • La colisión de hash es un estado en el que los hash resultantes de dos o más datos en el conjunto de datos asignan erróneamente el mismo lugar en la tabla hash.
  • El refrito y el encadenamiento son dos métodos que le ayudan a evitar colisiones de hash.