Un índice B-tree es una estructura de datos de árbol balanceado utilizada comúnmente en bases de datos para organizar y buscar grandes volúmenes de datos de manera eficiente.
Los B-trees son muy similares a los árboles binarios de búsqueda (BST), pero los nodos en un B-tree pueden tener más de dos hijos. Puede obtener más información sobre los BST en el curso Resumen de Algoritmos y Estructuras de Datos.

El B-tree almacena claves en ordenado dentro de los nodos, lo que permite una recuperación rápida de datos mediante la búsqueda jerárquica desde la raíz hasta los nodos hoja. La indexación B-tree es adecuada para consultas de rango y búsquedas de igualdad, lo que la convierte en una opción popular para optimizar el rendimiento de bases de datos.

¿Cómo funciona?

El índice B-tree organiza los datos de manera jerárquica, con cada nodo conteniendo un número fijo de claves y punteros a nodos hijos.
Los B-trees mantienen el equilibrio asegurando que todas las hojas estén al mismo nivel, lo que optimiza las operaciones de búsqueda.
Al buscar una clave en particular, el algoritmo B-tree recorre el árbol desde el nodo raíz hasta los nodos hoja, utilizando búsqueda binaria para localizar eficientemente la clave deseada.

Búsqueda en el índice implica recorrer el árbol hasta llegar a los nodos hoja, seguir la cadena de nodos hoja para encontrar los registros coincidentes y recuperar los datos reales desde el disco.

En la figura, se muestra la búsqueda de la clave 302:

1. Una estructura de árbol de búsqueda es un tipo de árbol donde cada nodo tiene dos punteros: el puntero izquierdo apunta a nodos hijos con valores menores que el nodo padre, y el puntero derecho apunta a nodos hijos con valores mayores que el nodo padre;

2. En un B-tree, el nodo raíz puede contener múltiples valores de índice. Por ejemplo, si la raíz contiene tres valores distintos, tendrá tres punteros, cada uno indicando el rango de valores entre esos valores clave;

3. Para buscar una clave, como 302, la búsqueda comienza en el nodo raíz y sigue los punteros apropiados hacia los nodos hoja. La búsqueda se completa después de recorrer tres bloques del árbol, como se muestra en el diagrama resaltado en rojo;

4. Para buscar un rango de valores comenzando desde 302, se pueden utilizar los punteros horizontales entre los nodos hoja. Por ejemplo, recuperar valores desde 302 hasta 502 se realiza siguiendo secuencialmente los nodos hoja.

Nota

La clave utilizada para buscar en un índice B-tree proviene de los valores almacenados en la(s) columna(s) indexada(s) de la tabla de la base de datos. Por ejemplo, si el índice está en una columna como "client_id", la clave de búsqueda serán los valores reales de "client_id". Cada valor numérico único en la columna indexada sirve como clave en el índice B-tree, lo que facilita encontrar y recuperar las filas correspondientes en la tabla de la base de datos.

Ventajas y desventajas

A diferencia de la estructura de datos estándar de Árbol Binario de Búsqueda, los nodos de un B-tree pueden albergar más de 2 hijos. El número máximo predeterminado de hijos por nodo suele establecerse en 16.

Implementación de índices

Para crear un índice B-tree en una columna en PostgreSQL, se puede utilizar el siguiente comando SQL:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Como el índice B-tree es un índice predeterminado en SQL, también se puede utilizar la siguiente sentencia para crearlo:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);

Nota

En SQL, cuando se crea una tabla con una restricción de clave primaria, la mayoría de los sistemas de gestión de bases de datos crean automáticamente un índice en la(s) columna(s) especificada(s) en la clave primaria. Este índice ayuda a hacer cumplir la restricción de unicidad de la clave primaria y también mejora el rendimiento de las consultas que implican búsquedas o uniones basadas en la(s) columna(s) de la clave primaria.