B-tree je samouravnotežujuće stablo pretrage gdje svaki čvor sadrži mnogo ključeva i ima mnogo djece (visoka fanout). Ovo drži stablo plitkim, minimiziranjem broja disk čitanja — što je upravo ono što baze podataka i datotečni sustavi trebaju.
B-tree je samouravnotežujuće stablo pretrage gdje svaki čvor sadrži mnogo ključeva i ima mnogo djece (visoka fanout). Ovo drži stablo plitkim, minimiziranjem broja disk čitanja — što je upravo ono što baze podataka i datotečni sustavi trebaju.
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
U B+ tree, sve vrijednosti žive u listovima i listovi su povezani, pa rasponski skenovi prolaze vezanu listu listova — idealno za upite kao WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operacija | Vrijeme | Disk I/O |
|---|---|---|
| pretraga | O(log n) | O(visina) |
| umetanje / brisanje | O(log n) | O(visina) |
| rasponski sken | O(log n + k) | sekvencijalni listovi |
pristup diskovanju i SSD-u je magnitudu sporiji od memorije, pa je metrika koja je bitna broj I/O, ne usporedbe.
Visoka fanout drastično smanjuje I/O održavanjem stabla samo nekoliko razina duboko.
To je razlog zašto je gotovo svaki relacijski indeks baze podataka (i mnogi datotečni sustavi) izgrađen na B+ trees umjesto binarnih stabala pretrage.
Knjižnica IT pitanja za razgovore za posao s detaljnim odgovorima — od Juniora do Seniora.
Doniraj