ต้นไม้ B และต้นไม้ B+ คืออะไร และเหตุใดฐานข้อมูลจึงใช้มัน

ต้นไม้ B คือต้นไม้ค้นหาที่ปรับสมดุลเองซึ่งแต่ละโหนดจะเก็บ คีย์จำนวนมาก และมี ลูกจำนวนมาก (fanout สูง) ซึ่งจะทำให้ต้นไม้มี ความลึกน้อย ลดจำนวน การอ่านจากดิสก์ — นี่คือสิ่งที่ฐานข้อมูลและระบบไฟล์ต้องการ

เหตุใด fanout สูงจึงดีกว่าต้นไม้แบบไบนารี่

Binary BST over 1,000,000 keys -> height ~20  (20 disk seeks)
B-tree, 100 keys/node          -> height ~3   (3 disk seeks)
Each node = one disk block/page read.

โครงสร้าง (B-tree ลำดับ 4)

            [ 17 | 35 ]
           /     |     \
   [4|9|12] [20|28]   [40|50|60]
   each node packs many keys -> few levels

การปรับปรุง B+ tree

ใน B+ tree ค่าทั้งหมดอยู่ในใบไม้ และใบไม้ถูก เชื่อมโยง ดังนั้นการสแกนช่วงจึงเดินผ่านรายการลิงก์ของใบไม้ — เหมาะสำหรับแบบสอบถาม เช่น WHERE age BETWEEN 20 AND 40

internal nodes: keys only (routing)
leaves:  [..]<->[..]<->[..]   <- linked for fast range scans

ความซับซ้อน

เหตุใดจึงมีความสำคัญ

การเข้าถึงดิสก์และ SSD ช้ากว่าหน่วยความจำหลายลำดับขนาด ดังนั้นหน่วยวัดที่สำคัญคือ จำนวน I/O ไม่ใช่การเปรียบเทียบ

Fanout สูงช่วยลด I/O อย่างมากโดยทำให้ต้นไม้มีความลึกเพียงสองสามระดับ

นี่คือเหตุผลว่าทำไมดัชนีฐานข้อมูลเชิงสัมพันธ์เกือบทั้งหมด (และระบบไฟล์จำนวนมาก) จึงสร้างจาก B+ tree แทนต้นไม้ค้นหาแบบไบนารี่