B-tree shine jirgin bincike na kai tsaye wanda kowane nod ake ajiyar marubuta masu yawa da yana da yara masu yawa (samun fanout babbar). Wannan yana kiyaye jirgi m dau**, yana raguwa adadin karatu diska — wanda shine daidai abin da databases da filesystems suke bukatarwa.
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 cikin B+ tree, duk daraja suna zaune a ganye da ganye sune haɗa kai, don haka yin jajjer nisa taka jerin ganye masu haɗa kai — kyau don ƙarin ire-ire kamar WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Aiki | Lokaci | Karatu Diska |
|---|---|---|
| bincike | O(log n) | O(tsayi) |
| saka / tsige | O(log n) | O(tsayi) |
| jajjer nisa | O(log n + k) | ganye jeri |
Karatu diska da SSD sune da jigon yawa a sannu fiye da alaƙa, don haka abin da ke doka shine adadin I/O, ba karɓoɓo ba.
Babar fanout yana tsotse I/O sosai ta riƙe jirgi kaɗai a waje matakai masu zuwa.
Do ya sa kusan duk Index na database mai kare (da ayoyi masu yawa na filesystem) an gina su akan B+ trees maimakon jirgin bincike na binary.