B-tree là một cây tìm kiếm tự cân bằng trong đó mỗi node chứa nhiều key và có nhiều con (fanout — độ phân nhánh cao). Điều này giữ cây nông (shallow), giảm thiểu số lần đọc đĩa (disk read) — chính là điều database và filesystem cần.
Binary BST trên 1.000.000 key -> chiều cao ~20 (20 lần seek đĩa)
B-tree, 100 key/node -> chiều cao ~3 (3 lần seek đĩa)
Mỗi node = một lần đọc disk block/page.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
mỗi node nhồi nhiều key -> ít tầng
Trong một B+ tree, tất cả giá trị nằm trong các leaf và các leaf được liên kết, nên việc quét khoảng (range scan) đi qua một linked list của các leaf — lý tưởng cho các truy vấn như WHERE age BETWEEN 20 AND 40.
node trong: chỉ key (định tuyến)
leaf: [..]<->[..]<->[..] <- liên kết để quét khoảng nhanh
| Thao tác | Thời gian | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | leaf tuần tự |
Truy cập đĩa và SSD chậm hơn bộ nhớ vài bậc độ lớn, nên thước đo quan trọng là số lần I/O, không phải số lần so sánh.
Fanout cao cắt giảm I/O bằng cách giữ cây chỉ vài tầng sâu.
Đây là lý do gần như mọi index database quan hệ (và nhiều filesystem) được xây dựng trên B+ tree thay vì binary search tree.