Nguồn: PlanetScale Blog
Tóm tắt
PlanetScale xuất bản một deep dive về B-trees và cách chúng được sử dụng trong database indexes. Bài viết giải thích tại sao B-trees — không phải binary search trees hay hash tables — trở thành data structure mặc định cho hầu hết database indexes trong hơn 50 năm qua, từ InnoDB đến PostgreSQL đến RocksDB.
Lý do cốt lõi là B-trees được thiết kế tối ưu cho block storage: chúng minimize số lần đọc đĩa (disk I/O) bằng cách pack nhiều keys vào mỗi node, matching với kích thước page của OS và disk sectors. Trong khi binary search trees có O(log n) operations, constant factor của chúng rất lớn trên disk storage vì mỗi node thường đòi hỏi một disk read riêng biệt.
Bài viết tiếp tục giải thích các variants quan trọng: B+ trees (chỉ lưu data ở leaf nodes, phổ biến nhất trong SQL databases), và các tối ưu hóa hiện đại như fractal tree indexes và LSM trees trong trường hợp write-heavy workloads. Đây là nền tảng kiến thức quan trọng cho bất kỳ engineer nào muốn hiểu query performance và index design.