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-tree 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.

El B-tree almacena claves en orden ordenado dentro de los nodos, lo que permite una recuperación rápida de datos mediante la navegación 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-tree 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 para 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 hasta 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 usar los punteros horizontales entre los nodos hoja. Por ejemplo, recuperar valores desde 302 hasta 502 se realiza siguiendo secuencialmente los nodos hoja.

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 alojar 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 instrucción para crearlo:

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