A B-tree é uma árvore de busca auto-equilibrada onde cada nó contém muitas chaves e tem muitos filhos (alto fanout). Isso mantém a árvore rasa, minimizando o número de leituras de disco — exatamente o que bancos de dados e sistemas de arquivos precisam.
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
Em uma B+ tree, todos os valores residem nas folhas e as folhas são vinculadas, então varreduras de intervalo percorrem uma lista vinculada de folhas — ideal para consultas como WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operação | Tempo | I/O de disco |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
O acesso a disco e SSD é ordens de magnitude mais lento que a memória, então a métrica que importa é contagem de I/O, não comparações.
Alto fanout reduz drasticamente I/O mantendo a árvore apenas alguns níveis de profundidade.
Por isso, quase todos os índices de banco de dados relacional (e muitos sistemas de arquivos) são construídos em B+ trees em vez de árvores de busca binária.