Índices de base de datos: cómo encontrar un registro entre 100 millones en 0,01 segundos

Al finalizar este tema

Podrás explicar el principio de por qué los índices son rápidos y determinar cuándo es necesario crear un índice.

Adivinar un número del 1 al 100

Juguemos a un juego. Tu oponente ha elegido un número entre 1 y 100. Debes adivinarlo.

Método A: "¿Es el 1?", "¿Es el 2?", "¿Es el 3?" — Preguntar uno por uno. En el peor de los casos, tendrás que preguntar 100 veces.

Método B: "¿Es mayor que 50?", "¿Es mayor que 75?", "¿Es mayor que 62?" — Reducir a la mitad en cada paso. Con un máximo de 7 intentos es suficiente.

En una base de datos, sin índice se aplica el método A, y con índice, el método B. Si hay 100 registros, la diferencia no se nota, pero con 100 millones de registros, la diferencia es 100 millones de veces frente a 27.

Qué ocurre al buscar sin un índice

SELECT * FROM users WHERE age = 20;

Si no hay un índice, la base de datos debe revisar cada fila de la tabla users individualmente. Esto se conoce como Full Scan. Si hay 100 millones de registros, tendría que buscar entre los 100 millones.

Al crear un índice

CREATE INDEX idx_age ON users(age);

Al ejecutar esta línea, la base de datos ordena previamente los valores de la columna age y los almacena en una estructura separada. A partir de ese momento, al ejecutar WHERE age = 20, se realiza una búsqueda eliminando la mitad de los datos ordenados en cada paso. Incluso con 100 millones de registros, solo se necesitan 27 comparaciones.

B+ Tree: la estructura que se utiliza en la práctica

La idea básica de "eliminar la mitad" es la búsqueda binaria. Sin embargo, las bases de datos reales no utilizan directamente un árbol de búsqueda binaria, sino una estructura llamada B+ Tree.

B-Tree: cada nodo contiene varios elementos de datos. Si el árbol de búsqueda binaria divide los datos a la mitad en cada paso, el B-Tree los divide en tercios o cuartos, lo que lo hace más rápido.

B+ Tree: es una evolución del B-Tree.

• Los datos reales se almacenan únicamente en el nivel inferior (nodos hoja).
• Los nodos superiores solo actúan como un índice que indica "hacia dónde dirigirse".
• Los nodos hoja están conectados entre sí, lo que permite realizar búsquedas por rango de forma rápida.

En una búsqueda por rango como «busca usuarios de entre 20 y 30 años»,
el B+ Tree localiza primero 20 y después recorre las hojas enlazadas hasta llegar a 30.

El índice base de las bases de datos modernas (MySQL, PostgreSQL) es el árbol B+.

El costo de los índices

Nada es gratis. Siempre hay un compromiso (trade-off):

Espacio de almacenamiento: Un índice es una copia ordenada de los datos. Cuantos más índices se creen, mayor será el tamaño de la base de datos.

Rendimiento de escritura: Al realizar un INSERT o un UPDATE, también se deben actualizar los índices. Si hay 10 índices, al insertar un solo registro, se deben modificar los 10.

Por lo tanto, se crean índices en las columnas con "muchas lecturas" y se evita su uso excesivo en las tablas con "muchas escrituras".

Un punto importante: la clave primaria (Primary Key) tiene un índice asociado automáticamente. Esto se conoce como índice agrupado (Clustered Index). Si se busca por la clave primaria, la búsqueda ya es rápida sin necesidad de crear un índice adicional.

Cuándo no se debe crear un índice

Hay casos en los que un índice puede ser perjudicial:

• Cuando hay pocos datos: En una tabla con 100 registros, crear un índice podría ser más lento que un escaneo completo (Full Scan). Leer secuencialmente los 100 registros es más rápido que navegar por la estructura ordenada.
• Cuando hay poca variedad de valores: En una columna como gender, donde los valores son solo "M" o "F", crear un índice no aporta beneficios. De todos modos, habría que leer la mitad de los datos. Esto se denomina tener una "baja cardinalidad" (low cardinality).
• Tablas con predominio de inserciones: En tablas de logs, donde los datos solo se acumulan y casi nunca se leen, el índice solo reduce el rendimiento de escritura.

En las entrevistas, es más común preguntar "cuándo no se debe crear un índice" que "cuándo sí". Se debe crear un índice solo cuando se cumplen estas tres condiciones: alta frecuencia de lecturas, alta cardinalidad y uso frecuente en la cláusula WHERE.

Puntos clave

Un índice es un índice o tabla de contenido con los datos preordenados. Sin él, se deben revisar los 100 millones de registros (Full Scan); con él, se termina en 27 comparaciones. Sin embargo, consume espacio de almacenamiento y ralentiza las escrituras. Úsalo solo en las columnas donde predominan las lecturas.