Fast Lookup (Nguyên tắc 1: Tra cứu nhanh)

Thao tác cơ bản nhất của index: tìm một giá trị cụ thể gần như tức thì bằng cách nhảy qua các tầng internal node, thay vì scan từ đầu đến cuối.

SELECT * FROM movies WHERE release_year = 2019;

Index summary (internal nodes):
[... | 2015-2017 | 2018-2020 | 2021-2023 | ...]
                      ↓
Leaf nodes:  [2018 | 2018 | 2019 | 2019 | 2019 | 2020 | 2020]
                            ▲ Database nhảy thẳng đến đây!

Database không đọc qua 2015, 2016, 2017… - nó nhảy thẳng đến khu vực 2018-2020 trong index summary, rồi tìm chính xác 2019 trong leaf nodes.

Hiểu nhầm phổ biến: “Index càng lớn thì query càng chậm”

Chưa chắc! Index là cấu trúc cây, không phải danh sách phẳng. Mỗi tầng internal node chia dữ liệu thành hàng trăm nhánh:

Số rows	Số bước nhảy
1,000	~2
1,000,000	~3
1,000,000,000	~4

Từ 1 nghìn lên 1 tỷ row chỉ thêm 2 bước nhảy - sức mạnh O(log n). Index đã được tối ưu hàng chục năm cho đúng use case này: đừng lo về kích thước.

Điều kiện để Fast Lookup hoạt động

• Điều kiện equality (=, IN, IS NULL) trên cột đầu của index
• Cột không bị biến đổi bởi hàm/phép tính → Column Transformation
• Kiểu dữ liệu khớp → Type Mismatch và Implicit Cast

Liên quan

• B+ Tree - cấu trúc cho phép fast lookup
• Quét một hướng - nguyên tắc 2, bước tiếp theo sau khi lookup
• Composite Index và Nguyên tắc Phễu - fast lookup trên nhiều cột