24. 스킵 리스트 (Skip List) — 확률적 균형 탐색 구조

핵심 인사이트 (3줄 요약)

본질: 스킵 리스트(Skip List)는 1990년 William Pugh가 고안한 확률적 자료구조(Probabilistic Data Structure)로, 여러 레벨의 연결 리스트(Linked List)를 계층화하여 평균 O(log n) 탐색·삽입·삭제를 달성하는 정렬된 딕셔너리(Sorted Dictionary) 구현체다.

가치: 스킵 리스트는 균형 이진 탐색 트리(AVL, Red-Black Tree)와 동일한 평균 성능을 제공하면서, 트리 회전(Rotation) 없이 확률적 랜덤화로 균형을 유지하므로 구현이 단순하고 동시성(Concurrency) 환경에서 Lock-free 구현이 용이하다.

판단 포인트: 스킵 리스트의 최악 O(n) 탐색 가능성은 확률에 의존하므로, 최악 성능 보장이 필요한 시스템에서는 AVL 또는 Red-Black Tree가 적합하다. 반면 Redis의 Sorted Set, LevelDB의 memtable은 스킵 리스트의 실무 활용 대표 사례다.

Ⅰ. 개요 및 필요성

정렬된 연결 리스트는 탐색이 O(n)으로 느리다. 스킵 리스트는 이 문제를 여러 레벨의 "고속 레인(Express Lane)"을 추가하여 해결한다.

┌───────────────────────────────────────────────────────────┐
│              스킵 리스트 구조 (값: 1~10 일부)               │
├───────────────────────────────────────────────────────────┤
│                                                           │
│  레벨3:  [1] ────────────────────────────────→ [9] → NIL │
│  레벨2:  [1] ────────────→ [5] ──────────────→ [9] → NIL │
│  레벨1:  [1] ──→ [3] ────→ [5] ──→ [7] ──────→ [9] → NIL │
│  레벨0:  [1] →[2]→[3] →[4]→[5] →[6]→[7] →[8]→[9] → NIL │
│                                                           │
│  탐색 7: 레벨3(1→9 X) → 레벨2(1→5 ok, 5→9 X) →          │
│          레벨1(5→7 ok!) → 발견 ✓                          │
│  비교 횟수: ~4회 vs 연결리스트 7회                          │
└───────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 스킵 리스트는 도시 교통 시스템이다. 모든 골목(레벨0)을 걷는 대신, 도시 고속도로(레벨3)→간선도로(레벨2)→지선(레벨1)→골목 순으로 내려가며 목적지를 빠르게 찾는다.

Ⅱ. 아키텍처 및 핵심 원리

레벨 결정 — 확률적 승진(Probabilistic Promotion)

새 노드 삽입 시 동전 던지기(p=0.5)로 레벨을 결정한다.

def random_level(max_level, p=0.5):
    level = 0
    while random() < p and level < max_level:
        level += 1
    return level
# 레벨0: 100%, 레벨1: 50%, 레벨2: 25%, 레벨3: 12.5%

기대 레벨 수: O(log n), 평균 포인터 수: O(n) → 전체 공간 O(n log n) (상수 작음).

시간 복잡도

연산	평균	최악
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

📢 섹션 요약 비유: 노드의 레벨을 동전 던지기로 정하는 것은 우체국 등급과 같다. 대부분의 우편물(노드)은 일반 배송(레벨0)이지만, 일부는 익일 배송(레벨1), 극소수는 특급(레벨3)으로 올라가 빠른 경로를 만든다.

Ⅲ. 비교 및 연결

항목	스킵 리스트	AVL 트리	Red-Black 트리
평균 탐색	O(log n)	O(log n)	O(log n)
최악 탐색	O(n) (확률적)	O(log n)	O(log n)
삽입/삭제	O(log n) 평균	O(log n) + 회전	O(log n) + 회전
구현 복잡도	낮음	중간	높음
Lock-free 구현	용이	어려움	어려움

Redis Sorted Set은 내부적으로 스킵 리스트를 사용하여 ZADD·ZRANK·ZRANGE 연산을 O(log n)에 처리한다.

📢 섹션 요약 비유: AVL 트리는 무게추가 달린 정밀 저울(엄격한 균형), Red-Black은 규칙이 복잡한 체스, 스킵 리스트는 주사위로 균형을 맞추는 즉흥 연주다. 즉흥이지만 평균적으로는 다 비슷하게 빠르다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오: Redis Sorted Set 활용

실시간 게임 리더보드 구현.

ZADD leaderboard 9800 "player1" → O(log n) 삽입 (내부 스킵 리스트).
ZRANK leaderboard "player1" → 순위 조회 O(log n).
ZRANGE leaderboard 0 9 WITHSCORES → 상위 10명 범위 조회 O(log n + k).

안티패턴

스킵 리스트를 최악 성능 보장이 필요한 실시간 시스템에 사용하는 안티패턴. p=0.5의 확률로 최악 O(n)이 발생할 수 있으며, 의료·항공 안전 시스템처럼 응답 시간 상한 보장이 필요한 경우에는 AVL이나 B-Tree가 적합하다.
📢 섹션 요약 비유: 스킵 리스트는 맑은 날에는 빠른 헬리콥터 배송이지만, 폭풍(최악의 경우)에는 지상 배송으로 바뀔 수 있다. 의료 응급 배송처럼 날씨에 관계없이 정시 도착이 필요하면 다른 수단을 써야 한다.

Ⅴ. 기대효과 및 결론

기대효과	내용
단순 구현	트리 회전 불필요, 코드 간결
동시성 친화	Lock-free 구현 가능
범위 쿼리	연결 리스트 기반 순서 유지 → 범위 탐색 효율

스킵 리스트는 LevelDB·RocksDB의 memtable 자료구조로 사용되어 쓰기 성능 최적화에 기여하며, CRDTs (Conflict-free Replicated Data Types) 등 분산 시스템에서도 확률적 자료구조의 활용이 증가하고 있다.

📢 섹션 요약 비유: 스킵 리스트는 자연 진화와 같다. 무작위 돌연변이(랜덤 레벨 결정)가 평균적으로 최적의 구조를 만들어내며, 인위적인 균형 조정(트리 회전) 없이도 빠른 탐색을 달성한다.

📌 관련 개념 맵

개념	연결 포인트
AVL / Red-Black Tree	스킵 리스트의 비교 대상; 최악 보장 균형 트리
Redis Sorted Set	스킵 리스트 실무 활용의 대표 사례
LevelDB memtable	스킵 리스트 기반 쓰기 최적화 자료구조
확률적 자료구조	스킵 리스트가 속하는 알고리즘 패밀리
Lock-free 동시성	스킵 리스트의 분산 환경 장점

📈 관련 키워드 및 발전 흐름도

[연결 리스트 — O(n) 탐색, 단순 구조]
    │
    ▼
[스킵 리스트 (1990) — 확률적 레벨, 평균 O(log n)]
    │
    ▼
[Redis Sorted Set — 스킵 리스트 실무 적용]
    │
    ▼
[LevelDB / RocksDB memtable — 쓰기 최적화 활용]
    │
    ▼
[Lock-free 스킵 리스트 — 동시성 분산 환경 활용]

👶 어린이를 위한 3줄 비유 설명

스킵 리스트는 도서관 책 찾기처럼, 큰 분류(레벨3)→중간 분류(레벨2)→작은 분류(레벨1)→실제 책(레벨0) 순으로 점점 좁혀가는 방식이에요!
처음부터 모든 책을 하나씩 뒤지는 대신, 위층 빠른 길을 먼저 타고 내려와서 훨씬 빠르게 찾을 수 있어요.
유명한 데이터베이스 Redis에서 순위표를 빠르게 처리할 때 이 방법을 쓴답니다!