B-tree làm 100 phép so sánh, tìm nhị phân làm 20 — mà B-tree vẫn nhanh hơn

Tìm một hồ sơ trong kho lưu trữ, cái đắt không phải việc đọc tên trên bìa — mà là việc đi bộ tới đúng cái kệ. Nếu mỗi lần so sánh bắt bạn chạy sang một kệ khác ở cuối kho, mười lần so sánh là mười chuyến chạy mệt nhoài. Nhưng nếu một ngăn kéo chứa sẵn năm mươi hồ sơ liền nhau, kéo ngăn ra một lần rồi liếc qua cả xấp gần như miễn phí — làm nhiều phép so sánh hơn mà ít chuyến đi hơn nhiều, và tổng lại nhanh hơn. Đó chính xác là tinh thần của B-tree. Bài trước kết thúc bằng một phát hiện khó chịu: hai cây nhị phân cùng chiều cao, cùng O(log n), mà tra chênh nhau 6 lần chỉ vì cách các node nằm trong bộ nhớ — thủ phạm là trượt cache. B-tree là câu trả lời trực diện. Tôi cài B-tree thật, đo nó ở nhiều bậc, và bắt gặp một trong những bài học đo lường sạch sẽ nhất của sê-ri: số so sánh và đồng hồ nói hai điều trái ngược, và chỉ một trong hai nói thật.

B-tree đổi cách bố trí, không đổi ý tưởng tìm kiếm

Ý tưởng tìm kiếm của B-tree vẫn là chia để trị như cây nhị phân, nhưng cách xếp dữ liệu vào bộ nhớ thì đảo ngược. Thay vì mỗi node giữ một khóa và hai con trỏ, một node B-tree giữ nhiều khóa — bậc B của cây — nằm liền nhau trong một khối, cùng B con trỏ tới các cây con. Vì mỗi node "nuốt" được nhiều khóa, cây thấp hẳn xuống: chiều cao là log theo cơ số B chứ không phải cơ số 2. Với hai triệu khóa, một cây nhị phân cao 22 tầng, còn B-tree bậc 64 chỉ cao 4 tầng.

Vì sao chiều cao lại đáng giá đến thế? Vì cái đắt không phải phép so sánh, mà là mỗi lần bước xuống một tầng — đó là lúc CPU phải nạp một node mới từ bộ nhớ, và nếu node không có trong cache thì phải chờ RAM (hàng trăm chu kỳ). Một node B-tree được gói trong một khối liền cỡ một dòng cache, nên nạp cả node chỉ tốn một lần chờ — đúng cái "kéo một ngăn kéo ra rồi liếc cả xấp". Ít tầng nghĩa là ít lần chờ. Bên trong một node thì CPU quét tuyến tính qua các khóa đã nằm sẵn trong cache — rẻ như không. Đây chính là lý do B-tree là cấu trúc của mọi chỉ mục cơ sở dữ liệu và hệ thống tệp: ở đó "một lần nạp" là một lần đọc đĩa, đắt gấp vạn lần, nên ép cây thật thấp là thắng lớn. Tôi đo xem lý thuyết này đúng tới đâu, và ở bậc B nào.

Quét đường cong theo bậc B

Tôi cài B-tree trong C (gcc -O2), nạp hai triệu khóa, rồi đo với các bậc B từ 2 tới 256: số tầng, số phép so sánh trung bình mỗi lần tra, và thời gian tra thực tế. Kèm một mốc so sánh: tìm nhị phân trên mảng phẳng đã sắp.

bậc B     tầng   so sánh/tra   thời gian tra
   2       22        22          437 ns   (chính là cây nhị phân con trỏ)
   8        8        31           92 ns
  16        6        43           71 ns
  32        5        66           70 ns   *
  64        4       100           70 ns   *
 128        3       190           81 ns
 256        3       271          100 ns
tìm nhị phân mảng phẳng: 20 so sánh, 98 ns

Đường cong kể một câu chuyện rõ ràng. Khi B tăng, số tầng giảm đều (22 xuống 3), số so sánh mỗi lần tra tăng (22 lên 271), còn thời gian thì đi theo hình chữ U: giảm mạnh từ 437 xuống chạm đáy khoảng 70 nano giây ở bậc 32-64, rồi lại nhích lên. B=2 — vốn chính là một cây nhị phân con trỏ — chậm nhất, 437 nano giây, vì 22 tầng là 22 lần trượt cache. Bậc tối ưu nằm ở 32-64, nơi node vừa cỡ một dòng cache. Và hai con số ở đáy chữ U với ở mốc nhị phân là chỗ tôi suýt kết luận sai.

Số so sánh nói dối, đồng hồ nói thật

Nếu tôi đo B-tree bằng thước quen thuộc nhất của phân tích thuật toán — đếm số phép so sánh — thì tôi đã kết luận B-tree tệ hơn. Nhìn thẳng vào số: tìm nhị phân trên mảng làm 20 phép so sánh mỗi lần tra; B-tree bậc 64 làm 100 — gấp năm lần. Theo cách đếm cổ điển, năm lần nhiều việc hơn thì phải năm lần chậm hơn. Tôi đã vào bài nửa tin rằng B-tree chỉ đáng cho đĩa, còn trong RAM thì tìm nhị phân gọn nhẹ sẽ thắng.

Đồng hồ nói ngược lại. B-tree bậc 64 tra mất 70 nano giây; tìm nhị phân mất 98. B-tree làm gấp năm lần số so sánh mà vẫn nhanh hơn. Lý do là số so sánh đo nhầm đại lượng: cái quyết định thời gian không phải số phép so sánh, mà là số lần trượt cache. Tìm nhị phân trên mảng hai triệu phần tử nhảy tới 20 vị trí cách xa nhau, phần lớn là trượt cache — khoảng 20 lần chờ RAM. B-tree bậc 64 chỉ đi xuống 4 tầng, tức 4 lần nạp node; 100 phép so sánh của nó nằm gọn trong 4 khối đã ở trong cache, chạy gần như miễn phí. Bốn lần chờ RAM đánh bại hai mươi lần, dù kèm theo nhiều phép so sánh gấp bội. Đây là bài học cốt lõi: số phép so sánh là một mô hình chi phí lỗi thời; trên phần cứng thật, đơn vị đắt tiền là một lần chạm bộ nhớ, và chỉ đồng hồ mới đếm đúng nó. Ai tối ưu theo số so sánh sẽ chọn sai cấu trúc.

Cú hớ thứ hai nằm ngay cạnh: nếu ít tầng là tốt, thì cứ chọn B thật lớn cho ít tầng nhất, phải không? Đo ra không. Bậc 256 có ít tầng nhất (3) nhưng lại chậm hơn bậc 64 (100 so với 70 nano giây), vì mỗi node giờ to tới mức quét tuyến tính qua 255 khóa trong nó bắt đầu tốn — và một node 2KB tràn khỏi một dòng cache, nên "một lần nạp" thành nhiều lần. Có một bậc B tối ưu, ở đây quanh 32-64, đúng chỗ một node vừa khít cỡ một dòng cache. Không đo cả đường cong thì không thấy được cái đỉnh này.

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

Điều đầu tiên: bỏ thói quen đếm số phép so sánh khi cần biết cái gì nhanh trên phần cứng thật. Số so sánh (và big-O đếm thao tác nói chung) là mô hình từ thời bộ nhớ phẳng, mọi truy cập tốn như nhau. Máy thật không như vậy — một lần trúng cache và một lần trượt cache chênh nhau cả trăm lần. Khi hai cấu trúc cùng độ phức tạp mà một cái chạm bộ nhớ ít lần hơn, cái đó thắng, dù nó làm nhiều "thao tác" hơn trên giấy.

Điều thứ hai: thiết kế cấu trúc theo cấp bộ nhớ mà nó sống trên đó. B-tree tỏa sáng vì nó khớp với thực tế phần cứng: dữ liệu di chuyển theo khối (dòng cache 64 byte, trang đĩa vài KB), không theo từng byte. Gói nhiều khóa vào một khối để mỗi lần nạp làm được nhiều việc là nguyên lý chung.

Và đây là chỗ B-tree thống trị đời thực nhiều hơn bất kỳ cấu trúc nào trong sê-ri, chỉ là bạn không thấy nó trực tiếp. Mọi chỉ mục cơ sở dữ liệu bạn từng tạo — CREATE INDEX trong PostgreSQL/MySQL/Oracle/SQLite — là một B-tree (chính xác là B+tree) với node cỡ trang đĩa (thường 8–16 KB), đúng để mỗi lần đọc đĩa nuốt được thật nhiều khóa; đó là lý do một truy vấn có index nhanh gấp vạn lần quét bảng. Các engine kiểu LSM (Cassandra, RocksDB) là biến thể cho tải ghi nặng. Ngay trong RAM, Java TreeMap và C++ std::map là cây đỏ-đen (nhị phân, con trỏ rải rác) — nên với dữ liệu lớn chỉ đọc, một mảng đã sắp + tìm nhị phân, hoặc một cấu trúc gói khối, thường đánh bại chúng đúng vì lý do cache ở đây. Mẫu số chung: khi một cấu trúc "làm nhiều việc hơn" mà vẫn nhanh hơn, đừng cãi lại đồng hồ — hãy hỏi nó đang đếm đúng cái gì (số lần chạm bộ nhớ) mà cách đếm cũ (số so sánh) của bạn bỏ sót; và chọn bậc khối khớp cấp bộ nhớ đang nghẽn (dòng cache nếu ở RAM, trang nếu ở đĩa).

Muốn tự thấy thì lần tới khi bạn định chọn cấu trúc tra cứu "ít thao tác nhất", dừng lại hỏi: mỗi thao tác của nó chạm bộ nhớ ở đâu? Một cây nhị phân đẹp trên giấy (log n so sánh) nhưng con trỏ rải khắp bộ nhớ sẽ trả giá một lần trượt cache cho mỗi tầng; một cấu trúc gói dữ liệu thành khối liền làm nhiều so sánh hơn nhưng ít lần chạm RAM hơn, và thường thắng. Đừng suy luận mà đo: lấy cấu trúc của bạn, đếm số lần nó nhảy tới một địa chỉ xa (các lần trượt cache tiềm tàng), rồi so với số lần nó đọc dữ liệu liền kề. Nếu thấy nhiều cú nhảy xa, đó là chỗ để cải thiện — gói dữ liệu lại gần nhau, giảm số tầng, tăng số việc làm trên mỗi lần nạp. Và luôn xác nhận bằng đồng hồ: nếu số so sánh giảm mà thời gian không giảm, bạn vừa tối ưu nhầm đại lượng.