Đã đăng vào khoảng 17 giờ trước 31 phút đọc

B-Tree Index – Database sẽ đọc Data từ Disk như thế nào?

B-Tree Index: Vì sao Database tìm kiếm hàng triệu dòng chỉ mất vài mili-giây?

Một bảng có 10 triệu dòng, nhưng database vẫn có thể tìm đúng một đơn hàng trong vài mili-giây. B-Tree Index làm được điều đó không phải vì database quét 10 triệu dòng nhanh hơn, mà vì nó giúp database tránh đọc gần như toàn bộ số dòng ấy.

Muốn hiểu vì sao B-Tree hiệu quả, chúng ta không nên bắt đầu từ hình vẽ một cái cây. Cần bắt đầu từ nơi dữ liệu thật sự nằm: disk. Đọc disk chậm hơn truy cập RAM nhiều bậc độ lớn, còn database lại đọc dữ liệu theo từng page. Vì vậy, câu hỏi quyết định không phải chỉ là “cần bao nhiêu phép so sánh?”, mà là:

Để tìm được một row, database phải đọc bao nhiêu page từ storage?

Bài viết sẽ lần lượt giải bài toán đó bằng ba phương án: Full Table Scan, Binary Search Tree và cuối cùng là B-Tree.

Tìm một dòng trong bảng 10 triệu bản ghi

Giả sử chúng ta có bảng orders với 10 triệu đơn hàng và cần chạy truy vấn:

SELECT *
FROM orders
WHERE order_id = 825731;

Nhìn từ phía ứng dụng, đây là một yêu cầu rất nhỏ: nhập một mã đơn hàng và nhận về một row.

Nhưng database phải giải quyết nhiều câu hỏi hơn:

Dữ liệu của bảng nằm ở đâu?
Cần đọc bao nhiêu phần của bảng?
Làm sao biết page nào chứa order_id = 825731?
Nếu chưa có dữ liệu trong RAM, phải chờ storage bao lâu?
Sau khi tìm thấy key trong index, có phải đọc thêm page của bảng không?

Chúng ta sẽ giữ nguyên truy vấn này để so sánh ba cách tìm kiếm:

Không có index: quét toàn bộ bảng.
Dùng một Binary Search Tree theo kiểu cấu trúc trong RAM.
Dùng B-Tree Index được thiết kế quanh page I/O.

Vì sao làm việc với Disk lại chậm?

CPU, RAM và Disk không cùng một thế giới tốc độ

CPU có thể thực hiện rất nhiều phép tính trong thời gian database chờ một lần đọc storage. RAM chậm hơn cache của CPU, nhưng vẫn nhanh hơn disk nhiều bậc độ lớn.

Để hình dung, hãy dùng một bộ số chỉ mang tính minh họa:

Thao tác	Độ trễ giả định
Truy cập RAM	100 nano-giây
Random read trên NVMe SSD	100 micro-giây
Random read trên HDD	5 mili-giây

Các giá trị thực tế thay đổi theo phần cứng, queue depth, hệ điều hành, controller, tải hệ thống và kiểu workload. Mục đích của bảng không phải benchmark thiết bị, mà để cho thấy chênh lệch về bậc độ lớn:

100 micro-giây = 1.000 × 100 nano-giây
5 mili-giây     = 50.000 × 100 nano-giây

Nếu coi một lần truy cập RAM kéo dài 1 giây trong một phép so sánh tưởng tượng, thì một random read 100 micro-giây sẽ tương đương khoảng 16 phút 40 giây. Một lần chờ 5 mili-giây tương đương gần 14 giờ.

Đây là lý do tối ưu database không thể chỉ đếm phép so sánh của thuật toán. Một phép so sánh key trong RAM rất rẻ; một page miss buộc database chạm storage mới thật sự đắt.

Một datasheet HDD của Seagate, chẳng hạn, ghi độ trễ quay trung bình 4,16 ms, chưa tính toàn bộ seek time và các tầng xử lý khác. Ở phía SSD, Amazon mô tả dòng EBS io2 Block Express có độ trễ ổn định dưới một mili-giây. Hai con số này không dùng để so sánh trực tiếp hai sản phẩm, nhưng chúng cho thấy storage hiện đại vẫn được nói đến bằng micro-giây hoặc mili-giây, trong khi RAM thường được hình dung ở thang nano-giây.

Sequential I/O và Random I/O

Không phải mọi lần đọc disk đều có chi phí giống nhau.

Sequential I/O đọc các vùng dữ liệu nằm gần nhau theo thứ tự. Storage có thể truyền một luồng dữ liệu lớn với throughput cao, còn hệ điều hành và database cũng có thể đọc trước các block kế tiếp.

Random I/O liên tục nhảy giữa các vị trí khác nhau. Với HDD, đầu đọc phải di chuyển và chờ phiến đĩa quay đến đúng vị trí. SSD không có bộ phận cơ học, nhưng mỗi request vẫn đi qua controller, flash translation layer, queue và các tầng phần mềm.

Vì vậy, một nghịch lý thường xuất hiện:

Full Table Scan đọc rất nhiều page, nhưng phần lớn là đọc tuần tự.
Một cấu trúc cây có thể đọc ít page hơn, nhưng mỗi bước lại nhảy sang một page khác.

Một index phù hợp phải giảm đủ mạnh số page cần đọc để bù cho đặc tính random access.

Database đọc Page, không đọc riêng từng Row

Page là đơn vị I/O cơ bản

Khi ứng dụng yêu cầu một row 200 byte, database thường không bảo storage trả đúng 200 byte đó. Nó đọc page chứa row.

Page là đơn vị cố định mà database dùng để tổ chức dữ liệu trên storage và trao đổi dữ liệu với buffer pool. Một page có thể chứa:

Nhiều row của bảng
Nhiều entry của index
Header và metadata quản lý
Vùng trống dành cho thay đổi sau này

Kích thước page phụ thuộc hệ quản trị và cấu hình. Tài liệu PostgreSQL cho biết table và index được lưu thành các mảng page có kích thước cố định, thường là 8 KB. Các database khác có thể dùng kích thước khác, nhưng tư duy chung vẫn giống nhau: I/O diễn ra theo block/page, không theo từng giá trị đơn lẻ.

Vì sao không đọc riêng từng Row?

Đọc từng row riêng lẻ sẽ tạo ra quá nhiều request nhỏ. Gom nhiều row hoặc index entry vào một page giúp:

Tận dụng tốt hơn mỗi lần truy cập storage
Giảm số lượng I/O request
Đọc trước các dữ liệu nằm gần nhau
Cache dữ liệu theo đơn vị dễ quản lý
Duy trì metadata, logging và cơ chế đồng thời

Đổi lại, dù chỉ cần một row, database vẫn phải đưa cả page chứa row đó vào RAM. Vì vậy, thiết kế index phải trả lời được câu hỏi: page nào đáng đọc?

Bảng 10 triệu dòng tương đương bao nhiêu Page?

Hãy tạo một mô hình đơn giản:

10.000.000 row × 200 byte/row
= 2.000.000.000 byte
≈ 2 GB dữ liệu thô

Nếu dùng page 8 KB:

2.000.000.000 / 8.192
≈ 244.141 page

Đây là con số lý tưởng hóa. Dữ liệu thực tế còn có row header, page header, alignment, khoảng trống, phiên bản row, fragmentation, index và nhiều metadata khác.

Điều quan trọng là quy mô: một truy vấn chỉ cần một row có thể đứng trước một bảng gồm khoảng hàng trăm nghìn page.

Full Table Scan làm việc với Disk như thế nào?

Hành trình của một lần quét bảng

Nếu không có index phù hợp, database có thể thực hiện Full Table Scan:

Yêu cầu page đầu tiên của bảng.
Kiểm tra page đã nằm trong buffer pool chưa.
Nếu chưa có, đọc page từ storage vào RAM.
Kiểm tra từng row trong page.
Chuyển sang page tiếp theo.
Lặp lại cho đến hết vùng dữ liệu cần quét.

Với truy vấn không có LIMIT và không có cấu trúc cho phép chứng minh tính duy nhất, database không thể dừng chỉ vì đã gặp một row phù hợp. Nó còn phải kiểm tra xem phía sau có kết quả khác hay không.

Full Table Scan chậm đến mức nào?

Tiếp tục dùng mô hình 2 GB. Nếu storage cung cấp tốc độ đọc tuần tự thực tế 500 MB/s:

2.000 MB / 500 MB/s ≈ 4 giây

Đây mới là thời gian truyền dữ liệu lý thuyết. Truy vấn còn có thể tốn chi phí:

Đưa page qua hệ điều hành và buffer manager
Kiểm tra visibility theo cơ chế transaction
Đọc row header
Đánh giá điều kiện order_id = 825731
Xử lý compression nếu có
Tranh chấp tài nguyên với workload khác

Nếu dữ liệu đã nằm trong RAM, truy vấn sẽ nhanh hơn đáng kể. Nếu database có thể parallel scan, thời gian cũng có thể giảm. Ngược lại, bảng thực tế lớn hơn 2 GB, storage đang bận hoặc dữ liệu phân mảnh sẽ làm thời gian tăng.

Phép tính 4 giây không phải một lời dự đoán cho mọi hệ thống. Nó chỉ cho thấy sự vô lý về mặt công việc: để lấy một row vài trăm byte, database có thể phải đọc khoảng 2 GB dữ liệu.

Nhưng Full Table Scan không phải lúc nào cũng xấu

Full Table Scan có một lợi thế: các page thường được đọc theo thứ tự. Nếu truy vấn cần 70% bảng, việc đọc tuần tự toàn bảng có thể rẻ hơn:

Đi qua index để lấy hàng triệu con trỏ.
Từ mỗi con trỏ lại tìm đến data page.
Đọc rất nhiều page theo thứ tự rời rạc.

Optimizer có thể chọn Full Table Scan khi:

Bảng nhỏ
Truy vấn trả về phần lớn row
Điều kiện có độ chọn lọc thấp
Data page đã nằm trong RAM
Sequential scan rẻ hơn hàng loạt random lookup

Vấn đề của Full Table Scan chỉ trở nên rõ ràng khi ứng dụng cần rất ít row nhưng database vẫn phải đọc phần lớn bảng.

Binary Search có phải lời giải?

Từ 10 triệu phép kiểm tra xuống khoảng 24 bước

Nếu 10 triệu key nằm trong một mảng đã sắp xếp, Binary Search có thể liên tục chia đôi vùng tìm kiếm:

log₂(10.000.000) ≈ 23,25

Nói cách khác, về lý thuyết chỉ cần khoảng 24 lần so sánh để xác định một key.

So với việc kiểm tra 10 triệu row, đây là bước tiến rất lớn. Nhưng database khó duy trì toàn bộ bảng như một mảng liên tục đã sắp xếp:

Row có kích thước khác nhau.
INSERT phải chèn vào giữa thứ tự hiện có.
UPDATE có thể thay đổi vị trí logic của row.
DELETE để lại khoảng trống hoặc phiên bản dữ liệu cũ.
Transaction và MVCC khiến một key có thể liên quan đến nhiều phiên bản row.

Database cần một cấu trúc riêng có thứ tự nhưng vẫn cho phép dữ liệu thay đổi. Binary Search Tree có vẻ là ứng viên tự nhiên tiếp theo.

Vì sao Binary Search Tree vẫn không hợp với Disk?

Binary Search Tree rất hợp với RAM

Một node của Binary Search Tree thường chứa:

Một key
Con trỏ đến node bên trái
Con trỏ đến node bên phải

Sau mỗi lần so sánh:

Key cần tìm nhỏ hơn: đi trái.
Key cần tìm lớn hơn: đi phải.
Key bằng nhau: đã tìm thấy.

Nếu cây cân bằng, 10 triệu key cần khoảng 24 tầng. Trong RAM, việc đi qua 24 con trỏ thường rất rẻ.

Trên Disk, mỗi con trỏ có thể dẫn đến một Page khác

Hãy hình dung một Binary Search Tree dạng node-pointer được lưu ngây thơ trên storage. Node tiếp theo có thể nằm ở bất kỳ page nào:

Root page
    |
    v  random read
Node page
    |
    v  random read
Node page
    |
   ...

Nếu mỗi tầng gây một page miss, tìm kiếm có thể cần gần 24 random page read.

Lấy con số HDD 4,16 ms chỉ để minh họa phần độ trễ quay:

24 × 4,16 ms ≈ 100 ms

Con số đó còn chưa cộng đầy đủ seek time, transfer time và các tầng phần mềm. Trên SSD, mỗi random read nhanh hơn nhiều, nhưng 24 page miss nối tiếp vẫn tạo ra độ trễ vì bước sau phụ thuộc kết quả của bước trước.

Đây là điểm quan trọng: O(log n) chưa đủ để kết luận một cấu trúc phù hợp với disk. Cần nhìn vào cơ số của logarithm và số lần I/O nối tiếp.

Một Page 8 KB nhưng chỉ nhận được quyết định trái hoặc phải

Vấn đề thứ hai là mức độ tận dụng page.

Giả sử database đọc 8 KB nhưng node logic chỉ cung cấp một key và hai con trỏ. Sau khi trả chi phí cho cả page, thông tin hữu ích mà database nhận được chỉ là:

Đi trái hay đi phải?

Page còn có thể chứa các node khác, nhưng một bố cục node-pointer thông thường không đảm bảo những node cần cho đường tìm kiếm tiếp theo nằm cùng page. Locality kém khiến database liên tục nhảy giữa các page.

Cấu trúc dành cho disk cần tận dụng một lần đọc page để đưa ra lựa chọn giữa nhiều nhánh, không chỉ hai nhánh.

Cây mất cân bằng còn tệ hơn

Một Binary Search Tree thông thường có thể suy biến nếu key được chèn theo thứ tự:

Khi đó, tìm kiếm suy giảm từ O(log n) thành O(n).

AVL Tree hoặc Red-Black Tree có thể giữ cây cân bằng, nhưng chúng vẫn là cây ít nhánh. Với storage, cây vẫn sâu hơn cần thiết và mỗi page chưa được tận dụng để chứa thật nhiều mốc điều hướng.

B-Tree: Cấu trúc cây được thiết kế quanh Page I/O

Một Node chứa nhiều Key

B-Tree thay đổi câu hỏi từ:

Sau khi đọc node này, đi trái hay đi phải?

thành:

Sau khi đọc page này, chọn một trong hàng trăm khoảng giá trị nào?

Một internal node có dạng khái niệm:

       [100 | 200 | 300 | 400]
       /     |     |     |     \
   <100  100–199 200–299 300–399  >=400

Trong triển khai thực tế, một page chứa nhiều key, con trỏ và metadata. Database trả chi phí đọc một page nhưng nhận lại đủ thông tin để loại bỏ phần lớn không gian tìm kiếm.

Đây là điểm khác biệt cốt lõi giữa B-Tree và Binary Search Tree:

Binary Search Tree có branching factor tối đa là 2.
B-Tree có branching factor lớn, tùy kích thước page và index entry.

Branching Factor làm cây thấp đến mức nào?

Giả sử minh họa mỗi internal page có thể điều hướng đến 300 page con:

1 tầng:       300 nhánh
2 tầng:    90.000 nhánh
3 tầng: 27.000.000 nhánh

Đây không phải công thức tính chính xác dung lượng một index thực tế. Leaf page còn chứa nhiều entry, page không phải lúc nào cũng đầy và kích thước key có thể rất khác nhau.

Nhưng phép tính cho thấy nguyên lý: với fan-out lớn, một B-Tree quản lý hàng triệu key mà chỉ cần một số ít tầng.

Từ khoảng 24 Page Read xuống còn 3–4

So sánh mô hình:

Binary Search Tree cân bằng
Root -> node -> node -> ... -> leaf
Khoảng 24 tầng cho 10 triệu key

B-Tree
Root -> internal -> leaf
Thường chỉ một số ít tầng

Nếu mọi page đều chưa có trong RAM:

Binary Search Tree giả định có thể gây gần 24 random page read.
B-Tree có thể chỉ cần khoảng 3–4 page read trong ví dụ minh họa.

Nếu root và internal page đã được cache, đường tìm kiếm trên storage có thể chỉ còn một leaf page, sau đó thêm một data page nếu index chưa chứa đủ dữ liệu.

Đó là cách một truy vấn trên hàng triệu row tiến gần mốc vài mili-giây: không phải đọc nhanh hàng triệu row, mà chỉ đọc một vài page đúng chỗ.

B-Tree tìm `order_id = 825731` như thế nào?

Bước 1: Đọc Root Page

Database bắt đầu ở root. Page này chứa nhiều key mốc.

Sau khi so sánh 825731 với các key, database xác định được con trỏ đến khoảng giá trị phù hợp. Toàn bộ các nhánh khác bị loại bỏ mà không cần đọc.

Bước 2: Đọc Internal Page

Internal page tiếp theo lại chứa nhiều mốc nhỏ hơn. Database lặp lại quá trình và thu hẹp phạm vi.

Mỗi tầng chỉ yêu cầu một page trên đường tìm kiếm, không phải toàn bộ page của tầng đó.

Bước 3: Đọc Leaf Page

Leaf page chứa các index entry đã được sắp xếp. Database tìm key 825731 trong page, thường bằng một cơ chế tìm kiếm trong bộ nhớ sau khi page đã được nạp.

Entry tìm được cho biết cách xác định row tương ứng.

Bước 4: Có thể phải đọc thêm Data Page

Tìm thấy key trong index chưa chắc đã có đủ dữ liệu cho:

SELECT *
FROM orders
WHERE order_id = 825731;

Nếu leaf entry chỉ chứa key và thông tin định vị row, database phải đọc thêm data page của bảng để lấy toàn bộ cột.

Hành trình đầy đủ có thể là:

Root page
    |
Internal page
    |
Leaf page: tìm thấy key
    |
Data page: lấy row hoàn chỉnh

Nếu truy vấn chỉ cần các cột đã có trong index và điều kiện visibility cho phép, database có thể tránh một phần hoặc toàn bộ việc quay lại bảng. Tên gọi và điều kiện cụ thể khác nhau giữa các hệ quản trị, thường được nhắc đến qua các khái niệm như covering index hoặc index-only scan.

So sánh ba cách tìm kiếm trên Disk

Phương án	Công việc chính	Đặc điểm I/O	Điểm yếu
Full Table Scan	Kiểm tra nhiều hoặc toàn bộ row	Nhiều page, thường đọc tuần tự	Đọc quá nhiều dữ liệu khi chỉ cần vài row
Binary Search Tree	Đi qua khoảng `log₂(n)` node	Có thể tạo nhiều random page read nối tiếp	Cây sâu, mỗi node chỉ chọn giữa hai nhánh
B-Tree Index	Đi qua một số ít page nhiều nhánh	Vài page read có mục tiêu	Tốn storage và chi phí duy trì khi ghi

Full Table Scan tận dụng sequential I/O nhưng không thu hẹp dữ liệu. Binary Search Tree thu hẹp dữ liệu nhưng chưa tận dụng tốt page. B-Tree kết hợp hai ý tưởng phù hợp hơn với database:

Key được duy trì theo thứ tự.
Mỗi page chứa nhiều mốc điều hướng.
Cây luôn cân bằng và có chiều cao thấp.
Leaf page hỗ trợ đọc liên tiếp khi cần một khoảng giá trị.

B-Tree hay B+Tree?

Trong nhiều hệ quản trị, cấu trúc được gọi là B-Tree Index thực tế mang đặc điểm của B+Tree.

Các internal page chủ yếu lưu key mốc và con trỏ xuống tầng dưới. Entry trỏ đến row tập trung ở leaf page. Nhờ dành internal page cho điều hướng, database có thể tăng số nhánh trong mỗi page và giữ cây thấp.

Tài liệu PostgreSQL mô tả B-Tree là cây cân bằng nhiều tầng:

Internal page trỏ đến tầng thấp hơn.
Leaf page ở tầng thấp nhất chứa tuple trỏ đến row của bảng.
Các page trong cùng một tầng được tổ chức thành danh sách liên kết hai chiều.

Chi tiết triển khai khác nhau giữa PostgreSQL, MySQL, SQL Server hay Oracle. Trong bài viết này, “B-Tree” được dùng theo cách gọi phổ biến cho họ cấu trúc index cân bằng nhiều nhánh.

Vì sao Leaf Page được liên kết?

Xét truy vấn:

SELECT *
FROM orders
WHERE created_at >= '2026-09-01'
  AND created_at < '2026-09-08';

Database có thể:

Đi từ root đến leaf page chứa mốc 2026-09-01.
Đọc các entry tiếp theo trong leaf page.
Chuyển sang leaf page kế tiếp.
Dừng khi key đạt 2026-09-08.

B-Tree không phải quay lại root để tìm từng key. Sau chi phí tìm điểm bắt đầu, nó có thể range scan qua các leaf page theo thứ tự.

Đó là lý do B-Tree phù hợp với:

=
<, <=, >, >=
BETWEEN
Một số truy vấn ORDER BY
MIN() và MAX()
Tìm kiếm prefix trong điều kiện phù hợp

Buffer Pool: Lý do B-Tree còn nhanh hơn trên thực tế

Không phải lần đọc Page nào cũng chạm Disk

Trước khi đọc storage, database kiểm tra buffer pool:

Cần một page
      |
Page đã có trong RAM?
      |
   Có -> đọc từ RAM
   Không -> đọc storage rồi cache page

Nếu page đã có trong RAM, database tránh được phần chậm nhất của quá trình.

Root và Internal Page có xác suất được Cache cao

Mọi lookup trên cùng một index đều bắt đầu từ root. Rất nhiều lookup cũng đi qua một tập internal page nhỏ.

Trong khi leaf page có thể có số lượng rất lớn, các tầng trên chỉ chiếm một phần nhỏ của index và được truy cập thường xuyên. Vì vậy, chúng có khả năng cao nằm trong buffer pool.

Một lookup thực tế có thể trông như sau:

Root page      -> RAM
Internal page  -> RAM
Leaf page      -> storage hoặc RAM
Data page      -> storage hoặc RAM

Trong trường hợp thuận lợi, database chỉ cần thêm một hoặc hai lần đọc storage. Đây là nền tảng thực tế cho thời gian phản hồi vài mili-giây.

Cold Cache và Warm Cache

Cùng một truy vấn có thể cho hai kết quả rất khác:

Cold cache: Page chưa có trong RAM, database phải chạm storage.
Warm cache: Page đã nằm trong buffer pool, phần lớn đường đi được xử lý trong RAM.

Vì vậy, chạy truy vấn lần thứ hai nhanh hơn lần đầu không nhất thiết chứng minh execution plan đã tốt hơn. Có thể bạn chỉ đang đo hiệu ứng của cache.

B-Tree luôn cân bằng bằng cách nào?

Các leaf của B-Tree nằm ở cùng một độ sâu logic. Khi một page không còn đủ chỗ cho entry mới, database có thể chia page và cập nhật các page phía trên.

Khái niệm đơn giản:

Trước:
[10 | 20 | 30 | 40 | 50]  -> page đầy

Sau khi split:
[10 | 20]    [30 | 40 | 50]
       \      /
    parent thêm mốc điều hướng

Page split giúp cây tiếp tục nhận dữ liệu mà không biến thành một danh sách dài. Đổi lại, nó tạo thêm công việc:

Cấp phát page
Di chuyển index entry
Cập nhật parent
Ghi log thay đổi
Có thể làm giảm tính liên tục vật lý của các page

B-Tree giữ lookup nhanh bằng cách chấp nhận thêm chi phí khi ghi.

Khi nào B-Tree Index không còn nhanh?

Truy vấn trả về quá nhiều Row

Giả sử 90% đơn hàng có trạng thái completed:

SELECT *
FROM orders
WHERE status = 'completed';

B-Tree có thể tìm điểm bắt đầu của nhóm completed rất nhanh. Nhưng database vẫn phải đọc hàng triệu leaf entry và rất nhiều data page để trả kết quả.

Khi đó, Full Table Scan có thể rẻ hơn vì đọc tuần tự bảng thay vì thực hiện nhiều lookup rời rạc. Optimizer bỏ qua index trong trường hợp này không phải lỗi; đó có thể là quyết định hợp lý.

Index có độ chọn lọc thấp

Một index trên cột chỉ có vài giá trị như status hoặc is_active chưa chắc hữu ích khi mỗi giá trị bao phủ phần lớn bảng.

Tuy nhiên, không nên áp dụng quy tắc máy móc. Cột ít giá trị vẫn có thể hữu ích khi:

Truy vấn tìm một nhóm rất hiếm.
Dữ liệu phân bố lệch.
Cột nằm trong composite index phù hợp.
Index chứa đủ dữ liệu để tránh quay lại bảng.

Chi phí nằm ở số row và page cần đọc sau khi đã tìm thấy vùng key.

Dùng hàm trên cột được Index

Index trên created_at được sắp xếp theo giá trị gốc của cột. Truy vấn sau có thể khiến database khó xác định trực tiếp một khoảng key:

WHERE YEAR(created_at) = 2026

Cách viết theo khoảng thường thân thiện hơn với B-Tree:

WHERE created_at >= '2026-01-01'
  AND created_at < '2027-01-01'

Một số database hỗ trợ expression index hoặc function-based index. Vì vậy, cần kiểm tra execution plan thay vì kết luận chỉ dựa trên hình thức câu SQL.

Composite Index sai thứ tự

Index:

CREATE INDEX idx_orders_status_created_at
ON orders(status, created_at);

được sắp xếp theo status trước, rồi mới đến created_at trong từng nhóm status. Nó không tương đương với:

CREATE INDEX idx_orders_created_at_status
ON orders(created_at, status);

Thứ tự cột quyết định cách key được bố trí trên B-Tree và những khoảng nào database có thể xác định trực tiếp. Đây là nền tảng của quy tắc Leftmost Prefix, chủ đề phù hợp cho bài tiếp theo trong serial.

Cái giá của B-Tree Index

`INSERT` phải cập nhật cây

Khi thêm một order, database không chỉ ghi row vào bảng. Nó còn phải:

Tìm leaf page phù hợp trong mỗi index liên quan.
Chèn index entry theo đúng thứ tự.
Ghi log thay đổi.
Split page nếu page không còn đủ chỗ.

Càng nhiều index, một lần INSERT càng phải làm nhiều việc.

`UPDATE` và `DELETE` cũng không miễn phí

Nếu UPDATE thay đổi cột được index, key có thể phải chuyển sang vị trí khác. DELETE cũng để lại công việc dọn dẹp hoặc cập nhật cấu trúc, tùy cơ chế của hệ quản trị.

Index tối ưu read bằng cách chuyển một phần chi phí sang write và maintenance.

Index chiếm cả Disk lẫn RAM

Mỗi index là một cấu trúc riêng:

Chiếm dung lượng storage.
Cần backup và replication.
Tốn thời gian xây dựng hoặc rebuild.
Cạnh tranh không gian trong buffer pool.
Có thể đẩy data page hoặc index page hữu ích khác khỏi RAM.

Vì thế, “thêm index” không phải đáp án mặc định cho mọi truy vấn chậm.

Kiểm chứng bằng EXPLAIN và số Page Read

So sánh trước và sau khi tạo Index

Đầu tiên, kiểm tra execution plan khi chưa có index phù hợp:

EXPLAIN
SELECT *
FROM orders
WHERE order_id = 825731;

Sau đó tạo index:

CREATE INDEX idx_orders_order_id
ON orders(order_id);

Chạy lại EXPLAIN hoặc biến thể có thực thi và thu thập thống kê mà database hỗ trợ.

Đừng chỉ nhìn vào thời gian

Thời gian bị ảnh hưởng mạnh bởi cache và tải hệ thống. Hãy quan sát thêm:

Full scan hay index lookup
Số row ước tính
Số row thực tế
Số buffer hit
Số page đọc từ storage
Có phải quay lại bảng để lấy row không
Có bước sort riêng không
Thời gian I/O và CPU nếu được cung cấp

Một thử nghiệm tốt phải chứng minh được sự thay đổi về lượng công việc:

Trước index:
đọc một phần lớn hoặc toàn bộ data page

Sau index:
đọc một số ít index page
+ data page thật sự cần thiết

Kiểm soát Cold Cache và Warm Cache

Không nên kết luận từ một lần chạy:

Chạy nhiều lần trong điều kiện kiểm soát.
Ghi nhận lần đầu và các lần sau.
Dùng dữ liệu đủ lớn để kế hoạch có ý nghĩa.
Đảm bảo hai phép đo chạy trên điều kiện tương đương.
Tránh thao tác xóa cache hoặc benchmark gây ảnh hưởng hệ thống production.

Mục tiêu không phải tạo ra con số đẹp nhất, mà là hiểu database đã giảm bao nhiêu page I/O.

Kết luận: B-Tree tối ưu I/O, không chỉ tối ưu phép so sánh

B-Tree Index nhanh vì nó được thiết kế từ bài toán storage:

Disk chậm hơn RAM nhiều bậc độ lớn.
Database phải đọc cả page dù chỉ cần một row.
Full Table Scan tận dụng sequential I/O nhưng có thể đọc hàng trăm nghìn page.
Binary Search Tree giảm số phép so sánh nhưng cây vẫn sâu và có thể tạo nhiều random page read.
B-Tree đặt nhiều key trong một page, tăng branching factor và giảm mạnh chiều cao cây.
Root và internal page thường được giữ trong buffer pool.
Một lookup trên hàng triệu key vì thế có thể chỉ cần đọc thêm một vài page.

Nói ngắn gọn:

B-Tree không giúp database xử lý 10 triệu dòng trong vài mili-giây. Nó giúp database tìm ra vài page cần thiết mà không phải xử lý 10 triệu dòng.

Đó cũng là cách nên đánh giá một index: đừng chỉ hỏi thuật toán có độ phức tạp bao nhiêu. Hãy hỏi execution plan phải đọc bao nhiêu page, bao nhiêu page đã có trong RAM và bao nhiêu lần thật sự phải chờ storage.

Ở phần tiếp theo của serial, chúng ta sẽ đi sâu vào Composite Index và quy tắc Leftmost Prefix: vì sao cùng các cột đó, chỉ cần đổi thứ tự trong index là execution plan có thể thay đổi hoàn toàn?

Nguồn tham khảo

PostgreSQL