Multiway Tree คืออะไร?
Multiway Tree = Tree ที่ Node มีลูกได้ > 2 ตัว
ถ้าสูงสุด m Children → เรียกว่า Multiway Tree of Order m (m-way Tree)
Node ใน m-way Tree ประกอบด้วย: m-1 Key Fields + Pointers ไป Children m ตัว
Multiway Search Tree of Order m (m-way Search Tree)
กำหนด Constraint/Order บน Keys ในแต่ละ Node เพื่อการ Process ง่ายขึ้น
By Definition: m-way Search Tree ต้อง Satisfy:
- Node แต่ละตัวมี m Children และ m-1 Key Fields
- Keys ใน Node เรียง Ascending Order
- Keys ใน First j Children < j-th Key
- Keys ใน Last m-j Children > j-th Key
ตัวอย่าง m=5 (5-way Search Tree)
Node มี 4 Keys: k₁ < k₂ < k₃ < k₄
5 Children: C₀, C₁, C₂, C₃, C₄
C₀: Keys < k₁
C₁: k₁ < Keys < k₂
C₂: k₂ < Keys < k₃
C₃: k₃ < Keys < k₄
C₄: Keys > k₄
สรุป
Multiway Search Trees = Generalization ของ BST (2-way)
ฐานของ B-Trees, B+ Trees, (a,b)-Trees
ลด Height → ลด Disk I/O สำคัญสำหรับ Database/File Systems
