Tại sao cấu trúc dữ liệu Skip List lại được sử dụng thay thế cho Balanced Binary Search Tree trong một số hệ thống cơ sở dữ liệu phân tán hoặc thư viện mã nguồn mở?

Question

Accepted Answer

Skip List là một cấu trúc dữ liệu dạng danh sách liên kết phân tầng (probabilistic data structure), cho phép thực hiện các thao tác tìm kiếm, chèn và xóa với độ phức tạp thời gian trung bình O(log n), tương đương với Balanced Binary Search Tree nhưng có ưu điểm vượt trội trong môi trường đa luồng (Concurrency).
1. Bản chất cơ chế hoạt động

Skip List bao gồm nhiều lớp danh sách liên kết. Lớp dưới cùng chứa tất cả các phần tử. Các lớp phía trên hoạt động như các làn đường nhanh (express lanes), bỏ qua một số phần tử để tăng tốc độ tìm kiếm.
Việc quyết định số lượng tầng của một node mới được xác định thông qua hàm tung đồng xu ngẫu nhiên (randomized coin flipping).

2. Ưu điểm so với Balanced Binary Search Tree

Dễ cài đặt hơn rất nhiều so với Red-Black Tree hay AVL Tree.
Tối ưu hóa cho Locking (Khóa đồng bộ): Khi thực hiện chèn hoặc xóa trên Balanced BST, việc cân bằng lại cây (Rebalancing/Rotations) yêu cầu khóa một phạm vi lớn hoặc toàn bộ cây. Trong Skip List, việc chỉnh sửa các con trỏ cục bộ ở các tầng ít ảnh hưởng toàn cục hơn, giúp tối ưu hóa Lock-free hoặc Fine-grained locking trong hệ thống phân tán.

3. Trường hợp sử dụng thực tế

Được sử dụng trong cấu trúc dữ liệu lưu trữ Sorted Set của Redis.
Các cơ sở dữ liệu NoSQL cần tốc độ đọc ghi đồng thời cao.

4. Lưu ý kinh nghiệm thực chiến

Mặc dù độ phức tạp trung bình là O(log n), trường hợp xấu nhất vẫn có thể đạt O(n) do tính chất ngẫu nhiên, tuy nhiên xác suất này cực kỳ thấp trong thực tế.
Khi thiết kế hệ thống cần tính nhất quán cao và xử lý concurrency lớn, hãy cân nhắc Skip List thay vì các cấu trúc cây phức tạp.

Tại sao cấu trúc dữ liệu Skip List lại được sử dụng thay thế cho Balanced Binary Search Tree trong một số hệ thống cơ sở dữ liệu phân tán hoặc thư viện mã nguồn mở?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi data structures liên quan cùng chủ đề