Hashing en DBMS: técnicas de hashing estáticas y dinámicas
Equipo editorial
⚡ Resumen inteligente
El hashing en los sistemas de gestión de bases de datos (DBMS) es una técnica que calcula la ubicación en disco de un registro directamente a partir de su clave, sin necesidad de recorrer un índice. Una función hash asigna claves de búsqueda a depósitos de datos, y el hashing estático o dinámico gestiona el crecimiento de dichos depósitos.
¿Qué es el hash en DBMS?
En los sistemas de gestión de bases de datos (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 de hashing se utiliza para indexar y recuperar elementos en una base de datos, ya que es más rápido buscar un elemento específico utilizando la clave hash más corta en lugar de su valor original. Los datos se almacenan en forma de bloques de datos cuya dirección se genera aplicando una función hash; la ubicación de memoria donde se almacenan estos registros se conoce como bloque de datos o depósito de datos.
¿Por qué necesitamos el hash?
Estas son las situaciones en un sistema de gestión de bases de datos (DBMS) en las que es necesario aplicar el método de hash:
- Para una estructura de base de datos enorme, es difícil buscar todos los valores del índice a través de todos sus niveles y luego llegar al bloque de datos de destino para obtener los datos deseados.
- El hashing se utiliza para indexar y recuperar elementos en una base de datos, ya que es más rápido buscar un elemento específico utilizando la clave hash más corta que el valor original.
- El hashing 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 presentan términos importantes utilizados en el hashing:
- Cubo de datos: Los depósitos de datos son ubicaciones de memoria donde se almacenan los registros. También se conocen como unidades de almacenamiento.
- Llave: a 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).
- Función hash: un mapaping Función que asigna todas las claves de búsqueda a la dirección donde se encuentran los registros reales.
- Sondeo lineal: un intervalo fijo entre sondeos. En este método, se utiliza el siguiente bloque de datos disponible para introducir el nuevo registro, en lugar de sobrescribir el anterior.
- Sondeo cuadrático: Ayuda a determinar la nueva dirección del bucket sumando la salida consecutiva de un polinomio cuadrático al valor inicial dado por el cálculo original.
- Índice hash: la dirección del bloque de datos. Una función hash puede ser una función matemática simple o una compleja.
- Double hash: un método utilizado en tablas hash para resolver colisiones aplicando una segunda función hash.
- Desbordamiento del cubo: La condición de desbordamiento del bucket se denomina colisión. Esta es una etapa fatal para cualquier función hash estática.
Tipos de técnicas de hashing
En los sistemas de gestión de bases de datos (DBMS) existen principalmente dos tipos de técnicas de hash:
- Hash estático
- Hashing dinámico
La principal diferencia entre ambos radica en si el número de cubetas es fijo, como se explica en las dos secciones siguientes.
Hash estático
En el hash estático, la dirección del bucket de datos resultante siempre permanecerá igual.
Por lo tanto, si genera una dirección para, digamos, ID_estudiante = 10 utilizando 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 bucket.
Por lo tanto, en el método de hash estático, el número de cubetas de datos en memoria siempre permanece constante.
Funciones hash estáticas
- Insertar un registro: Cuando se necesita insertar un nuevo registro en la tabla, se genera una dirección para él utilizando su clave hash. Una vez generada la dirección, el registro se almacena en esa ubicación.
- Buscando: Cuando necesite recuperar el registro, se utilizará la misma función hash para recuperar la dirección del depósito donde se almacenan los datos.
- Eliminar un registro: Utilizando la función hash, primero se obtiene el registro que se desea eliminar y, a continuación, se elimina dicho registro de la dirección de memoria correspondiente.
El hash estático se divide además en:
- hash abierto
- Hashing cerrado
Hashing abierto
En el método de hash abierto, en lugar de sobrescribir el registro anterior, se utiliza el siguiente bloque de datos disponible para introducir el nuevo registro. Este método también se conoce como sondeo lineal.
Por ejemplo, A2 es un nuevo registro que se desea insertar. La función hash genera la dirección 222, pero esta ya está ocupada por otro valor. Por eso, el sistema busca el siguiente segmento de datos, el 501, y le asigna A2.
Hashing cerrado
En el método de hash cerrado, cuando los depósitos están llenos, se asigna un nuevo depósito para el mismo hash y el resultado se enlaza después del anterior.
Hashing dinámico
El hash dinámico ofrece un mecanismo en el que se añaden y eliminan cubos de datos de forma dinámica y bajo demanda. En este método, la función hash ayuda a crear un gran número de valores, y la estructura crece o se reduce con los datos. Esto lo convierte en una opción ideal para tablas cuyo tamaño no se puede predecir de antemano, donde el hash estático desperdiciaría espacio o provocaría un desbordamiento.
Diferencia entre indexación ordenada y hash
A continuación se detallan las principales diferencias entre la indexación y el hashing:
| Parámetros | Indexación ordenada | Hashing |
|---|---|---|
| Almacenamiento de dirección | Las direcciones en la memoria se ordenan según un valor clave llamado clave primaria. | Las direcciones siempre se generan utilizando una función hash en el valor clave. |
| Rendimiento | Puede disminuir a medida que aumentan los datos, porque los datos se almacenan ordenados y cada inserción, eliminación o actualización los reordena. | El rendimiento es óptimo con la adición y eliminación constante de datos. Para bases de datos muy grandes, el mantenimiento del archivo hash resulta más costoso. |
| Uso | Preferible para la recuperación de rangos, donde se recuperan datos para un rango específico. | Ideal para recuperar un registro específico en función de la clave de búsqueda, y solo funciona correctamente cuando la función hash se aplica a la clave de búsqueda. |
| Gestión de la memoria | Muchos bloques de datos no utilizados surgen de las operaciones de eliminación y actualización y no se pueden liberar para su reutilización, por lo que se requiere un mantenimiento regular. | En el hash estático y dinámico, la memoria siempre se gestiona y el desbordamiento de los buckets se controla para extender el hash estático. |
En resumen, elija ordenado indexación para consultas de rango y hash para búsquedas de coincidencia exacta en la clave.
¿Qué es una colisión?
Una colisión de hash es un estado en el que los hashes resultantes de dos o más elementos en el conjunto de datos se asignan erróneamente al mismo lugar en el tabla de picadillo.
Cómo lidiar con una colisión de hash
Existen dos técnicas que puedes utilizar para evitar una colisión de hash:
- Retomando: Este método invoca una función hash secundaria, que se aplica de forma continua hasta que se encuentra un espacio vacío donde se pueda colocar un registro.
- Encadenamiento: El método de encadenamiento crea una lista enlazada de elementos cuyas claves tienen el mismo valor hash. Este método requiere un campo de enlace adicional en cada posición de la tabla.
