কম্পিউটার সায়েন্সে একটি m-এরি ট্রি হল নোডের একটি সংগ্রহ যা সাধারণত হায়ারার্কিক্যালি নিচের রূপে রিপ্রেজেন্ট করা হয়:
- ট্রি রুট নোড থেকে শুরু হয়।
- ট্রির প্রতিটি নোড তার চাইল্ড নোডগুলোর পয়েন্টারের একটি লিস্ট ধারণ করে।
- চাইল্ড নোডের সংখ্যা m-এর চেয়ে কম বা সমান।
এম-এরি ট্রির একটি সাধারণ রিপ্রেজেন্টেশন চাইল্ড সংরক্ষণের জন্য m রেফারেন্স (বা পয়েন্টার) এর একটি অ্যারে ব্যবহার করে (মনে রাখবেন m চাইল্ডের সংখ্যার একটি আপার বাউন্ড)।
এম-ওয়ে সার্চ ট্রি
ক. খালি হতে পারে অথবা
খ. একটি রুট ধারণ করতে পারে যাতে b (১≤b≤m) সংখ্যক কী, kᵦ, এবং সাব-ট্রির একটি সেট, Tₐ (a = 0..b), থাকে, যাতে
- যদি k, T₀-এ একটি কী হয়, তবে k ≤ k₁
- যদি k, Tₐ-এ একটি কী হয় (0
- যদি k, Tᵦ-এ একটি কী হয়, তবে k > kᵦ এবং
- সব Tₐ নন-এম্পটি m-ওয়ে সার্চ ট্রি হবেন অথবা সব Tₐ খালি হবেন
m-এরি ট্রির ছবি
n নোড সম্পন্ন একটি কমপ্লিট m-এরি ট্রির হাইট হল ceiling(logₘn)।
অর্ডার m-এর একটি B-ট্রি হল একটি m-ওয়ে ট্রি যাতে
ক. সব লীফ একই লেভেলে থাকবে এবং
খ. রুট এবং লীফ বাদে সব নোডে কমপক্ষে m/2 এবং সর্বোচ্চ m চাইল্ড থাকবে। রুটে কমপক্ষে ২ এবং সর্বোচ্চ m চাইল্ড থাকবে।
