Khi bạn cần một cấu trúc giữ thứ tự và cho tra cứu/chèn/xóa nhanh — một std::map, một sorted set — câu trả lời quen thuộc là cây cân bằng (đỏ-đen, AVL). Chúng giữ O(log n) bằng cách xoay (rotation) để cân bằng lại sau mỗi lần chèn/xóa. Logic xoay đúng nhưng rắc rối: nhiều trường hợp, dễ sai. Có một cấu trúc khác đạt cùng O(log n) mà không xoay gì cả: skip list — một danh sách liên kết nhiều tầng, mỗi node được thăng tầng theo xác suất (tung đồng xu). Nghe như một trò may rủi, nhưng nó là nền của Redis sorted set và LevelDB. Tôi đo skip list tự cài so với std::map trong container gcc:13, và con số cho thấy một câu chuyện hai chiều thú vị: nó không buộc phải cây, nhưng cũng không luôn thắng cây.
Xoay để cân bằng so với tung đồng xu để thăng tầng
Cây cân bằng như đỏ-đen giữ chiều cao O(log n) bằng cách, sau mỗi chèn/xóa, kiểm tra bất biến cân bằng và xoay các node để khôi phục nó (không để cây suy biến thành danh sách). Đảm bảo O(log n) xấu nhất, nhưng cái giá là logic xoay phức tạp.
Skip list đạt O(log n) theo cách hoàn toàn khác — bằng xác suất:
- Nó là một danh sách liên kết có thứ tự, nhưng chồng nhiều tầng con trỏ. Tầng 0 chứa mọi node (danh sách đầy đủ). Mỗi node được thăng lên tầng trên theo tung đồng xu (xác suất p=1/2): khoảng 1/2 số node lên tầng 1, 1/4 lên tầng 2, 1/8 lên tầng 3…
- Các tầng cao là những "đường cao tốc" nhảy xa. Tìm kiếm bắt đầu ở tầng cao nhất, chạy sang phải tới khi sắp vượt khóa, rồi tụt xuống tầng thấp hơn — bỏ qua rất nhiều node mỗi bước, cho O(log n) kỳ vọng.
- Chèn: tìm vị trí (nhớ các node cần nối ở mỗi tầng), tung đồng xu để chọn số tầng cho node mới, rồi nối lại con trỏ ở vài tầng đó. Không xoay, không cân bằng lại — nên code đơn giản hơn cây nhiều.
Điểm cần nhớ ngay: O(log n) của skip list là kỳ vọng (theo xác suất), không đảm bảo xấu nhất như cây; và các node rải rác trên heap như một linked list nên cache kém một mảng liền mạch.
Đo: cùng O(log n), cây nhanh hơn một chút
Tôi cài một skip list (mỗi node cấp một lần bằng mảng con trỏ linh hoạt, để công bằng), so với std::map (cây đỏ-đen của libstdc++), trên 1 triệu khóa:
N=1 triệu khóa phân biệt, g++ -O2:
A. TÌM KIẾM (5 triệu lần):
std::map (cây đỏ-đen) : 420,1 ns/lần
skip list : 452,5 ns/lần (trung bình 17,4 bước/tìm ~ log n)
-> cùng O(log n), std::map nhanh hơn ~8%
B. CHÈN (1 triệu khóa):
std::map (xoay cân bằng) : 282,8 ns/chèn
skip list (nối con trỏ, KHÔNG xoay) : 317,3 ns/chèn
-> std::map nhanh hơn ~12%
C. BỘ NHỚ (RSS thật):
std::map : 45,9 MB
skip list : 35,7 MB (skip list ~2 con trỏ/node do p=1/2; map 3 con trỏ + value)
Nhìn A — tìm kiếm: cả hai đều O(log n) (số bước tăng theo log của N), skip list trung bình 17,4 bước mỗi lần tìm ở N=1 triệu, đúng cỡ log₂(10⁶) ≈ 20. Nhưng về thời gian thật, std::map 420 ns nhỉnh hơn skip list 452 ns — nhanh hơn ~8%. Cây đỏ-đen của thư viện chuẩn được tối ưu rất kỹ, và mỗi bước của nó chỉ so một khóa rồi rẽ trái/phải, trong khi skip list quét ngang ở mỗi tầng.
Nhìn B — chèn: đây là chỗ tôi chờ skip list thắng, vì nó "không phải xoay". Nhưng đo cho thấy std::map 283 ns vẫn nhanh hơn skip list 317 ns (~12%). Việc bỏ xoay có giúp, nhưng skip list phải trả lại: tung đồng xu, nối con trỏ ở nhiều tầng, và mỗi node là một malloc. Tổng lại, xoay của cây đỏ-đen (đã tối ưu) không đắt như tôi tưởng.
Nhìn C — bộ nhớ: skip list dùng ít hơn (35,7 vs 45,9 MB), nhưng cần trung thực về lý do: skip list của tôi lưu chỉ khóa, còn std::map lưu khóa + value + ba con trỏ (trái/phải/cha) + màu. Với p=1/2, mỗi node skip list trung bình chỉ ~2 con trỏ tầng. Nên đây không phải bằng chứng "skip list tốn bộ nhớ hơn" như trực giác thường nói — với p=1/2 nó khá tiết kiệm; nếu tăng số tầng (p lớn hơn) để tìm nhanh hơn thì mới tốn thêm con trỏ.
Một lần tôi đo hớ: "phải cây cân bằng phức tạp" và "skip list luôn tốt hơn"
Tôi vào đo với niềm tin: "muốn một cấu trúc có thứ tự với O(log n) thì phải dùng cây cân bằng, mà cây cân bằng nghĩa là logic xoay rắc rối — không có đường nào đơn giản hơn". Đo phá tan phần đó: skip list đạt O(log n) kỳ vọng chỉ bằng tung đồng xu thăng tầng, chèn chỉ nối lại con trỏ mà không xoay — code đơn giản hơn cây cân bằng nhiều — và trong đo chỉ chậm hơn std::map ~8–12%. Cây cân bằng không phải cách duy nhất để có O(log n) có thứ tự; skip list là một lựa chọn thật, dễ viết đúng hơn.
Nhưng đo cũng phá luôn niềm tin ngược mà tôi suýt rơi vào sau khi thấy skip list hay: "vậy skip list đơn giản hơn thì chắc tốt như hoặc hơn cây, cứ dùng nó". Sai: std::map (cây đỏ-đen tối ưu kỹ) thực ra nhanh hơn skip list ~8–12% ở workload đơn luồng này, và O(log n) của skip list chỉ là kỳ vọng — một chuỗi tung đồng xu xui xẻo có thể cho một node cao bất thường hoặc phân bố tầng lệch, khiến vài thao tác chậm hơn, không đảm bảo xấu nhất như cây. Skip list không thắng ở tốc độ thô đơn luồng; nó thắng ở chỗ khác.
Bài học đo lường: skip list đạt O(log n) KỲ VỌNG bằng xác suất (tung đồng xu thăng tầng, ~1/2 lên mỗi tầng), chèn chỉ nối con trỏ KHÔNG xoay như cây — trong đo tìm 452 vs std::map 420 ns (~8%), chèn 317 vs 283 ns (~12%), cùng O(log n) (17,4 bước ~ log n); std::map (đỏ-đen tối ưu) NHANH hơn đơn luồng, và O(log n) skip list chỉ kỳ vọng không đảm bảo xấu nhất. Skip list thắng ở: code đơn giản (không xoay) + dễ làm lock-free/đồng thời. Nếu tôi tin "phải cây phức tạp" tôi bỏ lỡ một O(log n) đơn giản hơn; nếu tôi tin "skip list luôn hơn" tôi chọn nó cho đơn luồng nơi cây thật ra nhanh hơn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: cần O(log n) có thứ tự nhưng ngại độ phức tạp của cây cân bằng — skip list là lựa chọn hợp lý. Viết một cây đỏ-đen đúng (đủ mọi trường hợp xoay khi chèn và xóa) là một bài khó; một skip list chỉ cần một hàm tung đồng xu và vài phép nối con trỏ. Nếu bạn phải tự cài một cấu trúc có thứ tự (không dùng được thư viện chuẩn), skip list thường ít lỗi hơn nhiều với hiệu năng gần tương đương.
Hệ quả thứ hai: lý do thật khiến skip list được dùng ở hệ thống lớn là ĐỒNG THỜI, không phải tốc độ đơn luồng. Redis sorted set, LevelDB/RocksDB memtable dùng skip list vì nó dễ làm lock-free hoặc khóa mịn hơn cây cân bằng rất nhiều — chèn chỉ đụng vài con trỏ cục bộ, không xoay cả vùng cây. Đo đơn luồng của tôi không thấy lợi thế đó; nếu bài toán của bạn là nhiều luồng cùng đọc/ghi một cấu trúc có thứ tự, skip list mới lộ ưu thế. Còn đơn luồng thuần, std::map/std::set (hoặc một B-tree trong bộ nhớ) thường nhanh hơn.
Hệ quả thứ ba là tinh thần đo lường: "cách duy nhất" và "luôn tốt hơn" đều là bẫy — một cấu trúc thay thế có thể vừa khả thi vừa không thắng tuyệt đối. Con số mang theo: skip list = O(log n) kỳ vọng bằng xác suất, không xoay, code đơn giản; đo đơn luồng: chậm std::map ~8–12% (tìm 452 vs 420, chèn 317 vs 283 ns), bộ nhớ ~2 con trỏ/node (p=1/2). O(log n) chỉ kỳ vọng, không đảm bảo xấu nhất. Chọn skip list khi cần code đơn giản hoặc đồng thời (lock-free); chọn cây/std::map khi đơn luồng thuần muốn nhanh nhất. Đừng hỏi "cái nào tốt hơn" mà hỏi "tốt hơn ở tiêu chí nào".
Thử ba mươi giây
Cài một skip list nhỏ: mỗi node có một mảng con trỏ fwd với số tầng chọn bằng tung đồng xu (level=1; while(coin() && level<MAX) level++). Chèn: đi từ tầng cao xuống, nhớ node cần nối ở mỗi tầng, rồi nối node mới vào. Tìm kiếm: đi từ tầng cao, chạy sang phải tới khi sắp vượt khóa thì tụt xuống — và đếm số bước: bạn sẽ thấy nó cỡ log n (khoảng 17 bước cho 1 triệu phần tử). Rồi bấm giờ chèn và tìm trên 1 triệu khóa, so với std::map: bạn sẽ thấy cả hai cùng O(log n), và cây đỏ-đen của thư viện thực ra nhỉnh hơn một chút vì được tối ưu kỹ. Cuối cùng, để ý code skip list không có một dòng "xoay" nào — đó chính là lý do nó tồn tại. Ba mươi giây đó cho bạn thấy điều mà cả "phải dùng cây cân bằng" lẫn "skip list luôn tốt hơn" đều giấu đi: có nhiều đường tới O(log n), mỗi đường thắng ở một tiêu chí khác — đơn giản, đồng thời, hay tốc độ thô — và chỉ đo mới biết đường nào hợp với bài của bạn.
