Principios de funcionamiento de los índices: estructura de datos y algoritmos de búsqueda

Hoy vamos a meternos más a fondo en la arquitectura de los índices y ver cómo funcionan realmente por dentro. Porque saber cómo está hecho un índice no solo ayuda a entender por qué las consultas van más rápido, sino también a elegir los índices óptimos para cada caso.

Cuando hablamos de la estructura de un índice, nos referimos a cómo están organizados los datos dentro del índice para asegurar una búsqueda rápida. Imagina un armario con documentos. Si los documentos están todos tirados en una pila, encontrar el que necesitas es complicado. Pero si el armario está ordenado alfabéticamente, buscar se vuelve mucho más fácil. Los índices funcionan justo así: ordenan los datos de tal manera que buscar la info que necesitas sea lo más rápido posible.

Estructura del índice B-TREE

B-TREE (balanced tree — árbol balanceado) es el tipo de índice más usado en PostgreSQL. Básicamente, es una estructura en forma de árbol donde los datos están organizados en nodos, y la búsqueda se hace navegando desde la raíz del árbol hasta las hojas.

¿Cómo se ve esto?

         Raíz
          /       |       \
      Nodo 1    Nodo 2    Nodo 3
     /   \       |       /   \
Hoja1 Hoja2   Hoja3  Hoja4 Hoja5

Cada nodo contiene valores clave que permiten dirigir la búsqueda. Por ejemplo, si el nodo raíz tiene los valores [10, 20, 30], entonces:

• Todos los datos menores que 10 están en Hoja 1.
• Todos los datos entre 10 y 20 — en Hoja 2, y así sucesivamente.

Ventajas del índice B-TREE:

• Búsqueda rápida de datos: la complejidad de búsqueda es O(log n), mucho más rápido que una búsqueda lineal.
• Sirve para búsquedas por rangos (por ejemplo, encontrar todos los valores entre 10 y 50).

Ejemplo: supón que tenemos una tabla students con la columna age. Cuando creamos un índice B-TREE en esa columna:

CREATE INDEX age_idx ON students (age);

PostgreSQL crea un árbol balanceado para los valores de edad, lo que permite encontrar rápido a los estudiantes de una edad concreta o de un rango de edades.

Algoritmo de búsqueda en B-TREE

Cuando ejecutas una consulta, PostgreSQL usa el índice para buscar los datos así:

1. Determina la clave de búsqueda (por ejemplo, edad 25).
2. Empieza desde el nodo raíz.
3. Compara la clave con los rangos de valores del nodo y va al nodo hijo correspondiente.
4. Repite el paso 3 hasta llegar a la hoja.
5. Devuelve los datos de la hoja que coinciden con la clave.

Ejemplo de consulta:

SELECT * FROM students WHERE age = 25;

El índice reduce la cantidad de datos que hay que escanear, asegurando una búsqueda rápida.

Algoritmos de búsqueda y rendimiento

Los índices aceleran la búsqueda porque reducen la cantidad de filas que hay que escanear. Sin índice, PostgreSQL escanea toda la tabla (esto se llama escaneo secuencial, o Seq Scan). Con un índice se hace un escaneo por índice (Index Scan), que es mucho más rápido.

Comparación entre escaneo secuencial e indexado

• Escaneo secuencial (Seq Scan):

  • PostgreSQL lee cada fila de la tabla, comprueba las condiciones de la consulta y devuelve las filas que encajan.
  • Se usa si no hay índice o si la consulta abarca casi todas las filas de la tabla.

• Escaneo por índice (Index Scan):

  • PostgreSQL usa el índice para buscar las filas que corresponden y luego accede a la tabla solo para esas filas.
  • Mucho más rápido en tablas grandes si la consulta afecta a un subconjunto pequeño de datos.

Ejemplo: sin índice, buscar edades

SELECT * FROM students WHERE age = 25;

el resultado puede requerir leer 1 millón de filas. Con el índice B-TREE, por ejemplo, el sistema solo lee 100 filas.

Impacto de la estructura del índice en el rendimiento

Los índices funcionan más rápido porque reducen el volumen de datos a escanear. Por ejemplo, si una tabla tiene millones de filas, el índice las organiza de tal manera que la consulta solo tiene que leer unos pocos nodos en vez de toda la tabla.

Es muy importante entender la estructura del índice. Saber cómo funcionan exactamente los índices ayuda a entender por qué algunas consultas son lentas y cómo hacerlas más rápidas.

Además, es clave saber qué índices usar. Para búsquedas por rangos va bien B-TREE. Para arrays o JSONB — GIN. Elegir mal el índice puede hacer que la base vaya más lenta.

Ejemplos reales

Vamos a ver cómo los índices nos ayudan en el trabajo.

Índice para ordenar

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Con el índice B-TREE, PostgreSQL puede devolver los datos ya ordenados directamente desde el índice, sin tener que ordenarlos aparte.

Índice para rangos

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

El índice B-TREE permite encontrar rápido las filas que están en el rango indicado.

Preguntas frecuentes y trampas

¿Por qué no siempre hay que usar índices? Los índices ocupan espacio en disco y ralentizan las operaciones de inserción, actualización y borrado, porque hay que actualizar la estructura del índice. Por eso es importante crear índices solo para las columnas que se usan mucho.

¿Cuándo no ayudan los índices? Para consultas que cubren casi toda la tabla (por ejemplo, WHERE true), PostgreSQL prefiere Seq Scan, porque leer los nodos del índice no aporta ventaja.