นิยาม
m-ary Tree คือชุดของโหนดที่จัดแสดงแบบลำดับชั้น ดังนี้:
- เริ่มต้นที่ รูท (Root Node)
- แต่ละโหนดเก็บรายการ pointer ชี้ไปยังโหนดลูก (Child Nodes)
- จำนวนโหนดลูก ≤ m
การแทนค่าทั่วไป
ใช้ อาร์เรย์ของ m references (หรือ pointers) เพื่อเก็บลูก (m เป็นขีดจำกัดบนของจำนวนลูก)
m-way Search Tree
เป็นได้สองแบบ:
- ว่างเปล่า (Empty)
- ประกอบด้วยรูทที่มี b คีย์ (1 ≤ b ≤ m) คือ k₁, k₂, ..., k_b และชุดซับทรี Tₐ (a = 0..b) ที่ทำให้:
- ถ้า k เป็นคีย์ใน T₀ → k ≤ k₁
- ถ้า k เป็นคีย์ใน Tₐ (0 < a < b) → kₐ ≤ k ≤ kₐ₊₁
- ถ้า k เป็นคีย์ใน T_b → k > k_b
- ทุก Tₐ เป็น m-way search trees ที่ไม่ว่าง ทั้งหมด หรือว่างทั้งหมด
ความสูงของ m-ary Tree สมบูรณ์
ความสูงของ Complete m-ary Tree ที่มี n โหนดคือ ceiling(logₘ n)
B-Tree ของอันดับ m
เป็น m-way tree ที่:
- ใบ (Leaves) ทั้งหมดอยู่ระดับเดียวกัน
- โหนดทั้งหมดยกเว้นรูทและใบ มีลูกอย่างน้อย m/2 และสูงสุด m ลูก รูทมีลูกอย่างน้อย 2 และสูงสุด m ลูก
