Un Árbol B+ extiende al B-Tree separando claramente el almacenamiento de claves (en hojas) del enrutamiento (en nodos internos). Esto favorece recorridos ordenados y un mayor factor de ramificación efectivo para búsquedas.
7.1 Estructura general de un árbol B+
Los nodos internos solo guardan claves de separación y punteros a hijos.
Las hojas almacenan todas las claves y punteros a datos o registros.
La altura se mantiene baja como en el B-Tree, con el mismo grado t.
7.2 Todas las claves en hojas
Las claves reales (las que se devuelven al buscar) viven únicamente en las hojas:
Los nodos internos pueden repetir claves solo para guiar la búsqueda.
El espacio de las hojas se aprovecha al máximo para almacenar pares clave/valor.
Permite recorridos in-order lineales sin volver a nodos internos.
7.3 Nodo interno solo dirige la búsqueda
Un nodo interno actúa como índice de rangos:
Comparte el formato [k1 | k2 | ... | km] con m+1 punteros a hijos.
No guarda punteros a registros; cada clave interna funciona como límite superior del subárbol izquierdo.
Esto aumenta el fan-out efectivo porque no se reservan campos de datos en los internos.
7.4 Enlaces entre hojas (linked leaves)
Las hojas suelen enlazarse en una lista doble o simple:
Cada hoja apunta a su siguiente (y a veces a la anterior) para recorridos secuenciales rápidos.
Un range scan O(k + h) se logra con una única bajada a la primera hoja y luego saltando con los enlaces.
Esta propiedad hace a los B+ ideales para índices y consultas por rangos.