B-tree हा एक स्वयं-संतुलित शोध वृक्ष आहे जेथे प्रत्येक नोड अनेक की धारण करतो आणि अनेक मुले आहेत (उच्च fanout). हे वृक्षला उथळ ठेवते, डिस्क रीड्स ची संख्या कमी करते — जो डेटाबेस आणि फाइलसिस्टमला आवश्यक आहे.
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
B+ tree मध्ये, सर्व मूल्य पत्त्यांमध्ये राहतात आणि पत्त्या लिंक केलेली आहेत, तर रेंज स्कॅन पत्त्यांची लिंक केलेली यादी चालते — WHERE age BETWEEN 20 AND 40 सारख्या प्रश्नांसाठी आदर्श.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| ऑपरेशन | वेळ | डिस्क I/O |
|---|---|---|
| शोध | O(log n) | O(उंची) |
| प्रविष्टि / हटवणे | O(log n) | O(उंची) |
| रेंज स्कॅन | O(log n + k) | क्रमिक पत्त्या |
डिस्क आणि SSD प्रवेश मेमरीपेक्षा बराच धीमा आहे, तर महत्वाचा मेट्रिक I/O संख्या आहे, तुलनांचा नाही.
उच्च fanout वृक्षला काही स्तरांच्या खोलीवर ठेवून I/O मोठ्या प्रमाणात कमी करते.
ही कारण आहे की जवळजवळ प्रत्येक संबंधित डेटाबेस इंडेक्स (आणि अनेक फाइलसिस्टम) B+ trees वर बांधले जातात न की बायनरी सर्च ट्रीवर.