A B-tree este un arbore de căutare auto-echilibrat în care fiecare nod deține multe chei și are mulți copii (ridicat fanout). Aceasta menține arborele mic, minimizând numărul de citiri de disc — exact ceea ce au nevoie bazele de date și sistemele de fișiere.
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
Într-un B+ tree, toate valorile trăiesc în frunze și frunzele sunt legate, deci scanările de interval merg printr-o listă legată de frunze — ideal pentru interogări precum WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operație | Timp | I/O disc |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Accesul la disc și SSD este cu ordine de mărime mai lent decât memoria, deci metrica care conteaza este numărul I/O, nu comparații.
Fanout ridicat reduce drastic I/O prin menținerea arborelui la doar câteva niveluri adâncime.
Aceasta este motivul pentru care aproape fiecare index de bază de date relațională (și multe sisteme de fișiere) este construit pe B+ trees în loc de arbori de căutare binară.