ต้นไม้ B คือต้นไม้ค้นหาที่ปรับสมดุลเองซึ่งแต่ละโหนดจะเก็บ คีย์จำนวนมาก และมี ลูกจำนวนมาก (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.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
ใน B+ tree ค่าทั้งหมดอยู่ในใบไม้ และใบไม้ถูก เชื่อมโยง ดังนั้นการสแกนช่วงจึงเดินผ่านรายการลิงก์ของใบไม้ — เหมาะสำหรับแบบสอบถาม เช่น WHERE age BETWEEN 20 AND 40
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| การดำเนินการ | เวลา | Disk I/O |
|---|---|---|
| ค้นหา | O(log n) | O(ความสูง) |
| แทรก / ลบ | O(log n) | O(ความสูง) |
| สแกนช่วง | O(log n + k) | ใบไม้ตามลำดับ |
การเข้าถึงดิสก์และ SSD ช้ากว่าหน่วยความจำหลายลำดับขนาด ดังนั้นหน่วยวัดที่สำคัญคือ จำนวน I/O ไม่ใช่การเปรียบเทียบ
Fanout สูงช่วยลด I/O อย่างมากโดยทำให้ต้นไม้มีความลึกเพียงสองสามระดับ
นี่คือเหตุผลว่าทำไมดัชนีฐานข้อมูลเชิงสัมพันธ์เกือบทั้งหมด (และระบบไฟล์จำนวนมาก) จึงสร้างจาก B+ tree แทนต้นไม้ค้นหาแบบไบนารี่
คลังคำถามสัมภาษณ์งาน IT พร้อมคำตอบโดยละเอียด — ตั้งแต่ระดับ Junior ถึง Senior
บริจาค