เราจะมาดูกันว่าบีทรีคืออะไร B-Trees เป็นต้นไม้ค้นหา m-way เฉพาะทาง สามารถใช้กันอย่างแพร่หลายสำหรับการเข้าถึงแผ่นดิสก์ B-tree ของคำสั่ง m สามารถมีคีย์ m-1 สูงสุดและ m ลูกได้ นี้สามารถเก็บองค์ประกอบจำนวนมากในโหนดเดียว ความสูงจึงค่อนข้างเล็ก นี่เป็นข้อดีอย่างหนึ่งของ B-Trees
B-Tree มีคุณสมบัติทั้งหมดของต้นไม้ m-way เพียงต้นเดียว มีคุณสมบัติอื่นๆ บ้าง
-
ทุกโหนดใน B-Tree จะรองรับลูกได้สูงสุด m
-
ทุกโหนดยกเว้นรูทและใบ สามารถเก็บลูกอย่างน้อย m/2 ได้
-
โหนดรูทต้องมีลูกอย่างน้อยสองคน
-
โหนดปลายสุดทั้งหมดต้องมีระดับเดียวกัน
ตัวอย่าง B-Tree
รองรับการทำงานพื้นฐาน เช่น การค้นหา การแทรก การลบ ในแต่ละโหนด รายการจะถูกจัดเรียง องค์ประกอบที่ตำแหน่ง i มีลูกก่อนและหลัง ดังนั้นเด็กที่ป่วยก่อนจะมีค่าน้อยกว่า และเด็กที่อยู่ทางขวาจะมีค่ามากกว่า
