B+Tree
Data structure มาตรฐานที่เกือบทุก database ใช้สำหรับ index — ปรับปรุงจาก B-Tree โดยเก็บ values เฉพาะใน leaf nodes และ link leaf nodes เข้าด้วยกัน ทำให้ range query เร็วมาก
B-Tree (ต้นกำเนิด)
- มี degree M (จำนวน child node สูงสุด)
- แต่ละ node มีไม่เกิน M-1 elements
- แต่ละ element =
(key, value)โดย value มักเป็น pointer ไปยัง row - 1 node = 1 disk page ในระบบ DB จริง (Postgres 8KB, MySQL 16KB)
ข้อจำกัดของ B-Tree
- Internal nodes ใหญ่ — เก็บ value ด้วย → fit elements ได้น้อย → tree สูง → IO มาก
- Range query แย่ — ต้อง traverse หลาย subtree เพราะ leaf ไม่เชื่อมกัน
B+Tree — 2 การปรับปรุง
- Internal nodes เก็บแค่ key (ไม่เก็บ value) → เล็กกว่ามาก → fit ใน memory ง่าย → tree เตี้ยกว่า
- Values อยู่ใน leaf nodes เท่านั้น + leaf nodes linked list ต่อกัน
→ Range query: หา leaf แรก → walk linked list → เร็วมาก
B+Tree ใน MySQL vs PostgreSQL
| ด้าน | MySQL (InnoDB) | PostgreSQL |
|---|---|---|
| Primary index | Clustered — leaf เก็บ PK + row data ทั้งแถว | ชี้ไป heap (tuple id) |
| Secondary index ชี้ไป | Primary key → ต้อง 2 lookups | Tuple id → 1 lookup |
| UPDATE ผลต่อ secondary | ไม่ต้อง update (ถ้า PK ไม่เปลี่ยน) | ต้อง update ทุก index (write amplification) |
| ไม่มี heap แยก | ตาราง = primary index ตรง ๆ | มี heap แยกจาก index |
ทำไม B+Tree ถึงเร็ว
- Page size 8-16KB → fit keys ได้เยอะ → tree มักสูงแค่ 3-4 ระดับ
- 3 ระดับ = 3 IO operations = หาข้อมูลในล้านแถวได้
- Internal nodes ที่ใช้บ่อย cache ใน buffer pool → IO จริงแค่ leaf
Key Points
- B+Tree = B-Tree + internal nodes เก็บแค่ key + leaf nodes linked list
- Range query เร็ว เพราะ leaf linked → walk ต่อกันได้
- MySQL ใช้ clustered index (PK + data ใน leaf), Postgres ใช้ heap + index แยก
- Tree สูงแค่ 3-4 ระดับ → หาข้อมูลในล้านแถวใช้แค่ 3-4 IO
Related
- Database Indexing — B+Tree เป็น data structure หลักของ index
- Database Internals — Pages, IO ที่ B+Tree ช่วยลด
- Database Engines — InnoDB (B+Tree), RocksDB (LSM-Tree) เลือกตาม workload
- MySQL — Clustered index ใช้ B+Tree
- PostgreSQL — Heap-organized + B+Tree index แยก