Ở bài trước ta thấy chỉ mục biến một phép tìm "đọc cả bảng 7353 trang" thành "đọc 4 trang". Nhưng vì sao chỉ 4 trang? Và khi bảng lớn lên gấp trăm, gấp vạn lần, con số đó tăng theo không? Bài này mổ vào cấu trúc bên trong của chỉ mục — cây B-tree — và đo trực tiếp độ sâu của nó khi bảng phình từ nghìn hàng lên chục triệu. Kết quả làm tôi phải xem lại một giả định.
B-tree là một cây rất nông
Chỉ mục mặc định của PostgreSQL (và hầu hết cơ sở dữ liệu) là một B-tree — cây cân bằng. "Cân bằng" nghĩa là mọi nút lá đều cách gốc đúng một số tầng bằng nhau, nên tìm bất kỳ giá trị nào cũng tốn đúng số bước như nhau. Điểm cốt lõi khiến B-tree mạnh là fanout (số nhánh mỗi nút): mỗi nút của cây là một trang 8KB, và một trang chứa được hàng trăm khóa cùng con trỏ. Nghĩa là mỗi tầng đi xuống, số hàng bao phủ được nhân lên hàng trăm lần.
Hệ quả là cây nông đến bất ngờ. Với fanout khoảng 360 (con số thực tế cho khóa bigint):
- 2 tầng phủ ~360² ≈ 130 nghìn hàng
- 3 tầng phủ ~360³ ≈ 47 triệu hàng
- 4 tầng phủ ~360⁴ ≈ 17 tỉ hàng
Nghĩa là toàn bộ một bảng hàng tỉ dòng vẫn được một cây chỉ 4 tầng lập chỉ mục. Tìm một hàng chỉ là đi từ gốc xuống lá — đọc đúng bằng "độ sâu" số trang. Đó là lý do phép tìm ở bài trước chỉ đọc 4 trang.
Đo: bảng gấp 10.000 lần, cây sâu thêm một tầng
Tôi tạo cùng một bảng với ba kích thước — 1.000, 100.000, và 10 triệu hàng — đánh chỉ mục cột id, rồi đọc độ sâu cây thật bằng bt_metap (extension pageinspect) và số trang phải đọc khi tìm một hàng bằng EXPLAIN (ANALYZE, BUFFERS):
| Số hàng | Độ sâu cây | Số trang index | Trang đọc khi tìm 1 hàng |
|---|---|---|---|
| 1.000 | 2 | 5 | 6 |
| 100.000 | 2 | 276 | 6 |
| 10.000.000 | 3 | 27.422 | 7 |
Nhìn cột "độ sâu cây" và "trang đọc": bảng lớn lên 10.000 lần (từ nghìn lên chục triệu), chỉ mục phình từ 40kB lên 214MB (5 trang lên 27.422 trang), nhưng cây chỉ sâu thêm đúng một tầng (2 lên 3), và số trang phải đọc để tìm một hàng gần như y nguyên: 6, 6, rồi 7. Đáng chú ý nhất là hai dòng đầu: bảng to gấp 100 lần (1.000 lên 100.000) mà độ sâu không đổi — vẫn 2 tầng, vẫn đọc 6 trang. Chi phí tìm kiếm gần như một đường phẳng, bất kể bảng lớn cỡ nào.
Một lần tôi đo hớ: lẫn "cỡ dữ liệu" với "chi phí tra cứu"
Tôi vào bài với ý định đo đường cong: chi phí tìm kiếm tăng thế nào theo cỡ bảng. Tôi đinh ninh bảng to gấp 100 lần thì tìm phải chậm đi thấy rõ — nhiều dữ liệu hơn thì phải lục nhiều hơn chứ. Tôi đã chuẩn bị sẵn đầu để vẽ một đường đi lên.
Nhưng số đo ra là một đường phẳng: 1.000 hàng và 100.000 hàng cho cùng độ sâu 2 và cùng 6 trang đọc. Hai cỡ bảng khác nhau một trăm lần mà chi phí y hệt — thoạt nhìn cứ như tôi đo sai, hoặc cache che mất khác biệt. Theo kỷ luật, hai con số "lẽ ra phải khác" mà lại bằng nhau buộc tôi kiểm lại: mình có đang hiểu đúng cái mình đo không?
Hóa ra số phẳng đó hoàn toàn đúng, và nó dạy tôi một điều tôi vẫn biết trên lý thuyết nhưng chưa thấm khi đo: tìm trong B-tree tốn theo logarit số hàng, với cơ số là fanout (~360). Logarit cơ số lớn tăng theo từng nấc nguyên rất thưa: log₃₆₀(1.000) và log₃₆₀(100.000) đều làm tròn lên 2 — gấp 100 lần dữ liệu chưa đủ để thêm một tầng cây. Phải gấp tới ~360 lần mới nhích lên một tầng; đó là lý do mãi tới 10 triệu hàng (gấp 10.000 lần) cây mới sâu thành 3. Cái tôi đo hớ là lẫn "cỡ dữ liệu" với "chi phí tra cứu" — hai thứ khác hẳn nhau khi có chỉ mục. Cỡ dữ liệu tăng tuyến tính; chi phí tra cứu tăng theo log cơ số vài trăm, tức gần như đứng yên. Con số phẳng không phải lỗi đo, nó chính là điều kỳ diệu của B-tree.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, và trấn an nhất: một truy vấn dùng chỉ mục gần như không chậm đi khi bảng lớn lên. Đây là lý do bạn có thể yên tâm rằng một SELECT ... WHERE id = ? có chỉ mục sẽ chạy tốt dù bảng có một nghìn hay một tỉ hàng — độ sâu cây chỉ nhích từ 2 lên 4-5 trong suốt khoảng đó. Ngược lại, một truy vấn quét tuần tự (không chỉ mục) chậm tuyến tính theo cỡ bảng: gấp 100 lần dữ liệu thì chậm gấp 100. Khác biệt "log so với tuyến tính" này chính là ranh giới giữa một ứng dụng mở rộng được và một ứng dụng sập khi dữ liệu lớn.
Hệ quả thứ hai: hiểu fanout giúp đọc đúng chi phí chỉ mục. Vì fanout phụ thuộc kích thước khóa, một chỉ mục trên cột nhỏ (bigint 8 byte) có fanout lớn, cây nông; một chỉ mục trên cột lớn (chuỗi dài, khóa ghép nhiều cột) có fanout nhỏ hơn, cây sâu hơn một chút và mỗi bước đọc tốn hơn. Đây là một lý do thực tế để giữ khóa chỉ mục gọn: khóa càng nhỏ, mỗi trang chứa càng nhiều, cây càng nông và tra cứu càng rẻ. Nhưng ngay cả trường hợp xấu, log cơ số vài chục vẫn cho cây rất nông — đừng lo cây "cao" khi bảng lớn. Cụ thể trong phép đo trên, chỉ mục bigint có fanout ~360 nên 100.000 hàng vẫn nằm gọn trong cây 2 tầng, còn 10 triệu hàng cũng chỉ cần 3 tầng.
Hệ quả thứ ba là bài học đo lường. Con số mang theo: tìm trong B-tree tốn theo log(số hàng) với cơ số là fanout (~vài trăm), nên bảng to gấp 10.000 lần chỉ làm cây sâu thêm một tầng và tra cứu vẫn đọc 6-7 trang — cỡ dữ liệu và chi phí tra cứu là hai đại lượng khác hẳn nhau khi có chỉ mục. Khi một phép đo cho con số "phẳng" ở nơi bạn chờ một đường cong, đừng vội cho là đo sai — hãy hỏi lại bạn đang đo đại lượng nào. Ở đây, cỡ dữ liệu tăng vạn lần trong khi chi phí tra cứu gần như đứng yên, và cả hai đều đúng.
Thử ba mươi giây
Nếu bạn có PostgreSQL với extension pageinspect, chạy SELECT level FROM bt_metap('tên_index') trên một chỉ mục của bảng lớn nhất bạn có — bạn gần như chắc chắn thấy một số rất nhỏ (2, 3, hiếm khi 4-5), dù bảng có hàng triệu hàng. Đó là độ sâu cây, cũng là số bước tối đa để tìm một giá trị. Không có pageinspect? Chạy EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bang WHERE cot_co_index = ? và nhìn dòng Buffers: shared hit/read của Index Scan — con số trang đọc sẽ chỉ một chữ số, và nó gần như không đổi dù bảng lớn cỡ nào. Đó là B-tree đang giữ cho phép tìm của bạn phẳng.
