← Về danh sách
Cơ sở dữ liệu
#스킵리스트#확률적자료구조#인덱스#RedisZSET#동시성
Cập nhật lần cuối · 2026-11-12

Skip List (Danh sách bỏ qua)

1. Tổng quan

A. Định nghĩa

Skip List là một cấu trúc dữ liệu xác suất (probabilistic) xếp chồng nhiều tầng con trỏ đường tắt thưa (express lane) lên trên một danh sách liên kết đã sắp xếp theo cách ngẫu nhiên, thực hiện tìm kiếm, chèn và xóa ở mức trung bình O(log n) mà không cần các phép quay và tái cân bằng phức tạp của cây tìm kiếm nhị phân cân bằng.

Skip List được William Pugh đề xuất năm 1990 như "một giải pháp thay thế xác suất cho cây cân bằng (A Probabilistic Alternative to Balanced Trees)". Ý tưởng cơ bản rất đơn giản. Danh sách liên kết đơn đã sắp xếp dễ cài đặt nhưng tìm kiếm chậm ở O(n). Nếu thêm vào đó một danh sách cấp cao hơn nhảy qua từng phần tử một, ta có thể thu hẹp phạm vi tìm kiếm còn một nửa ở mỗi bước, và lặp lại việc này qua nhiều tầng sẽ đạt hiệu quả tương tự tìm kiếm nhị phân chỉ bằng danh sách liên kết. Việc mỗi nút lên tới bao nhiêu tầng được quyết định bằng tung đồng xu (xác suất p), nên khác với cây, cấu trúc không lệch theo thứ tự đầu vào mà luôn cân bằng ở chiều kỳ vọng.

Cái nhìn cốt lõi là nó không ép buộc cân bằng mà kỳ vọng cân bằng một cách xác suất. Cây AVL và cây đỏ-đen thực hiện quay và tô màu để khôi phục bất biến mỗi khi chèn và xóa, logic này khó cài đặt và đặc biệt gây khóa trên phạm vi rộng trong môi trường đồng thời. Skip List không có phép tái cân bằng nào nên mã ngắn gọn, và vì mỗi nút chỉ thay đổi vài con trỏ cục bộ nên phạm vi khóa hẹp, có lợi cho tính đồng thời. Nhờ tính chất này, nhiều hệ thống thực tế như Redis, LevelDB, HBase đã chọn nó làm chỉ mục lõi.

B. Bối cảnh ra đời và sự cần thiết

Các tình huống đồng thời cần tìm kiếm, truy vấn phạm vi và duy trì thứ tự trên dữ liệu đã sắp xếp là phổ biến trong chỉ mục cơ sở dữ liệu, kho lưu trữ trong bộ nhớ và hàng đợi ưu tiên. Giải pháp truyền thống, cây tìm kiếm nhị phân cân bằng (B-Tree, cây đỏ-đen), bảo đảm O(log n) ngay cả trong trường hợp xấu nhất, nhưng logic tái cân bằng (quay, tách, gộp) khi chèn và xóa lại phức tạp. Sự phức tạp này không chỉ là ổ phát sinh lỗi mà còn làm tăng tranh chấp khóa trong môi trường đa lõi khi thay đổi cấu trúc lan truyền tới các nút tổ tiên. Nói cách khác, "cân bằng chính xác" phải trả giá bằng "chi phí cài đặt và đồng thời".

Skip List nhắm đúng điểm này. Bằng cách chọn cân bằng xác suất thay cho cân bằng hoàn hảo, nó đạt O(log n) trung bình trong khi loại bỏ hoàn toàn mã tái cân bằng. Đặc biệt, vì chèn và xóa chỉ sửa một số ít con trỏ lân cận, nên khóa chi tiết (fine-grained locking) hoặc cài đặt không khóa (lock-free) dễ hơn nhiều so với cây. Trong khi bảng băm không bảo toàn thứ tự và do đó không phù hợp với truy vấn phạm vi, thì tầng dưới cùng của Skip List là một danh sách đã sắp xếp hoàn chỉnh, khiến quét phạm vi (range scan) và truy cập tuần tự trở nên tự nhiên. Skip List nổi lên như một lựa chọn thực tế đúng nơi ba yêu cầu "đơn giản khi cài đặt + truy vấn phạm vi + tính đồng thời" giao nhau.

2. Cấu trúc và nguyên lý tìm kiếm

Skip List là một danh sách liên kết nhiều tầng đặt ở dưới cùng một danh sách liên kết đã sắp xếp hoàn chỉnh chứa tất cả phần tử (tầng 1) và xếp chồng lên trên các tầng cao hơn chỉ chứa một phần phần tử. Mỗi nút có một mảng con trỏ tiến (forward pointer) bằng số tầng của nó, và nút đầu (head) ngoài cùng bên trái giữ các con trỏ tới tầng tối đa, trở thành điểm vào của tìm kiếm.

flowchart LR
    subgraph L3["Tầng 3 (đường tắt thưa nhất)"]
      H3["HEAD"] --> N6_3["30"] --> NIL3["NIL"]
    end
    subgraph L2["Tầng 2"]
      H2["HEAD"] --> N2_2["10"] --> N6_2["30"] --> N9_2["60"] --> NIL2["NIL"]
    end
    subgraph L1["Tầng 1 (chứa tất cả phần tử)"]
      H1["HEAD"] --> A["5"] --> B["10"] --> C["20"] --> D["30"] --> E["45"] --> F["60"] --> G["75"] --> NIL1["NIL"]
    end

Trong hình trên, các giá trị 10, 30, 60 được thăng lên các tầng cao hơn và đóng vai trò đường tắt. Các tầng cao càng xuống dưới càng chứa nhiều phần tử, tạo thành hình kim tự tháp, và lý tưởng là thiết kế sao cho số nút ở tầng k khoảng p lần tầng k−1 (một nửa khi p=1/2 như thường lệ). Cấu trúc "giảm còn một nửa ở mỗi tầng" này tạo ra độ sâu logarit của tìm kiếm nhị phân.

Tìm kiếm (Search) xuất phát từ đầu của tầng cao nhất, tiến sang phải chừng nào chưa vượt qua giá trị mục tiêu ở tầng hiện tại, và đi xuống một tầng tại điểm mà nếu đi tiếp sẽ vượt quá mục tiêu. Lặp lại quá trình này cho đến khi tới tầng 1 sẽ thu hẹp không gian tìm kiếm theo bậc thang nhờ đường tắt (nhảy qua), đạt mục tiêu ở mức trung bình O(log n).

flowchart TB
    S["Bắt đầu tìm: HEAD tầng cao nhất"] --> C1{"khóa nút phải < khóa cần tìm?"}
    C1 -->|"Có"| R["tiến sang phải (dùng đường tắt)"]
    R --> C1
    C1 -->|"Không (vượt quá)"| C2{"tầng hiện tại > 1?"}
    C2 -->|"Có"| DN["đi xuống một tầng"]
    DN --> C1
    C2 -->|"Không (đã tới tầng 1)"| CHK{"khóa nút kế == khóa cần tìm?"}
    CHK -->|"Có"| FOUND["tìm kiếm thành công"]
    CHK -->|"Không"| NOT["tìm kiếm thất bại (không tồn tại)"]

Ví dụ giả sử ta tìm giá trị 45. Ở tầng 3, nút sau đầu là 30 và vì 30<45 nên tiến tới 30, nhưng nút kế tầng 3 của 30 là NIL không đi tiếp được nên đi xuống tầng 2. Ở tầng 2, nút kế của 30 là 60 và vì 60>45 nên đi xuống tầng 1. Ở tầng 1, tiến một bước 30→45 và tìm thấy 45. Với danh sách liên kết đơn ta phải so sánh năm lần qua 5, 10, 20, 30, 45, nhưng nhờ đường tắt, số lần so sánh giảm đi.

3. Chèn, xóa và mô hình xác suất quyết định tầng

Tiền đề chung của chèn và xóa là trước tiên thực hiện tìm kiếm trong khi ghi lại "nút ngay trước khi đi xuống" ở mỗi tầng vào mảng update[]. Mảng này trở thành danh sách các nút lân cận mà con trỏ của chúng sẽ được cập nhật khi chèn vào hoặc tháo ra một nút mới.

Chèn (Insert) gồm ba bước. Thứ nhất, tìm kiếm vị trí mục tiêu trong khi ghi lại update[] cho mỗi tầng. Thứ hai, quyết định tầng của nút mới một cách xác suất — bắt đầu từ tầng 1, tung đồng xu và nâng tầng lên 1 chừng nào còn ra mặt ngửa (xác suất p), dừng lại khi ra mặt sấp. Thứ ba, với số tầng đã quyết định, nối con trỏ tiến của update[i] tới nút mới và nối các con trỏ của nút mới tới nút mà update[i] vốn trỏ tới. Như vậy chèn chỉ sửa số con trỏ bằng số tầng đã quyết định (hằng số theo kỳ vọng), không có phép toán phạm vi rộng như quay.

Xóa (Delete) cũng điền update[] bằng tìm kiếm rồi kết thúc bằng cách chuyển hướng, ở mỗi tầng mà nút cần xóa tham gia, con trỏ của nút đứng trước sang nút kế của mục tiêu. Khi mục tiêu đã tách khỏi mọi tầng, có thể hạ tầng tối đa hiện tại của danh sách nếu các tầng trên trở nên trống. Các con trỏ mà xóa chạm tới cũng tỷ lệ với số tầng của mục tiêu (hằng số theo kỳ vọng).

Lấy một ví dụ chèn cụ thể, hãy xét việc chèn giá trị 50 làm nút tầng 3. Trước tiên, tìm vị trí của 50 từ đầu, ở mỗi tầng 3, 2, 1 ta ghi "nút cuối cùng nhỏ hơn 50" vào update[3], update[2], update[1]. Nếu tầng của nút mới được tung đồng xu quyết định là 3, thì qua ba tầng 1, 2, 3 ta đổi con trỏ tiến của update[i] thành 50 và nối ba con trỏ của 50 lần lượt tới các nút mà update[i] vốn trỏ tới. Ở cây, các phép quay có thể lan truyền lên trên để khôi phục cân bằng, nhưng ở đây việc kết thúc bằng cách đấu nối lại đúng ba cặp con trỏ cho thấy rõ tính cục bộ của thay đổi cấu trúc.

Mô hình xác suất quyết định tầng là cơ sở của hiệu năng Skip List. Xác suất một nút lên tới tầng k trở lên là p^(k−1), nên khi p=1/2, khoảng 1/2 số nút chỉ tồn tại ở tầng 1, 1/4 ở tầng 2 trở lên, và 1/8 ở tầng 3 trở lên. Số tầng kỳ vọng (số con trỏ) của một nút là 1/(1−p), chỉ là 2 trung bình khi p=1/2. Nói cách khác, bộ nhớ thêm vào trung bình khoảng hơn một con trỏ mỗi phần tử, nên độ phức tạp không gian vẫn là O(n). Tầng tối đa kỳ vọng của danh sách là log_(1/p) n, và số lần so sánh kỳ vọng của tìm kiếm được phân tích ở mức (log_(1/p) n)/p, dẫn tới O(log n) trung bình. Tuy nhiên đây là kỳ vọng, và nếu kém may một nút có thể rút được tầng quá cao làm hiệu năng dao động, nên khi cài đặt người ta đặt cận trên cho tầng tối đa (MaxLevel).

Phép toán Độ phức tạp thời gian trung bình Độ phức tạp thời gian xấu nhất Ghi chú
Tìm kiếm (Search) O(log n) O(n) xấu nhất khi mọi nút đều ở tầng 1
Chèn (Insert) O(log n) O(n) tìm kiếm + sửa hằng số con trỏ
Xóa (Delete) O(log n) O(n) tìm kiếm + sửa hằng số con trỏ
Truy vấn phạm vi O(log n + k) O(n) k là số phần tử kết quả, quét tuần tự ở tầng dưới
Không gian O(n) O(n log n) kỳ vọng n/(1−p) con trỏ

Như bảng cho thấy, độ phức tạp xấu nhất là O(n), nhưng đây là sự kiện cực hiếm về mặt xác suất khi mọi nút tình cờ chỉ rút tầng 1, và vì tầng được định bằng số ngẫu nhiên độc lập với giá trị đầu vào nên việc không thể ép trường hợp xấu nhất bằng đầu vào ác ý tương phản với điểm yếu của cây trước đầu vào lệch.

4. So sánh với cây cân bằng và các trường hợp áp dụng

So sánh Skip List với cây tìm kiếm nhị phân cân bằng (đặc biệt là cây đỏ-đen và AVL) làm rõ tiêu chí lựa chọn. Cả hai đều cung cấp O(log n) trung bình, nhưng sự khác biệt nảy sinh ở "cách bảo đảm cân bằng", và sự khác biệt đó dẫn tới hàm ý thực tế. Cây giữ nghiêm ngặt bất biến để bảo đảm O(log n) ngay cả trong trường hợp xấu nhất, đổi lại logic tái cân bằng phức tạp và thay đổi cấu trúc lan truyền lên trên. Skip List giao cân bằng cho xác suất và từ bỏ bảo đảm xấu nhất, đổi lại mã đơn giản và thay đổi cục bộ.

Phân loại Skip List Cây đỏ-đen B+Tree
Cách cân bằng xác suất (tầng ngẫu nhiên) tất định (màu, quay) tất định (tách, gộp)
Tìm kiếm trung bình O(log n) O(log n) O(log n)
Tìm kiếm xấu nhất O(n) (hiếm) O(log n) bảo đảm O(log n) bảo đảm
Độ khó cài đặt thấp cao cao
Tính đồng thời thuận lợi (sửa cục bộ) bất lợi (khóa rộng) trung bình (khóa nút)
Truy vấn phạm vi xuất sắc (quét tầng dưới) cần duyệt trung thứ tự xuất sắc (liên kết lá)
Tính cục bộ bộ nhớ đệm thấp do truy đuổi con trỏ thấp cao (theo khối)

So sánh này làm lộ ra các hàm ý thực tế. Chỉ mục cơ sở dữ liệu dựa trên đĩa phải đọc nhiều khóa trong một lần I/O, nên B+Tree với tính cục bộ bộ nhớ đệm theo khối xuất sắc chiếm ưu thế. Ngược lại, trong môi trường trong bộ nhớ, chi phí truy đuổi con trỏ tương đối nhỏ và ưu thế đơn giản khi cài đặt cùng tính đồng thời trở nên lớn, cho Skip List khả năng cạnh tranh. Nói cách khác, "lưu ở đâu (đĩa hay bộ nhớ)" là biến then chốt chia tách lựa chọn.

Cảm nhận bằng con số, sức mạnh của đường tắt trở nên rõ ràng. Giả sử ta tra hạng của một người dùng cụ thể trong bảng xếp hạng trò chơi có 10 triệu (n=10⁷) người tham gia. Một danh sách sắp xếp đơn cần trung bình 5 triệu lần so sánh, nhưng Skip List với p=1/2 có tầng kỳ vọng chỉ log₂(10⁷)≈23 tầng, đạt mục tiêu trong vài chục lần so sánh. Truy vấn phạm vi lấy 100 người điểm cao nhất (ZRANGE) cũng đi xuống điểm vào ở O(log n) rồi quét tuần tự 100 ô ở tầng dưới nên kết thúc ở O(log n + k). Như vậy, với khối lượng công việc đồng thời cần "duy trì thứ tự + hạng/phạm vi", Skip List cung cấp một tổ hợp mà băm và mảng không đem lại.

Các trường hợp áp dụng củng cố nguyên lý này. Thứ nhất, Sorted Set (ZSET) của Redis dùng song song Skip List với bảng băm cho sắp xếp theo điểm, truy vấn hạng và truy vấn phạm vi — băm tìm thành viên→điểm ở O(1), và Skip List xử lý phạm vi và hạng theo thứ tự điểm (ZRANGE, ZRANK) ở O(log n). Tra hạng bảng xếp hạng là ứng dụng tiêu biểu. Thứ hai, MemTable của LevelDB và RocksDB dùng Skip List làm cấu trúc gom các ghi trong bộ nhớ trước khi đẩy xuống đĩa, vì ngay cả khi nhiều luồng ghi chèn đồng thời thì tranh chấp khóa vẫn nhỏ và được giữ ở trạng thái sắp xếp, phù hợp để đẩy tuần tự sang SSTable sau đó. Thứ ba, MemStore của Apache HBase và ConcurrentSkipListMap/ConcurrentSkipListSet của thư viện chuẩn Java cũng cung cấp cấu trúc dữ liệu sắp xếp đồng thời dựa trên Skip List vì cùng lý do. Tất cả đều có yêu cầu chung "duy trì thứ tự + ghi đồng thời cao".

5. Chuyên sâu: Skip List không khóa / đồng thời và các biến thể thiết kế

Lý do quyết định khiến Skip List được chú ý trong các hệ thống hiện đại là tính thân thiện với đồng thời. Tái cân bằng của cây lan truyền các phép quay về phía gốc và phải khóa một phạm vi rộng, nhưng chèn và xóa của Skip List chỉ thay đổi con trỏ của các nút đứng trước lân cận, cho phép cài đặt khóa chi tiết hoặc không khóa (lock-free). ConcurrentSkipListMap của Java áp dụng thuật toán không khóa cập nhật con trỏ chỉ bằng phép CAS (Compare-And-Swap), cung cấp một map sắp xếp có thể tuyến tính hóa (linearizable) mà không cần khóa. Khi xóa, thay vì gỡ nút ngay lập tức, nó đặt một dấu xóa logic (marker) rồi dọn dẹp vật lý sau đó, qua đó bảo toàn tính nhất quán của truy cập đồng thời. Như vậy, việc "tính cục bộ của thay đổi cấu trúc" trực tiếp dẫn tới "tính mở rộng của đồng thời" là điểm khác biệt bản chất so với cây.

Các biến thể thiết kế cũng đa dạng. Hạ xác suất p xuống 1/4 làm giảm số con trỏ trung bình mỗi nút còn 1/(1−p)=4/3, tiết kiệm bộ nhớ nhưng tầng nông hơn khiến so sánh tìm kiếm tăng đôi chút, còn đặt p là 1/2 làm tìm kiếm nhanh hơn nhưng dùng nhiều không gian hơn do con trỏ tăng — nghĩa là p là núm điều chỉnh đánh đổi thời gian và không gian. Trong môi trường cần tính tất định, Skip List tất định (Deterministic Skip List) gán tầng theo quy tắc thay vì số ngẫu nhiên để bảo đảm O(log n) xấu nhất đã được đề xuất, và để nâng hiệu quả bộ nhớ đệm, các biến thể unrolled / B-skip-list gói nhiều phần tử vào một nút cũng được nghiên cứu. Gần đây, khi nhu cầu phân tích trong bộ nhớ và thời gian thực tăng lên, vị thế của Skip List như cấu trúc dữ liệu chuẩn cho tầng bộ nhớ của kho lưu trữ dạng log (LSM-Tree) ngày càng vững chắc.

6. Cân nhắc và hàm ý

Khi áp dụng và đánh giá Skip List từ góc nhìn của Kỹ sư chuyên nghiệp, cần cân nhắc toàn diện những điều sau.

  • Chiến lược lựa chọn theo môi trường lưu trữ phải đi trước. Vì truy đuổi con trỏ gây lỗi bộ nhớ đệm, nên B+Tree cho chỉ mục đĩa nơi I/O theo khối chiếm ưu thế, và Skip List cho cấu trúc trong bộ nhớ nơi chi phí con trỏ nhỏ và ưu thế cài đặt/đồng thời lớn, là phù hợp. Chọn cấu trúc dữ liệu mà bỏ qua đặc tính môi trường có thể làm hiệu năng đảo ngược.

  • Phải thận trọng ở các lĩnh vực bắt buộc bảo đảm độ phức tạp xấu nhất. Skip List là O(log n) trung bình nhưng xấu nhất là O(n). Dù hiếm về xác suất, ở các lĩnh vực phải cam kết cận trên độ trễ xấu nhất như hệ thống thời gian thực cứng (hard real-time) và an toàn thiết yếu, xem xét cây cân bằng tất định hoặc Skip List tất định sẽ an toàn hơn.

  • Điều chỉnh tham số xác suất p và MaxLevel theo quy mô dữ liệu. p quyết định đánh đổi thời gian và không gian, còn MaxLevel phải đặt ít nhất bằng log_(1/p) n đối với số phần tử tối đa dự kiến n thì mới bảo đảm hiệu ứng đường tắt. Vì nguồn ngẫu nhiên bị lệch sẽ phá vỡ cân bằng lý thuyết, nên phải dùng bộ sinh số ngẫu nhiên chất lượng cao.

  • Yêu cầu đồng thời càng cao thì ưu thế tương đối của Skip List càng lớn. Ở các kho trong bộ nhớ, bộ nhớ đệm và hàng đợi thông điệp nơi chèn và xóa đồng thời từ nhiều luồng diễn ra thường xuyên, Skip List không khóa thuận lợi hơn cây về mặt mở rộng. Ngược lại, với khối lượng công việc đơn luồng, ưu thế đọc thì cấu trúc dữ liệu có tính cục bộ bộ nhớ đệm tốt có thể tốt hơn, nên phải lấy đặc tính khối lượng công việc (tỷ lệ đọc/ghi, mức đồng thời) làm tiêu chí lựa chọn.

  • Thiết kế đồng thời yêu cầu truy vấn phạm vi và phép tính hạng. Bảng băm mạnh về truy vấn thành viên và điểm (point) nhưng yếu về thứ tự và phạm vi. Ở các khối lượng công việc mà thứ tự là cốt lõi như bảng xếp hạng và truy vấn phạm vi chuỗi thời gian, thiết kế lai đặt song song băm và Skip List như Redis ZSET để xử lý mỗi phép toán bằng cấu trúc dữ liệu tối ưu là hiệu quả.

Tổng hợp lại, Skip List là điển hình của sự thỏa hiệp kỹ thuật thay cân bằng hoàn hảo bằng cân bằng xác suất để đạt các lợi ích thực chất là đơn giản khi cài đặt, tính đồng thời và truy vấn phạm vi. Ở lĩnh vực đĩa nó nhường chỗ cho B+Tree, nhưng khi các yêu cầu của hạ tầng dữ liệu hiện đại về trong bộ nhớ, đồng thời cao và duy trì thứ tự tăng lên thì giá trị sử dụng của nó thực ra đang mở rộng, và cốt lõi của thiết kế là so sánh nó với họ cây dọc theo các trục môi trường lưu trữ, yêu cầu bảo đảm xấu nhất, mức đồng thời và mẫu truy vấn, rồi đặt nó vào đúng vị trí.

Tài liệu tham khảo


Tóm tắt một câu: Skip List xếp chồng con trỏ đường tắt một cách xác suất trên danh sách liên kết đã sắp xếp để đạt tìm kiếm, chèn và xóa trung bình O(log n) mà không cần tái cân bằng; nhờ sự đơn giản khi cài đặt cùng ưu thế đồng thời/truy vấn phạm vi, nó được dùng làm chỉ mục lõi của các hệ thống đồng thời cao trong bộ nhớ như Redis ZSET và LevelDB MemTable.