यहाँ हम देखेंगे कि B-ट्री (B-Trees) क्या हैं। B-ट्री विशेष m-मार्ग खोज ट्री (m-way search tree) हैं। इनका व्यापक रूप से डिस्क एक्सेस (disc access) के लिए उपयोग किया जा सकता है। क्रम m का B-ट्री, अधिकतम m-1 कुंजियाँ और m बच्चे रख सकता है। यह एक ही नोड में बड़ी संख्या में तत्वों को संग्रहीत कर सकता है। इसलिए ऊंचाई अपेक्षाकृत छोटी होती है। यह B-ट्री का एक बड़ा लाभ है।
B-ट्री में एक m-मार्ग ट्री के सभी गुण होते हैं। इसके कुछ अन्य गुण हैं:
B-ट्री में प्रत्येक नोड अधिकतम m बच्चे रखेगा
रूट और पत्तियों को छोड़कर प्रत्येक नोड कम से कम m/2 बच्चे रख सकता है
रूट नोड्स में कम से कम दो बच्चे होने चाहिए।
सभी पत्ती नोड्स समान स्तर पर होने चाहिए
B-ट्री का उदाहरण
यह खोज, सम्मिलन, विलोपन जैसे मूल संक्रियाओं का समर्थन करता है। प्रत्येक नोड में, आइटम क्रमबद्ध होंगे। स्थिति i पर तत्व के पहले और बाद में बच्चा होता है। इसलिए पहले क्रमबद्ध बच्चे छोटे मान रखेंगे, और दाएं मौजूद बच्चे बड़े मान रखेंगे।
