Sorted Set - SkipList
1. 핵심 아이디어: “지름길 만들기”
일반적인 Linked List에서 특정 데이터를 찾으려면 처음부터 끝까지 하나씩 거쳐야 하므로 $O(N)$의 시간이 걸린다.
SkipList는 이 리스트 위에 ‘상위 레벨의 지름길’을 층층이 쌓아서 검색 속도를 O(log N)으로 끌어올린다.
- Level 0 (Base): 모든 데이터가 포함된 기본 연결 리스트
- Upper Levels: 아래 계층의 노드 중 일부를 선택하여 위로 올린다. 위로 갈수록 노드 수가 적어지며, 멀리 떨어진 노드로 한 번에 점프할 수 있다.
2. 검색 과정
1부터 10까지 정렬된 리스트에서 ‘7’ 찾기
- 최상위 레벨에서 시작한다. 현재 위치에서 다음 노드가 7보다 크면 아래 레벨로 내려가고, 작으면 앞으로 전진한다.
- “1에서 다음 노드가 10이네? 7보다 크니까 한 단계 내려가자.”
- “중간 레벨에서 1 다음이 5네? 7보다 작으니까 5로 이동하자.”
- “5 다음이 8이네? 다시 아래로 내려가서 찾자.”
이렇게 큰 폭으로 데이터를 건너뛰기 때문에, 데이터가 100만 개가 있어도 단 20번 내외의 점프($\log_2 1,000,000 \approx 20$)만으로 원하는 값을 찾을 수 있다.
3. 삽입과 “동전 던지기”
이진 탐색 트리(BST)는 균형을 맞추기 위해 복잡한 회전(Rotation) 로직이 필요하지만, SkipList는 확률에 의존한다.
- 새로운 노드가 추가될 때, 이 노드를 몇 층까지 올릴지를 동전 던지기(Random)로 결정
- 예를 들어, “앞면이 나오면 한 층 더 올리기”를 반복
- 이 확률적 설계 덕분에 구현이 매우 단순하면서도 통계적으로 완벽한 균형을 유지
4. 왜 Hash Table을 같이 쓸까?
각자의 장점이 다르다.
- SkipList: “점수 50점부터 100점 사이의 유저를 가져와(Range Query)” 같은 범위 검색에 최적화
- Hash Table: “유저 A의 점수가 몇 점이지?” 같은 특정 키의 값을 찾는 연산을 $O(1)$에 끝내기 위해 사용