B-strom je samorovnávající se vyhledávací strom, kde každý uzel obsahuje mnoho klíčů a má mnoho potomků (vysoký fanout). To udržuje strom mělký, čímž se minimalizuje počet disk reads — což je přesně to, co potřebují databáze a souborové systémy.
B-strom je samorovnávající se vyhledávací strom, kde každý uzel obsahuje mnoho klíčů a má mnoho potomků (vysoký fanout). To udržuje strom mělký, čímž se minimalizuje počet disk reads — což je přesně to, co potřebují databáze a souborové systémy.
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
V B+ stromě všechny hodnoty se nacházejí v listech a listy jsou propojeny, takže prohledávání rozsahu prochází propojeným seznamem listů — ideální pro dotazy jako WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operace | Čas | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Přístup na disk a SSD je řádově pomalejší než v paměti, takže metrika, která záleží, je počet I/O, nikoli porovnání.
Vysoký fanout drasticky snižuje I/O tím, že udržuje strom pouze několik úrovní hluboký.
Proto je skoro každý index relační databáze (a mnoho souborových systémů) postaven na B+ stromech spíše než na binárních vyhledávacích stromech.