Árboles B y B+
El árbol balanceado reimaginado para disco.
Nodos anchos → pocos niveles → pocas lecturas de disco.
En disco, costo = bloques leídos
- Cada nodo = un bloque de disco, repleto de cientos de llaves
- Fan-out m → altura log_m n, no log₂ n
- Árbol de orden 128 sobre 1M de llaves: 3 niveles, no 20
- El mismo O(log n), pero log base 128, no base 2
Mira los nodos llenarse y partirse
Las llaves se acumulan; desbordamiento → partición, la mediana sube. La raíz se parte → el árbol crece.
Todas las hojas se quedan a la misma profundidad.
El fan-out aplasta la altura
500000 llaves: 3 niveles vs 19 → ~6× menos lecturas de disco. A ms por seek, ahí está todo el partido.
Árboles B+ (los que usan las bases de datos)
- Datos solo en las hojas; los nodos internos son puras llaves guía → todavía más bajo
- Hojas encadenadas → los recorridos por rango caminan la lista de hojas en secuencia
- Todo índice SQL, todo sistema de archivos
Para llevar
Empata la estructura con la jerarquía de memoria sobre la que corre.
¿En memoria? Usa un árbol rojo-negro. ¿En disco? Árbol B. Sigue: Union-Find.