A B-tree एक self-balancing search tree हो जहाँ प्रत्येक node ले धेरै keys राख्छ र धेरै children छन् (उच्च fanout)। यसले tree को गहिराई कम राख्छ, disk reads को संख्या न्यून गर्छ — जो ठीक डाटाबेस र filesystems लाई चाहिन्छ।
A B-tree एक self-balancing search tree हो जहाँ प्रत्येक node ले धेरै keys राख्छ र धेरै children छन् (उच्च fanout)। यसले tree को गहिराई कम राख्छ, disk reads को संख्या न्यून गर्छ — जो ठीक डाटाबेस र filesystems लाई चाहिन्छ।
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 मा, सबै values leaves मा बस्छन् र leaves linked छन्, त्यसैले range scans ले leaves को linked list हरु हिँडेर जान्छन् — queries जस्तै WHERE age BETWEEN 20 AND 40 को लागि आदर्श।
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Time | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk र SSD को पहुँच memory भन्दा असंख्य गुणा ढिलो छ, त्यसैले मेट्रिक जो महत्त्वपूर्ण छ I/O count, comparisons होइन।
उच्च fanout ले tree को केवल केही स्तर गहिरो राखेर I/O घटाउँछ।
यही कारण हो कि लगभग हरेक relational database index (र धेरै filesystems) B+ trees मा निर्मित छ binary search trees भन्दा।
विस्तृत उत्तरसहित IT अन्तर्वार्ता प्रश्नहरूको पुस्तकालय — जुनियरदेखि सिनियरसम्म।
दान गर्नुहोस्