A B-tree to samozrównoważone drzewo wyszukiwania, w którym każdy węzeł przechowuje wiele kluczy i ma wielu potomków (wysoki fanout). Utrzymuje to drzewo płytkim, minimalizując liczbę odczytów z dysku — dokładnie to, czego potrzebują bazy danych i systemy plików.
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
W B+ tree wszystkie wartości znajdują się w liściach i liście są połączone, więc skanowanie zakresu przechodzi przez połączoną listę liści — idealne dla zapytań takich jak WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operacja | Czas | I/O z dysku |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Dostęp do dysku i SSD jest o wiele rzędów wielkości wolniejszy niż pamięć, więc metryką, która ma znaczenie, jest liczba I/O, a nie porównania.
Wysoki fanout drastycznie zmniejsza I/O, utrzymując drzewo na zaledwie kilka poziomów głębokie.
Dlatego prawie każdy indeks relacyjnej bazy danych (i wiele systemów plików) jest zbudowany na B+ trees zamiast na binarnych drzewach wyszukiwania.