Índices en Bases de Datos: Parte 1 — El Origen
¿Por qué existen los índices?
¿Alguna vez te has preguntado cómo una base de datos encuentra un solo registro entre millones… en milisegundos?
Detrás de esa magia no hay trucos, sino estructuras de datos cuidadosamente diseñadas: los índices.
Pero… ¿qué son realmente? ¿Cómo surgieron? ¿Cómo funcionan internamente y cómo llegan hasta el disco?
Para responder a todo esto, preparamos una serie dividida en tres partes donde vamos a desmenuzar los índices desde su origen histórico hasta su representación física en disco, pasando por árboles B, simulaciones en código y visualizaciones byte a byte.
📘 Parte 1 — ¿Por qué existen los índices?
El caos de las búsquedas lineales
Qué pasaba antes de los índices
Por qué ordenar no fue suficiente
La evolución hacia árboles B como solución
📘 Parte 2 — ¿Cómo funciona un índice internamente?
La anatomía del árbol B/B+
Cómo se estructuran los nodos y enlaces
Simulación visual y en código
Comparación contra escaneo lineal
📘 Parte 3 — ¿Qué hay en disco cuando consultas?
Cómo los motores (como PostgreSQL) almacenan los índices
Páginas físicas, headers, punteros y TIDs
Cómo se navega desde el índice hasta la fila real
Análisis práctico con herramientas como
EXPLAIN ANALYZEypageinspect
Parte 1 — ¿Por qué existen los índices?
De las Búsquedas Lineales a la Necesidad de Estructuras Inteligentes
📜 Todo empezó en los años 70…
Corría el año 1973. Hacía apenas tres años que Edgar F. Codd, desde los laboratorios de IBM, había formulado el modelo relacional de datos. La industria aún digería esa revolución teórica, mientras las bases de datos seguían siendo, en esencia, archivos planos sobre cintas o discos duros.
Imagina que te entregan un archivo con un millón de empleados. Y te piden encontrar a "Juan Pérez". No hay índices, ni motores SQL, ni columnas ordenadas. Solo una lista.
Así que comienzas: registro por registro, nombre por nombre.
Era como buscar una hoja específica en una pila de un millón de papeles… sin clips, sin separadores, sin colores. Solo esperanza y paciencia.
📁 ¿Qué había antes? Archivos secuenciales
En los sistemas de los años 70, una tabla no era más que un archivo secuencial. Literalmente una lista larga de registros, uno detrás del otro en disco:
Archivo: empleados.dat
├── Juan Pérez (ID: 1001)
├── María García (ID: 1002)
├── Carlos López (ID: 1003)
...Búsqueda = recorrer archivo desde el principio hasta encontrar el valor deseado.
Inserción = escribir al final.
Actualización = sobrescribir en el mismo lugar o reescribir el archivo entero.
Era simple, pero escalaba pésimo.
📊 Comparación de tiempos de búsqueda:
Registros | Comparaciones Promedio | Tiempo (1970s)
--------------------------------------------------------
1,000 | 500 | 0.5 segundos
10,000 | 5,000 | 5 segundos
100,000 | 50,000 | 50 segundos
1,000,000 | 500,000 | 8.3 minutos
10,000,000 | 5,000,000 | 83 minutosEl problema no era solo el tiempo de búsqueda, sino que no había forma de saltar directamente a un registro si no sabías dónde empezaba.
♻️ Primeras mejoras: ordenamiento y archivos índice
Una de las primeras ideas fue ordenar los archivos por una clave (como el ID) para que, en teoría, se pudiera hacer búsqueda binaria.
Pero había un problema: a diferencia de un array en memoria, los archivos en disco no permiten saltar al "elemento del medio" si no sabes dónde empieza cada registro. No puedes calcular posición = inicio + (n / 2) * tamañoRegistro, porque los registros no siempre tienen el mismo tamaño.
La única solución era mantener un índice auxiliar con los offsets exactos: los byte offsets de cada registro dentro del archivo.
En esencia, un índice es una estructura auxiliar que actúa como un mapa de ubicaciones: no guarda todos los datos, pero sí mantiene un listado ordenado de identificadores (como los IDs) junto a sus posiciones físicas en disco. Gracias a esto, la base de datos puede hacer una búsqueda rápida en memoria y leer directamente el registro correcto sin recorrer toda la tabla.
Así nació el concepto del índice simple: una tabla separada que permitía hacer búsqueda binaria sobre los IDs y luego acceder directamente al byte exacto (offset) en el archivo principal.
🧾 Comparación visual:
Archivo de datos original (ordenado):
Archivo: empleados.dat
├── ID 1001 | Juan Pérez → Offset: 0 bytes
├── ID 1002 | María García → Offset: 64 bytes
├── ID 1003 | Carlos López → Offset: 128 bytesÍndice auxiliar:
ID → Byte Offset
1001 → 0
1002 → 64
1003 → 128Esto significaba que podías hacer lo siguiente:
Cargar el índice auxiliar en memoria (era pequeño comparado con el archivo de datos)
Buscar el ID deseado en memoria (búsqueda binaria)
Obtener el offset exacto en el archivo de datos
Hacer una única lectura precisa en disco para recuperar el registro
🎯 ¿Por qué era mejor?
Con un índice auxiliar, podías evitar recorrer todo el archivo. Solo necesitabas hacer una búsqueda rápida en memoria (búsqueda binaria sobre los IDs) y luego una única lectura precisa en disco.
Pero esta solución venía con un nuevo precio: fragilidad ante los cambios.
Si querías insertar un nuevo registro intermedio (por ejemplo entre los IDs 1002 y 1003), tenías que mover los datos en el archivo o reconstruir el índice desde cero.
Si borrabas, los offsets quedaban obsoletos.
Este índice era como una guía telefónica impresa: útil mientras nada cambie. Pero los datos no se quedan quietos. En bases de datos reales, cada inserción, edición o borrado... lo cambia todo.
🛠️ Nuevas estrategias, nuevos problemas
A medida que las bases de datos crecían en volumen y complejidad, el índice simple con offsets mostró sus limitaciones: cada inserción o modificación podía invalidar toda la estructura, y los datos reales seguían siendo sensibles al orden físico del archivo.
Los ingenieros comenzaron entonces a explorar otras formas de mantener el acceso eficiente sin tener que reconstruir todo desde cero en cada cambio. Probaron con múltiples soluciones intermedias, intentando balancear rendimiento y flexibilidad.
Algunas estrategias funcionaban bien para ciertas columnas o tipos de consulta. Otras intentaban dividir o distribuir los datos para reducir el impacto de cambios. Pero ninguna resolvía todos los problemas a la vez. Algunas funcionaban para ciertos casos, pero ninguna resolvía el problema completo.
🔧 Intento #1: Índices múltiples por columna
🎯 Objetivo:
Evitar que el sistema dependa solo del ID para buscar. ¿Y si el usuario quiere consultar por nombre, email o fecha de nacimiento.
🔍 Solución:
Mantener copias ordenadas del archivo, una por cada campo
⚠️ Problema:
Cada inserción, actualización o eliminación debía replicarse en todas las copias.
Eso significaba duplicación de datos y costos altísimos de mantenimiento.
🔧 Intento #2: Particionamiento por rangos
🎯 Objetivo:
Reducir el impacto de modificar un archivo enorme.
🔍 Solución:
Dividir el archivo original en partes más pequeñas según el rango de ID (ej. 1000–1999, 2000–2999, etc.).
⚠️ Problema:
Aunque se limitaba el área afectada por una inserción, cada partición seguía siendo secuencial.
Y si los datos no se distribuían uniformemente, algunas particiones explotaban mientras otras quedaban vacías.
🔧 Intento #3: Separación por inicial alfabética
🎯 Objetivo:
Facilitar búsquedas textuales (por nombre) sin indexar completamente.
🔍 Solución:
Crear archivos separados por letra inicial (ej. A–M, N–Z).
⚠️ Problema:
La distribución era arbitraria e ineficiente. ¿Y si el 60% de los registros eran “Silva”?
⚡ La Necesidad Real
Todas estas soluciones aliviaban parte del problema, pero seguían dependiendo de estructuras lineales, estáticas o frágiles. Se necesitaba algo más:
Buscar en tiempo logarítmico (log N)
Insertar y borrar sin reconstruir todo
Escalar a millones de registros
A esas alturas, las soluciones planas —basadas en listas, archivos y offsets— ya no bastaban. Lo que faltaba era una estructura inteligente, capaz de adaptarse al crecimiento sin colapsar. No solo más rápida, sino más resiliente.
Era momento de explorar algo distinto: estructuras jerárquicas.
🌲 El Binary Tree: una mejora… que no alcanzó
Después de probar con archivos ordenados y con índices auxiliares basados en offsets, algunos ingenieros empezaron a explorar el uso de estructuras jerárquicas en memoria, como los árboles binarios de búsqueda (BST). Estos árboles ofrecían una mejora sobre los índices planos: mantenían el orden de forma jerárquica, permitiendo búsquedas en O(log n), pero también insertando y borrando sin necesidad de reordenar todo el archivo.
[40]
/ \
[20] [60]
/ \ / \
[10] [30] [50] [70]
/ \ / \ / \ / \
[5] [15][25][35][45][55][65][75] ← cada uno apuntando
a un bloque/página diferente en discoY sí, funcionaban muy bien en memoria. Pero al llevarlos al mundo del disco, surgieron varios problemas:
Crecen en profundidad muy rápidamente → muchas lecturas de disco
Cada nodo suele contener una sola clave, lo cual no es eficiente para discos duros donde se prefiere leer bloques de 4 KB o más
Además, los nodos de un árbol binario clásico (BST) generalmente no están en bloques contiguos de memoria. Al insertarse dinámicamente, terminan dispersos en el heap, lo que reduce la eficiencia del acceso por CPU cache. Y si llevamos esta estructura a disco, cada nodo podría terminar en una página distinta — haciendo que una búsqueda requiera múltiples accesos costosos a disco
En disco, cada acceso es costoso. Lo ideal es leer una página completa y aprovecharla al máximo.
🧠 ¿Sabías que...?
Los discos leen datos en bloques llamados páginas, típicamente de 4 KB. Si solo necesitas una clave específica, igual se lee el bloque entero.
Si cada nodo solo almacena una clave, estás usando quizás 20 bytes y desperdiciando los otros 4076. Eso implica más lecturas repetidas a disco para encontrar lo que necesitas.
🌳 Aquí entra el B-Tree: diseñado para almacenamiento externo
El B-Tree fue inventado en 1971 por Rudolf Bayer y Edward McCreight en Boeing, como una respuesta directa a las limitaciones de los árboles binarios en almacenamiento en disco.
Se preguntaron: "¿Y si en lugar de páginas planas, creamos una jerarquía de páginas donde cada página contenga muchas entradas y nos lleve a otras páginas completas?"
Esa pregunta llevó al diseño del B-Tree: un árbol ancho, poco profundo, optimizado desde el principio para el acceso eficiente a disco.
Mientras que los BST tradicionales crecen hacia abajo (en profundidad), el B-Tree crece hacia lo ancho: cada nodo contiene muchos índices ordenados que dividen el espacio de entradas posibles en rangos bien definidos. Por cada rango, hay un puntero que lleva a una subpágina del árbol.
Esto cambia radicalmente el juego:
Un solo nodo puede almacenar decenas o cientos de índices, todos ordenados
Cada nodo se ajusta al tamaño exacto de una página de disco (por ejemplo 4 KB), aprovechando al máximo cada lectura
En lugar de 20 niveles como un BST, un B-Tree puede cubrir millones de registros con solo 3 o 4 niveles.
Visualmente:
[5000]
/ \
[1000, 2000] [7000, 8000]
/ \ / \
[1001] [1500] [7300] [7900]
| | | |
Página12 Página17 Página87 Página94🧠 ¿Dónde vive realmente el índice?
En motores de bases de datos reales, los B-Trees están serializados en disco, no solo en memoria.
Cada nodo del árbol (raíces, intermedios, hojas) se guarda como una página física (por ejemplo, bloques de 4 KB).
Al hacer una búsqueda, el motor carga solo las páginas necesarias al buffer pool en memoria.
La raíz del árbol suele mantenerse en memoria, y a medida que navegas, se van trayendo más páginas desde disco bajo demanda.
Esto permite que el árbol sea persistente, escalable y eficiente, incluso con millones de registros.
🎯 Comparación real: sin índice vs con índice
Imagina esta consulta:
SELECT * FROM usuarios WHERE email = 'ana@example.com';
💡 ¿Qué cambió en el paradigma?
Antes, acceder a un registro en disco implicaba leer secuencialmente miles de bloques, uno tras otro, hasta dar con el dato.
Con un índice jerárquico como el B-Tree, la base de datos puede recorrer niveles de decisión estructurados: desde la raíz hasta la hoja, saltando entre páginas clave en disco, con solo 2 o 3 accesos en lugar de miles.
🧠¿Qué aprendimos en esta parte?
Las bases de datos no siempre fueron rápidas.
El problema de búsqueda lineal era estructural, no de hardware.
Intentos manuales (ordenar, segmentar, duplicar) eran frágiles.
La solución fue una estructura robusta y autoajustable: el índice B-Tree.
🔍Qué viene en la Parte 2
En la próxima entrega vamos a abrir la caja negra del índice y ver cómo funciona internamente:
Cómo se estructura un árbol B y B+ en páginas
Qué guardan sus nodos: entradas, punteros, enlaces
Cómo crece, se divide y se reequilibra
Y cómo construir uno paso a paso con simulación en código
¿Te gustó esta primera parte?
Dejame tus dudas o sugerencias, porque esto recién comienza.