Nguồn: PlanetScale Blog
Tóm tắt
B-tree là cấu trúc dữ liệu cân bằng tự động, được sử dụng rộng rãi để triển khai index trong database. Mỗi node của B-tree chứa keys và values: node gốc và node nội bộ dùng để dẫn đường tìm kiếm, còn node lá chứa con trỏ đến dữ liệu thực. Tính chất tự cân bằng đảm bảo độ phức tạp tìm kiếm luôn là O(log n).
Trong MySQL (InnoDB), primary key luôn là clustered index — nghĩa là dữ liệu được lưu vật lý theo thứ tự của index, và node lá chứa row data thực sự. Ngược lại, secondary index (non-clustered) chỉ lưu các cột được đánh index cùng con trỏ đến primary key, dẫn đến quá trình “double lookup” khi truy vấn. Covering index là trường hợp đặc biệt giúp tránh double lookup bằng cách đưa tất cả cột cần thiết vào index.
Bài viết cũng giải thích các trường hợp index không được sử dụng: implicit type conversion (query string trên cột integer), áp dụng hàm lên cột được đánh index (LOWER(name)), và index trên cột có cardinality thấp (như boolean). Composite index cũng tuân theo quy tắc prefix — index (name, email) có thể dùng cho filter name hoặc name + email, nhưng không dùng được khi chỉ filter email.
Index có chi phí ghi: mỗi lần INSERT, UPDATE, DELETE đều phải cập nhật tất cả index liên quan. Ngoài B-tree, các cấu trúc thay thế gồm Hash index (chỉ phù hợp exact match) và LSM Tree (tối ưu cho write-heavy workloads như RocksDB, Cassandra).