B-miti ni miti wa utafutaji wa kujizangoiza ambapo kila nodi ina funguo nyingi na ina watoto wengi (fanout ya juu). Hii inabaki miti kichwa, ikiwa na kiwango cha chini cha kusoma kwa diski — ambayo ni kwa nini besi za data na mifumo ya faili zinahitaji.
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
Katika B+ miti, thamani zote zinaishi katika majani na majani ni manukuu, kwa hivyo ufatuzi wa thamani hutembea kwa orodha ya manukuu ya majani — bora kwa maswali kama WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operesheni | Wakati | Disk I/O |
|---|---|---|
| kutafuta | O(log n) | O(urefu) |
| kuingiza / kufuta | O(log n) | O(urefu) |
| ufatuzi wa thamani | O(log n + k) | majani ya mlolongo |
Upatikanaji wa diski na SSD ni haraka zaidi kuliko kumbukumbu kwa kiwango cha ukubwa, kwa hivyo kipimo kinachohusika ni hesabu ya I/O, sio kulinganisha.
Fanout ya juu inapunguza I/O kwa kasi kwa kubaki miti inaendelea viwango vichache tu.
Hii ndiyo sababu karibu kila index ya besi ya mahusiano (na mifumo mingi ya faili) imejengwa kwa B+ miti badala ya miti wa utafutaji wa jozi.
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia