Un B-tree es un árbol de búsqueda autobalanceado donde cada nodo contiene muchas claves y tiene muchos hijos (alto fanout). Esto mantiene el árbol poco profundo, minimizando el número de lecturas de disco — que es exactamente lo que necesitan las bases de datos y los sistemas de archivos.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
En un B+ tree, todos los valores viven en las hojas y las hojas están vinculadas, por lo que los escaneos de rango caminan una lista vinculada de hojas — ideal para consultas como WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operación | Tiempo | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
El acceso a disco y SSD es órdenes de magnitud más lento que la memoria, por lo que la métrica que importa es el conteo de I/O, no las comparaciones.
El alto fanout reduce drásticamente el I/O manteniendo el árbol solo algunos niveles de profundidad.
Este es el motivo por el cual casi cada índice de base de datos relacional (y muchos sistemas de archivos) se construye en B+ trees en lugar de árboles de búsqueda binarios.
Una biblioteca de preguntas de entrevista de IT con respuestas detalladas — de Junior a Senior.
Donar