¿Cómo funcionan realmente los índices B-tree y hash, y por qué eso determina qué consultas aceleran?
Un índice hash y un B-tree responden ambos "¿dónde está esta fila?", pero su forma interna decide, con certeza matemática, qué consultas puede acelerar cada uno y cuáles no.
APRENDE HACIENDOPon a prueba tu intuición3 pasos
¿Cómo funcionan realmente los índices B-tree y hash, y por qué eso determina qué consultas aceleran?
Usa los ejemplos y la explicación de la lección para comprobar tu idea.
Reflexión personal. No se envía a ningún servicio de IA.#Por qué existen los índices, y por qué importa la estructura de datos elegida
Todo índice existe para responder una pregunta más rápido que recorriendo cada fila: "¿dónde están los datos que busco?" Sin un índice, la base de datos tiene exactamente una opción — un escaneo completo de la tabla, comprobando cada fila contra tu predicado, con un costo que crece linealmente con el tamaño de la tabla. Un índice cambia algo de sobrecarga en escritura y almacenamiento por una búsqueda que escala mucho mejor que lineal. Pero qué estructura de datos hay detrás de ese índice determina exactamente qué tipos de consultas se aceleran y cuáles no — y esa es la parte que la mayoría de los candidatos pasa por alto.
Las dos estructuras que aparecen constantemente en entrevistas son el B-tree (específicamente la variante B+tree que usan casi todas las bases de datos relacionales reales) y el índice hash. Ambas resuelven el mismo problema general — búsqueda rápida por clave — con formas internas completamente distintas, y esas formas tienen consecuencias directas y demostrables sobre qué consultas SQL pueden acelerar.
#Índices hash: búsqueda O(1) en promedio, y nada más
Un índice hash pasa el valor indexado por una función hash para calcular un bucket, y guarda en ese bucket un puntero a la fila (o la fila misma, en algunos diseños). Buscar un valor significa aplicarle el hash una vez y saltar directamente al bucket — O(1) en promedio, sin importar el tamaño de la tabla. Las colisiones (dos claves distintas que caen en el mismo bucket) se resuelven con encadenamiento (una lista pequeña por bucket) o direccionamiento abierto (probar el siguiente slot libre); de cualquier forma, la búsqueda se mantiene cerca de tiempo constante mientras la tabla no esté sobrecargada.
El problema es que el hashing destruye el orden a propósito. hash("manzana") y hash("albaricoque") caen en buckets sin relación alguna aunque las cadenas sean lexicográficamente cercanas. Eso significa que un índice hash puede responder "¿existe exactamente este valor?" extremadamente rápido, pero es estructuralmente incapaz de responder "dame todo lo que está entre X e Y", "dame todo lo mayor que X", "dame esto en orden" o "dame todo lo que empieza con este prefijo". No hay forma de pasar de un bucket a otro numérica o lexicográficamente adyacente, porque la adyacencia en el espacio del hash no tiene nada que ver con la adyacencia en los datos reales.
#B-trees: sacrificar un poco de velocidad de búsqueda para conservar todo lo demás
Un B-tree (y su refinamiento casi universal, el B+tree) es un árbol balanceado, ordenado y de múltiples ramas. "Múltiples ramas" es la diferencia clave frente a un árbol binario: en lugar de dos hijos por nodo, un nodo de B-tree contiene muchas claves y muchos punteros a hijos — a menudo cientos, porque el tamaño del nodo se ajusta para coincidir con una página de disco (comúnmente 4–16 KB). Ese factor de ramificación alto es deliberado: mantiene el árbol extremadamente bajo incluso sobre tablas enormes, lo cual importa porque históricamente cada nivel del árbol significaba una búsqueda en disco, y las búsquedas en disco son la parte cara.
El recorrido es un descenso directo: empiezas en la raíz, comparas tu clave de búsqueda contra las claves separadoras guardadas en ese nodo para decidir qué puntero de hijo seguir, pasas a ese hijo, y repites hasta llegar a una hoja. En un B+tree en particular, todos los punteros reales a los datos (o las filas mismas, en un índice clúster) viven en las hojas, y — este es el detalle que desbloquea todo lo demás — las hojas están enlazadas entre sí en orden, formando una cadena ordenada a lo largo de la base del árbol.
Esa capa de hojas enlazadas y ordenadas es la razón por la que los B-trees pueden hacer mucho más que los índices hash: una vez que descendiste hasta la hoja de inicio correcta, un escaneo de rango es simplemente "seguir recorriendo la cadena de hojas hacia adelante hasta que la condición deje de cumplirse". Un ORDER BY sobre la columna indexada puede resolverse directamente con el orden de las hojas, sin un paso de ordenamiento aparte. Una coincidencia de prefijo (LIKE 'sm%') desciende hasta la primera hoja donde el prefijo podría empezar y recorre hacia adelante desde ahí. Las búsquedas por igualdad también funcionan — desciendes hasta la hoja, y encuentras la clave o demuestras que está ausente — solo que en O(log_f n) en lugar de O(1), donde f es el factor de ramificación.
Sigue una búsqueda del valor 63 en el diagrama de arriba: en la raíz, 63 es mayor que 50 y menor que 120, así que sigues el puntero del hijo del medio hacia el nodo [70 | 95]. Ahí, 63 es menor que 70, así que sigues su puntero al hijo más a la izquierda hacia la hoja que contiene 55, 63, 70, donde un recorrido de esa hoja (pequeña) encuentra la clave directamente. Son tres lecturas de nodo para una tabla que podría tener millones de filas — y si la consulta hubiera pedido en cambio todo lo que está entre 60 y 90, llegarías a la misma hoja de inicio y simplemente seguirías recorriendo la cadena de hojas enlazadas (la línea punteada) hacia la derecha, recogiendo 63, 70, luego pasando a la siguiente hoja por 80, 88, deteniéndote apenas superes 90.
#Por qué ganaron los B-trees a pesar de ser asintóticamente más lentos
Si un índice hash es O(1) y un B-tree es O(log n), ¿por qué prácticamente todas las bases de datos relacionales usan un B-tree como tipo de índice por defecto, reservando los índices hash para un nicho estrecho? Dos razones. Primero, un logaritmo en base 100 o más es pequeño en la práctica — un B-tree sobre mil millones de filas con un factor de ramificación de 200 tiene apenas unos 4 niveles de profundidad, así que la brecha asintótica casi no importa a escala real. Segundo, y más importante, un B-tree es un superconjunto estricto en capacidades: resuelve igualdad, rango, prefijo, ordenamiento, MIN/MAX y joins que dependen de sort-merge, todo desde una sola estructura. Un índice hash resuelve exactamente una de esas cosas. Dado que la mayoría de los esquemas necesitan al menos ocasionalmente consultas de rango u orden sobre una columna indexada, usar B-tree por defecto y reservar los índices hash para el caso raro de igualdad pura sin necesidad de orden jamás es la decisión de ingeniería pragmática — y es exactamente por eso que PostgreSQL, InnoDB de MySQL, SQL Server y Oracle hacen que CREATE INDEX use un B-tree por defecto a menos que pidas explícitamente otra cosa.
#El detalle que prepara tu próxima pregunta de entrevista
Como las hojas de un B-tree están ordenadas por la clave completa en estricto orden de izquierda a derecha, un índice compuesto sobre (a, b, c) es en realidad una sola estructura ordenada primero por a, luego por b dentro de cada a, y luego por c dentro de cada b — no tres índices independientes pegados entre sí. Esa es la razón estructural directa por la que los índices compuestos solo sirven eficientemente a una consulta cuando esta restringe un prefijo de izquierda a derecha de las columnas indexadas. Es el mismo árbol, la misma regla de recorrido, solo aplicada a una clave compuesta — que es exactamente el mecanismo detrás de la selectividad de índices y el orden de columnas.
#Ponte a prueba
🧠 Check your understanding
0/3 · 0/3 answered1. ¿Por qué un índice hash no puede resolver una consulta de rango como `WHERE age BETWEEN 20 AND 30`?
2. En un B+tree, ¿por qué los nodos hoja están enlazados entre sí en orden?
3. ¿Por qué la mayoría de las bases de datos relacionales usan un B-tree por defecto en CREATE INDEX en lugar de un índice hash, aunque las búsquedas hash sean asintóticamente más rápidas para igualdad?