SQL Index Under the Hood (Part 2): Làm sao Database tìm được 1 dòng giữa 10 triệu records?

Ở Part 1, ta đã biết: không có Index → Database chỉ có một cách — đọc lần lượt từng Page. Ổn với vài nghìn dòng. Nhưng 10 triệu dòng thì sao?

Ví dụ: tìm người trong danh bạ

• Cách 1 – không sắp xếp: đọc từ Aaron → Adam → Alex → ... → Zoe. Nếu người cần tìm ở cuối, gần như phải đọc hết.

• Cách 2 – đã sắp xếp: mở thẳng chữ N → Nguyễn → Nguyễn Anh → Nguyễn Hoàng... Nhanh hơn nhiều.

Database làm điều tương tự — nhưng bằng một cấu trúc tên là B-Tree. Nghe đáng sợ, nhưng bạn dùng nó mỗi ngày.

Mental model: sơ đồ trung tâm thương mại

Vào Aeon Mall tìm Uniqlo, bạn không chạy khắp nơi — bạn nhìn Directory: Tầng 1 → Tầng 2 → Fashion → Uniqlo.

B-Tree hoạt động y hệt: nó không đưa bạn dữ liệu ngay, nó chỉ chỉ đúng hướng để đi tiếp.

Vấn đề nếu không có "đường tắt"

Nếu dữ liệu chỉ là một chuỗi nối tiếp (1 → 2 → 3 → ... → 10.000.000), tìm số 8.200.315 nghĩa là đi từng bước — không khác gì Full Scan.

B-Tree ra đời: xây thêm các tầng

Thay vì một đường thẳng, B-Tree chia dữ liệu thành các nhánh:

                 Root
              3,000,000
          /              \
     <3,000,000      >3,000,000

Tìm 8.200.315? Database biết ngay: đi phải. Cây càng sâu, khoảng tìm kiếm càng thu hẹp, đến khi chỉ còn đúng 1 Page.

🔍 Vậy chính xác thì B-Tree được tổ chức như thế nào?

Vài điểm quan trọng mà ví dụ ở trên chưa nói hết:

1. Mỗi node chứa nhiều "key", không chỉ một Trong thực tế, một node của B-Tree không chỉ giữ đúng 1 giá trị như 3,000,000 — nó có thể chứa hàng trăm giá trị được sắp xếp sẵn, mỗi giá trị đi kèm một con trỏ trỏ đến nhánh con phù hợp. Đây là lý do B-Tree có fan-out (số nhánh con) rất cao, thường vài trăm nhánh mỗi tầng.

2. Vì sao fan-out cao lại quan trọng? Fan-out càng cao, cây càng "lùn và rộng" thay vì "cao và mảnh". Với fan-out ~300, chỉ cần 4 tầng là đủ để đánh chỉ mục hơn 8 tỷ dòng dữ liệu. Đó là lý do dù bảng có 10 triệu hay 100 triệu dòng, số lần đọc để tìm một giá trị vẫn chỉ dao động quanh 3-5 lần — gần như không đổi.

3. "B" trong B-Tree nghĩa là Balanced (cân bằng) Dù bạn insert hay delete dữ liệu liên tục, B-Tree luôn tự tổ chức lại để mọi nhánh lá (leaf) nằm ở cùng một độ sâu. Không có chuyện một nhánh sâu 3 tầng, nhánh khác sâu 10 tầng. Điều này đảm bảo thời gian tìm kiếm luôn ổn định, bất kể bạn tìm giá trị nào.

4. Leaf node không chỉ để dừng lại — chúng được nối với nhau Các leaf node trong B-Tree (thực ra PostgreSQL dùng biến thể B+Tree) được liên kết thành một danh sách liên kết ngang. Nhờ vậy, khi bạn query dạng range như WHERE id BETWEEN 100 AND 200, Database chỉ cần tìm đến leaf đầu tiên rồi đi ngang sang các leaf kế tiếp, thay vì phải quay lại Root mỗi lần.

5. Leaf node lưu gì? Đây là điểm hay bị hiểu lầm: leaf node không lưu toàn bộ dòng dữ liệu, mà chỉ lưu giá trị được index (ví dụ email) kèm theo một con trỏ (CTID trong PostgreSQL) trỏ đến vị trí thật của dòng đó trong bảng. Đây chính là lý do bước tiếp theo — nhảy từ Index sang bảng thật — luôn cần thêm một bước riêng (mình sẽ nói kỹ ở phần dưới).

Tóm gọn: B-Tree không phải là "cây nhị phân đơn giản" như trong sách giáo trình — nó được thiết kế đặc biệt để tối ưu số lần đọc Page từ đĩa, với node rộng, cây thấp, và luôn cân bằng.

Điều kỳ diệu: với 10 triệu dòng, Full Scan có thể đọc 10 triệu dòng — B-Tree chỉ cần 4–5 lần đọc (Root → Internal → Internal → Leaf). Index nhanh không phải vì CPU khỏe hơn, mà vì đọc ít hơn rất nhiều.

Hiểu lầm thường gặp

Nhiều người nghĩ B-Tree tìm xong (Root → Leaf) là kết thúc. Sai. Đó mới là Index Scan. Sau đó Database còn phải nhảy sang bảng thật để lấy dữ liệu và trả về — đây chính là nguồn gốc của không ít query chậm (hẹn ở Part 3).

Hands-on Lab

Không có index

Tạo index

CREATE INDEX idx_customer_email ON customers(email);

EXPLAIN ANALYZE
SELECT * FROM customers WHERE email='customer_999999@gmail.com';

Lần này bạn sẽ thấy Index Scan thay vì Seq Scan.

Benchmark tham khảo

(Số liệu minh họa xu hướng — nên tự chạy EXPLAIN (ANALYZE, BUFFERS) trên máy bạn để lấy số thật cho bài viết)

Điểm mấu chốt: Seq Scan tăng gần tuyến tính theo dữ liệu; Index Scan gần như không đổi.

Production Tip

Trước khi tạo Index, luôn tự hỏi:

1. Query nào đang chậm?

2. Nó lọc theo cột nào?

3. Mỗi lần trả về bao nhiêu dòng?

Tổng kết

• ✅ Index không chứa toàn bộ dữ liệu bảng — nó là bản đồ

• ✅ B-Tree là cây cân bằng, fan-out cao, nên chỉ cần vài lần đọc dù dữ liệu lớn cỡ nào

• ✅ Leaf node chỉ lưu giá trị index + con trỏ, không lưu cả dòng dữ liệu

• ✅ Nhưng Index Scan xong vẫn cần quay lại bảng thật để lấy dữ liệu

Part 3 – The Optimizer: Vì sao PostgreSQL đôi khi cố tình không dùng Index dù nó nhanh hơn? Query Planner nghĩ gì khi chọn Seq Scan thay vì Index Scan?