Indexación de bases de datos en pocas palabras con B+tree y Hash en comparación

A menudo se dice que la indexación es una técnica de referencia para procesar consultas de manera eficiente en caso de que su base de datos sea lo suficientemente grande. Esta publicación es para resumir qué es el índice de la base de datos y revisar hash y B+Tree.

El índice es una estructura de datos que organiza registros para optimizar ciertos tipos de operaciones de recuperación. Podemos crear un índice en un campo de la tabla y luego recuperar todos los registros que satisfagan las condiciones de búsqueda en search-key campo. Sin índice, nuestra consulta terminaría escaneando linealmente todo el contenido de la tabla para obtener solo uno o unos pocos registros.

En esta publicación, me gustaría resumir el rendimiento y los casos de uso de dos técnicas de indexación comunes:Índice hash y B+árbol

Índice hash

Esta técnica es ampliamente utilizada para crear índices en memoria principal porque su rápida recuperación por naturaleza. Tiene una complejidad de operación promedio O(1) y una complejidad de almacenamiento O(n).
En muchos libros, la gente usa el término bucket para denotar una unidad de almacenamiento que almacena uno o más registros
Hay dos cosas a discutir cuando se trata de hash:

• Función hash:asigna claves de búsqueda (como su entrada) a un número entero que representa esa clave en el depósito.
• Esquema hash:cómo lidiar con la colisión de claves después del hashing.

Algunas personas preguntan:¿por qué colisión? ¿Existe alguna vez una función hash perfecta? De hecho, digamos que sus claves son un conjunto infinito, es imposible mapearlas en un conjunto de enteros de 32 bits sin colisión. Debería haber una compensación entre el cálculo y la tasa de colisión.

Hay algunos esquemas de hash que vale la pena mencionar:sondeo lineal, hash encadenado y hash extensible. Los algoritmos de búsqueda/inserción/eliminación varían según el esquema de hash, por ejemplo, el hash encadenado se ocupa de las colisiones de claves al colocar elementos que tienen el mismo valor de hash en el mismo depósito.

Ventajas

• El índice hash es adecuado para la igualdad o la búsqueda de clave principal. Las consultas pueden beneficiarse del índice hash para amortizar el costo de búsqueda de O(1). Por ejemplo:SELECT name, id FROM student WHERE id = '1315';

Contras

La tabla hash tiene algunas limitaciones:

• Las consultas de rango no son eficientes. La tabla hash se basa en una distribución uniforme. En otras palabras, no tiene control sobre dónde se colocará una entrada de índice.
• Baja escalabilidad:el rendimiento de la operación de búsqueda puede degradarse cuando hay muchas colisiones y es necesario cambiar el tamaño de la tabla hash y luego rehacer las entradas de índice existentes.

B+Árbol

Se trata de una estructura de datos de árbol autoequilibrada que mantiene los datos ordenados y permite una búsqueda rápida dentro de cada nodo, normalmente mediante la búsqueda binaria.
B+Tree es una implementación de índice estándar en casi todos los sistemas de bases de datos relacionales.

B+Tree es básicamente un árbol de búsqueda M-way que tiene la siguiente estructura:

• equilibrio perfecto:los nudos de las hojas siempre tienen la misma altura.
• todos los nodos internos que no sean la raíz están al menos medio llenos (M/2 − 1 <=número de claves <=M − 1).
• cada nodo interno con k claves tiene k+1 hijos no nulos.

Cada nodo del árbol tiene una matriz de pares clave-valor ordenados. El par clave-valor se construye a partir de (valor de clave de búsqueda, puntero) para los nodos raíz e interno. Los valores de los nodos hoja pueden tener 2 posibilidades:

• el registro real
• el puntero al registro real

Buscar un valor v

• Empezar con el nodo raíz
• Si bien el nodo no es un nodo hoja, sí:
  • Encuentre el Ki más pequeño donde Ki>=v
  • Si Ki ==v:establecer el nodo actual en el nodo apuntado por Pi+1
  • De lo contrario, establezca el nodo actual en el nodo apuntado por Pi

Duplicado de llaves

En general, la clave de búsqueda puede estar duplicada, para resolver esto, la mayoría de las implementaciones de bases de datos presentan una clave de búsqueda compuesta. Por ejemplo, queremos crear un índice en student_name entonces nuestra clave de búsqueda compuesta debería ser (student_name, Ap) donde Ap es la clave principal de la tabla.

Ventajas

Hay dos funciones principales que ofrece B+tree:

• Minimización de operaciones de E/S
  • Altura reducida:B+Tree tiene un factor de ramificación bastante grande (se usa a menudo un valor entre 50 y 2000) que hace que el árbol sea gordo y bajo. La siguiente figura ilustra un árbol B+ con una altura de 2. Como podemos ver, los nodos están dispersos, se necesitan menos nodos para atravesar hasta una hoja. El costo de buscar un solo valor es la altura del árbol + 1 para el acceso aleatorio a la tabla.
• Escalabilidad:
  • Tiene un rendimiento predecible para todos los casos, O(log(n)) en particular. Para las bases de datos, por lo general es más importante que tener un mejor rendimiento de casos mejor o promedio.
  • El árbol siempre permanece equilibrado por su implementación. Un B+Tree con n claves siempre tiene una profundidad de O(log(n)). Por lo tanto, el rendimiento no se degradará si la base de datos crece. Un árbol de cuatro niveles con un factor de ramificación de 500 puede almacenar hasta 256 TB siempre que una página tenga un tamaño de 4 KB.

• B+Tree es más adecuado para consultas de rango, por ejemplo "SELECT * FROM student WHERE age > 20 AND age < 22"

Conclusión

Aunque el índice hash funciona mejor en términos de consultas de coincidencia exacta, se puede decir que B+Tree es la estructura de índice más utilizada en RDBMS gracias a su rendimiento constante en escalabilidad general y alta.

Recientemente, el árbol de combinación con estructura de registro (LSM-tree) ha atraído un gran interés como competidor del árbol B+, porque su estructura de datos podría permitir una mejor eficiencia en el uso del espacio de almacenamiento. Lo investigaré más a fondo y haré una publicación al respecto en un futuro cercano.