B-tree index hoạt động thế nào? Vì sao tra cứu nhanh?

Index là cấu trúc dữ liệu có thứ tự giữ giá trị cột đã sắp xếp + con trỏ tới hàng thật. Loại phổ biến nhất là B-tree (cây cân bằng):

• Root → branch → leaf: cây cân bằng nên mọi leaf ở cùng độ sâu; đi từ gốc xuống leaf chỉ vài bước dù bảng lớn.
• Tra cứu là O(log n) thay vì O(n) của quét toàn bảng (full table scan).
• Leaf nối thành danh sách liên kết đôi có thứ tự → hỗ trợ tốt truy vấn khoảng (BETWEEN, >, <) và ORDER BY mà không cần sort lại.

Nhờ có thứ tự, DB "đi cây" để tới đúng vùng dữ liệu thay vì đọc hết bảng. Đánh đổi: tốn dung lượng và làm chậm ghi (mỗi INSERT/UPDATE/DELETE phải cập nhật index).