B-tree — это самобалансирующееся дерево поиска, в котором каждый узел содержит много ключей и имеет много потомков (высокий fanout). Это делает дерево неглубоким, минимизируя количество дисковых операций чтения — ровно то, что нужно базам данных и файловым системам.
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
В B+ tree все значения находятся в листьях и листья связаны, поэтому сканирование диапазона проходит по связному списку листьев — идеально для запросов типа WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Операция | Время | Дисковые операции ввода-вывода |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Доступ к диску и SSD на порядки медленнее, чем к памяти, поэтому важный показатель — количество дисковых операций, а не сравнений.
Высокий fanout резко снижает количество дисковых операций, держа дерево в глубине всего нескольких уровней.
Поэтому практически каждый индекс реляционной базы данных (и многие файловые системы) построены на B+ trees вместо двоичных деревьев поиска.