Nếu cây nhị phân cân bằng đã cho tra cứu O(log n), vì sao mọi cơ sở dữ liệu và hệ thống file — PostgreSQL, MySQL, SQLite, ext4, NTFS — đều lưu chỉ mục bằng B-tree chứ không phải cây nhị phân? Cả hai đều "O(log n)" mà. Câu trả lời nằm ở một chi tiết mà ký hiệu Big-O cố tình bỏ qua: cơ số của log, và cái giá của mỗi lần "đi xuống một tầng". Tôi dựng cả cây nhị phân lẫn B-tree với 4 triệu khóa trong container gcc:13, đo tra cứu theo fanout, và con số cho thấy "cùng O(log n)" che giấu một khác biệt gần 6 lần.
Số tầng = số lần chạm, và đó mới là thứ đắt
Ý tưởng cốt lõi: mỗi lần đi xuống một tầng cây là một lần "chạm" một vùng bộ nhớ mới — mà vùng đó nằm ở địa chỉ khó đoán (node con do malloc cấp rải rác), nên gần như luôn là một cache miss ~100 ns. Với dữ liệu trên đĩa, mỗi tầng là một lần đọc block đĩa — cỡ mili-giây. Nên chi phí tra cứu không phải là "số phép so sánh" mà là số tầng phải đi qua = số lần chạm.
Cây nhị phân giữ một khóa mỗi node, fanout 2 (mỗi node hai con). Chiều cao là log₂(N). Với N = 4 triệu, đó là ~22 tầng → 22 lần chạm, mỗi lần một cache miss.
B-tree giữ nhiều khóa mỗi node (fanout B cao — hàng chục tới hàng trăm), nên mỗi node rẽ thành B nhánh. Chiều cao là log_B(N) — nhỏ hơn nhiều. Với fanout 64, N = 4 triệu chỉ còn ~4 tầng; fanout 256 còn 3 tầng. Cái giá: mỗi node giờ chứa nhiều khóa, phải quét trong node để tìm nhánh đi tiếp. Nhưng — và đây là mấu chốt — các khóa trong một node nằm liền nhau trong bộ nhớ, nên quét chúng là truy cập tuần tự thân thiện cache/prefetch (rẻ), không phải nhảy lung tung. B-tree đổi "quét nhiều khóa hơn mỗi tầng" (rẻ) lấy "ít tầng hơn" (cắt cache miss đắt).
Đo: fanout cao, ít tầng, nhanh hơn
Tôi tra cứu 1 triệu lần trên 4 triệu khóa, so std::set (cây đỏ-đen nhị phân) với B-tree tự cài ở các fanout khác nhau. (Lưu ý trung thực: đây đo cache miss trong RAM, không phải đọc đĩa thật — nhưng đó chính là cùng một hiện tượng ở quy mô nhỏ hơn: mỗi tầng là một lần chạm đắt.)
N = 4 triệu khóa, tra cứu (g++ -O2, min):
CÂY NHỊ PHÂN (std::set, fanout 2) : ~22 tầng | 887,1 ns/tra cứu
B-TREE theo fanout:
fanout 4 : 11 tầng | 389,4 ns
fanout 16 : 6 tầng | 152,2 ns
fanout 64 : 4 tầng | 153,4 ns
fanout 256 : 3 tầng | 191,7 ns
Nhìn hàng đầu: cây nhị phân với ~22 tầng tốn 887 ns mỗi tra cứu — 22 lần nhảy tới node ở địa chỉ khó đoán, phần lớn là cache miss. Giờ nhìn B-tree: chỉ cần nâng fanout lên 16, chiều cao rơi xuống 6 tầng và thời gian còn 152 ns — nhanh hơn 5,8 lần. Fanout 64 (4 tầng) giữ ~153 ns. Cùng độ phức tạp "O(log n)", cùng 4 triệu khóa, nhưng B-tree chạm bộ nhớ ít hơn 5 lần nên nhanh gần 6 lần.
Và chú ý fanout 256: nó nhích lên 192 ns dù chỉ 3 tầng. Vì sao? Mỗi node giờ có tới 256 khóa để quét, và chi phí quét tuần tự đó bắt đầu vượt phần cache miss tiết kiệm được từ việc bớt một tầng. Đây là đánh đổi: ít tầng hơn (tốt) nhưng quét mỗi node lâu hơn (xấu). Điểm ngọt nằm ở fanout vừa phải (16–64 trong bộ nhớ), nơi số tầng đã nhỏ mà node chưa quá to. Đây chính là lý do fanout thực tế được chọn theo kích thước cache line / block đĩa, không phải càng cao càng tốt.
Vì sao CSDL và hệ thống file dùng B-tree
Con số RAM trên đã đủ thuyết phục, nhưng động lực thật của B-tree là đĩa. Một block đĩa (hay trang SSD) cỡ 4–16 KB, đọc một lần tốn ~mili-giây — chậm hơn cache miss RAM cả chục nghìn lần. Một block 16 KB chứa được hàng trăm tới hàng nghìn khóa. Nên B-tree đặt cả một node = một block đĩa: fanout lên tới hàng trăm, và cây chỉ cao 3–4 tầng cho hàng tỷ khóa. Tra cứu một khóa = 3–4 lần đọc đĩa. Nếu dùng cây nhị phân, cùng số khóa cần ~30+ tầng = 30+ lần đọc đĩa — chậm gấp mười lần, mỗi lần một cú seek mili-giây. Khi mỗi lần chạm đắt tới mili-giây, tối thiểu số lần chạm là tất cả — và đó chính xác là điều B-tree tối ưu.
Một lần tôi đo hớ: "cây nào cũng O(log n) nên như nhau"
Tôi vào đo với phép so Big-O phẳng: "cây nhị phân và B-tree đều O(log n), khác gì nhau". Đo phá tan: cây nhị phân 22 tầng (887 ns) so với B-tree fanout 64 chỉ 4 tầng (153 ns) — nhanh 5,8 lần, dù cùng O(log n). Bí mật nằm ở cơ số của log mà Big-O giấu: log₂(N) so với log₆₄(N) chênh nhau đúng bằng log₂(64) = 6 lần về số tầng, và mỗi tầng là một lần chạm đắt (cache miss, hay đọc đĩa). Còn niềm tin phụ "nhiều khóa mỗi node thì quét chậm" cũng sai: quét các khóa liền nhau trong một node là tuần tự, rẻ nhờ cache — đổi lấy ít tầng hơn là món hời, ít nhất tới một điểm cân bằng.
Bài học đo lường: "O(log n)" giấu CƠ SỐ của log, mà cơ số quyết định SỐ TẦNG = số lần chạm bộ nhớ/đĩa — cây nhị phân (fanout 2) đi ~22 tầng (887 ns), B-tree fanout 64 chỉ 4 tầng (153 ns, nhanh 5,8x); mỗi tầng một cache miss (~100ns) hay đọc đĩa (~ms), nên ít tầng thắng dù mỗi node phải quét nhiều khóa liền-mạch (rẻ). Nếu tôi tin "cùng O(log n) thì như nhau" và dùng cây nhị phân cho một chỉ mục trên đĩa, tôi đã biến mỗi tra cứu thành hàng chục lần seek đĩa thay vì vài lần — chậm cả bậc, đúng lý do không ai làm CSDL bằng cây nhị phân.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi dữ liệu lớn hoặc trên đĩa, chọn cấu trúc theo SỐ LẦN CHẠM, không theo số phép so sánh. B-tree, B+-tree thắng không phải vì ít so sánh hơn (chúng còn so sánh nhiều hơn) mà vì ít lần chạm bộ nhớ/đĩa hơn. Mọi cấu trúc "thân thiện cache" (mảng liền mạch, B-tree, hash mở địa chỉ) đều theo cùng nguyên lý: gom dữ liệu-hay-truy-cập-cùng-nhau vào cùng một block để mỗi lần chạm mang về nhiều việc.
Hệ quả thứ hai: fanout nên khớp kích thước cache line / block đĩa, không phải càng cao càng tốt. Đo cho thấy fanout 256 chậm hơn fanout 64 vì node quá to để quét. Trong bộ nhớ, fanout ~kích-thước-cache-line/khóa là hợp lý; trên đĩa, fanout ~kích-thước-block/khóa (hàng trăm). Đây là lý do các CSDL cho chỉnh page size — nó điều khiển fanout của B-tree.
Hệ quả thứ ba là tinh thần đo lường: đọc Big-O kèm hằng số bị giấu — cơ số của log là một hằng số như thế. Con số mang theo: cây nhị phân và B-tree cùng O(log n) nhưng khác CƠ SỐ log = khác SỐ TẦNG = khác số lần chạm: N=4tr, cây nhị phân ~22 tầng (887 ns) vs B-tree fanout 64 4 tầng (153 ns) = nhanh 5,8x; mỗi tầng là 1 cache miss (~100ns) hay 1 lần đọc đĩa (~ms). Fanout cao -> ít tầng (tốt) nhưng quét node lâu hơn (fanout 256: 3 tầng nhưng 192 ns) -> chọn fanout khớp cache line/block đĩa. CSDL dùng B-tree vì block đĩa chứa hàng trăm khóa -> 3-4 lần đọc cho hàng tỷ khóa. Cùng O(log n) không có nghĩa cùng số lần chạm.
Thử ba mươi giây
Lấy vài triệu khóa và tra cứu chúng hai cách: bằng std::set (cây nhị phân) và bằng một mảng đã sắp xếp mà bạn tìm theo kiểu "khối" — chia thành các block liền nhau, quét block để chọn hướng rồi đi sâu (một B-tree thu nhỏ). Đếm số lần bạn nhảy tới một vùng bộ nhớ mới trong mỗi cách, và bấm giờ. Bạn sẽ thấy phiên bản khối chạm bộ nhớ ít lần hơn hẳn và nhanh hơn nhiều, dù nó so sánh nhiều hơn — vì mỗi lần chạm là phần đắt, còn quét vài khóa liền nhau trong một block gần như miễn phí nhờ cache. Rồi thử tăng kích thước block dần: nhanh lên tới một điểm rồi chậm lại khi block quá to. Ba mươi giây đó cho bạn thấy điều mà "O(log n)" giấu đi: không phải số phép tính, mà số lần chạm bộ nhớ, mới là thứ quyết định tốc độ ở quy mô lớn — và đó là toàn bộ lý do thế giới lưu dữ liệu bằng B-tree.
