Vì sao mọi CSDL dùng B-tree chứ không cây nhị phân — dù cùng O(log n)

Hình dung bạn tìm một mục trong một tòa nhà khổng lồ. Cách thứ nhất: ở mỗi ngã, có người hỏi "tầng cao hơn hay thấp hơn?" và bạn phải đi qua hàng chục cái ngã như vậy mới tới nơi. Cách thứ hai: sảnh có một bảng chỉ dẫn lớn chia thẳng bạn về đúng cánh, tới đó một bảng nữa chia về đúng tầng, rồi đúng phòng — ba bốn bước là xong, mỗi bước loại bỏ rất nhiều khả năng cùng lúc. Cách thứ nhất là cây nhị phân, cách thứ hai là B-tree — và cái khác biệt "mỗi bước loại bỏ bao nhiêu" chính là lý do mọi cơ sở dữ liệu chọn cách thứ hai.

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. Đây là "hỏi cao-hay-thấp 22 lần".

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. (Nói thẳng cho sòng phẳng: đâ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.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, N=4 triệu, mỗi số lấy MIN sau warmup. Đo cache miss trong RAM, không phải đĩa thật; cái cần nhìn là số tầng tỉ lệ nghịch với fanout và mỗi tầng là một lần chạm đắ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.

Hai niềm tin đối nghịch, cùng sai

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". Con số 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.

Còn niềm tin phụ, nghe hợp lý — "nhiều khóa mỗi node thì quét chậm hơn, thà cây nhị phân so ít lần" — cũng sai: quét các khóa liền nhau trong một node là tuần tự, rẻ nhờ cache và prefetch, trong khi mỗi tầng của cây nhị phân là một cú nhảy cache miss đắt. Đổi "so sánh nhiều nhưng liền mạch" lấy "ít lần chạm rải rác" là món hời — ít nhất tới điểm fanout cân bằng.

Về đến code hằng ngày

Điều đầ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.

Điều 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.

Chỗ này gần như là "tour" qua hệ thống thật, vì B-tree ở khắp nơi bạn lưu dữ liệu. Chỉ mục mặc định của PostgreSQL, MySQL/InnoDB (bảng chính lưu luôn dạng B+-tree theo khóa chính), SQLite, Oracle — tất cả là B+-tree với trang 4–16 KB. Hệ thống file ext4, NTFS, HFS+ dùng B-tree cho thư mục và siêu dữ liệu. Ngay cả các engine "log-structured" như RocksDB/Cassandra (dùng LSM-tree thay B-tree cho ghi) vẫn dùng B-tree-kiểu-block bên trong mỗi file đã sắp. Và các collection sắp-xếp trong bộ nhớ của ngôn ngữ thì đi hướng ngược lại vì lý do đúng như bài này: chúng KHÔNG cần tối ưu đĩa, nên Java TreeMap và C++ std::map dùng cây đỏ-đen (nhị phân) — hợp cho RAM — trong khi thư viện cho dữ liệu lớn thì chuyển sang B-tree. Cùng một câu hỏi "mỗi bước loại bỏ bao nhiêu", trả lời khác nhau tùy mỗi-lần-chạm đắt cỡ nào.

Muốn tự thấy thì 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. Vài phút đó 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.