โครงสร้างข้อมูลแบบ B* - Trees

Bayer และ McCreight ได้พัฒนาโครงสร้างแบบ B-Tree ต่อไปเป็นแบบ Overflow Technique ซึ่งเรียกว่าเป็น B*-Tree เทคนิคใหม่นี้ได้ปรับปรุงวิธีการแทรกข้อมูล โดยการหมุนค่าคีย์ที่ล้นจากโหนดที่เต็มแล้วไปยังโหนดที่เป็นพี่น้องใกล้เคียงกัน (Sibling) คุณสมบัติของ B*-Tree มีดังนี้

1. B*-Tree คือ M-Way Search Tree ซึ่งมีค่าความสูง >= 1 หรือว่างอยู่

2. โหนดที่ Root จะต้องมีโหนดลูกอย่างน้อย 2 Child (ดังนั้นจะมีค่าอย่างน้อย 1 ค่า) และมีค่าโหนดอย่างมากที่สุด

3. โหนดที่ไม่ใช่ Terminal Node ทุกตัว นอกจากโหนดที่เป็น Root จะต้องมีโหนดลูกอย่างน้อย (2m-2)/3 Child (และดังนั้นจะมีค่าข้อมูลย่อย |(2m-1)/3|-1 ค่า

4. ทุก Terminal จะต้องถูกจัดอยู่ในระดับเดียวกัน

5. ทุกโหนดที่ไม่ใช่ Terminal Node ซึ่งค่า k Si มีค่าคีย์เท่ากับ k-1 ค่า



ข้อแตกต่างที่สำคัญระหว่าง B-Tree กับ B*-Tree

ข้อแตกต่างที่สำคัญระหว่าง B-Tree กับ B*-Tree คือ Nodes ภายใน B-Tree (เรียกว่า Interior Node) จะมีอย่างน้อย ½ Tuples ของที่จะจุได้เต็มที่ แต่โหนดภายใน B*-Tree ต้องมีอย่างน้อย 2/3 Tuples ของที่จะจุได้เต็มที่