B+ Tree
Ý tưởng cốt lõi: Index = một danh sách đã được sắp xếp (sorted list) + bảng tóm tắt phân cấp giúp nhảy nhanh. Không cần hiểu chi tiết thuật toán insert/delete/rebalance để dùng index tốt.
Hình dung: cuốn từ điển 2000 trang
Muốn tìm từ “performance”:
- Nhìn gáy sách → thấy chữ P nằm khoảng trang 1200
- Lật đến 1200, nhìn header → thấy “PER” bắt đầu từ trang 1245
- Lật đến 1245, scan vài trang → tìm thấy
Chỉ 3 bước thay vì đọc 2000 trang. Index trong database hoạt động y hệt:
- Leaf nodes (tầng dưới cùng) = các trang từ điển, chứa danh sách giá trị đã sorted. Các leaf được liên kết với nhau (linked list) → đọc liên tục theo một hướng rất nhanh (nền tảng của Quét một hướng).
- Internal nodes (các tầng trên) = gáy/header sách, chứa “tóm tắt phạm vi” để nhảy nhanh.
- Kể cả bảng hàng tỷ row, số bước nhảy qua internal nodes chỉ khoảng 3-4 lần (mỗi tầng chia dữ liệu thành hàng trăm/hàng nghìn nhánh) → sức mạnh O(log n).
| Số rows | Số bước nhảy (tree depth) |
|---|---|
| 1,000 | ~2 |
| 1,000,000 | ~3 |
| 1,000,000,000 | ~4 |
→ Hiểu nhầm phổ biến: “Index càng lớn thì query càng chậm” - sai, từ 1 nghìn lên 1 tỷ row chỉ thêm 2 bước nhảy.
Database tự quản lý index hoàn toàn
Mỗi khi INSERT/UPDATE/DELETE, database tự cập nhật tất cả index liên quan:
- Thêm row → tạo entry mới, đặt đúng vị trí sorted
- Xóa row → xóa entry tương ứng
- Sửa row → xóa entry cũ + thêm entry mới (chỉ khi cột trong index bị thay đổi)
→ Dẫn đến trade-off quan trọng: xem Index Write Overhead.
Hạn chế cơ bản của B+ tree
- Chỉ scan được một hướng tại một thời điểm → Quét một hướng
- Gặp range condition thì các cột sau không thu hẹp được nữa → Range Condition phá vỡ Phễu
- Không xử lý được leading wildcard
LIKE '%abc%'→ LIKE và Wildcard, Trigram Index - Dữ liệu đa chiều (toạ độ) cần cấu trúc khác → Spatial Index
Liên quan
- Fast Lookup - thao tác cơ bản nhất của B+ tree
- Composite Index và Nguyên tắc Phễu - index nhiều cột
- Heap Table vs Clustered Index - index gắn với cách lưu trữ bảng
- Prefix Index và Hash Index - khi B+ tree không phù hợp