Skip list: O(log n) có thứ tự mà không cần một phép xoay

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.

Hình dung hệ thống tàu điện của một thành phố. Cây cân bằng giống việc giữ mọi ga cách đều nhau tuyệt đối: mỗi khi thêm một ga, phải dịch lại cả tuyến cho cân — chính xác nhưng lằng nhằng. Skip list đi theo cách khác, giống thêm các tuyến tàu nhanh chồng lên tuyến thường: tầng dưới cùng ghé mọi ga, tầng trên là tàu tốc hành chỉ dừng vài ga, tầng trên nữa dừng ít ga hơn. Muốn tới ga xa, bạn đi tàu tốc hành trên cao cho gần rồi tụt xuống tàu thường — bỏ qua rất nhiều ga. Và ga nào được lên tuyến tốc hành? Quyết định bằng tung đồng xu. Nghe như 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 đủ — tàu thường). 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 "tuyến tốc hành" 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ỏ.

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

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 nếu vì thấy skip list hay mà nhảy sang "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ó" thì cũng 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.

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

Việc đầ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.

Việc 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.

Cái tinh thần "nhiều đường tới O(log n), mỗi đường thắng một tiêu chí" này lặp lại ở khắp các hệ thống thật. Java có TreeMap (cây đỏ-đen) cho đơn luồng và ConcurrentSkipListMap cho đa luồng — chính xác sự lựa chọn "đơn luồng dùng cây, đồng thời dùng skip list" mà đo ở trên chỉ ra, và không phải ngẫu nhiên JDK chọn skip list cho phiên bản concurrent. Ở tầng database, câu chuyện lại rẽ theo tầng lưu trữ: index trên đĩa gần như luôn là B-tree/B+tree (nhánh rộng, ít lần chạm đĩa) chứ không phải skip list hay cây nhị phân, vì tiêu chí thắng đổi từ "cache CPU" sang "số lần đọc trang đĩa"; nhưng memtable trong RAM của LSM-tree (RocksDB, Cassandra) lại quay về skip list vì cần ghi đồng thời nhanh. Nguyên tắc chung: cùng một bài toán "có thứ tự, O(log n)", cấu trúc thắng đổi theo tiêu chí thật — đơn giản để viết, an toàn đồng thời, cache CPU, hay số lần chạm đĩa — chứ không có quán quân tuyệt đối.

Muốn tự thấy thì 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 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.