A B-tree egy önkiegyenlítő keresési fa, ahol minden csomópont sok kulcsot tartalmaz és sok gyermeke van (magas fanout). Ez a fát sekélynek tartja, minimalizálva a lemezolvasások számát — amit pontosan az adatbázisok és fájlrendszerek igényelnek.
A B-tree egy önkiegyenlítő keresési fa, ahol minden csomópont sok kulcsot tartalmaz és sok gyermeke van (magas fanout). Ez a fát sekélynek tartja, minimalizálva a lemezolvasások számát — amit pontosan az adatbázisok és fájlrendszerek igényelnek.
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
A B+ tree-ben minden érték a levelekben él és a levelek összekapcsoltak, így a tartomány-keresések egy összekapcsolt levelek listáját haladják meg — ideális olyan lekérdezésekhez, mint WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Művelet | Idő | Lemez I/O |
|---|---|---|
| keresés | O(log n) | O(magasság) |
| beszúrás / törlés | O(log n) | O(magasság) |
| tartomány-keresés | O(log n + k) | szekvenciális levelek |
A lemez és SSD hozzáférés nagyságrendekkel lassabb, mint a memória, így a mérvadó metrika az I/O-szám, nem az összehasonlítások.
A magas fanout drámaian csökkenti az I/O-t azáltal, hogy a fát csak néhány szint mélyre tartja.
Ezért szinte minden relációs adatbázis-index (és sok fájlrendszer) B+ trees alapján épül, nem pedig bináris keresési fák alapján.