스킵 리스트(Skip List)
1. 개요
가. 정의
스킵 리스트(Skip List)란 정렬된 연결 리스트 위에 여러 층의 희소한 지름길(express lane) 포인터를 확률적으로 쌓아 올려, 균형 이진 탐색 트리의 복잡한 회전·재균형 없이도 탐색·삽입·삭제를 평균 O(log n)에 수행하는 확률적(probabilistic) 자료구조이다.
스킵 리스트는 1990년 William Pugh가 "균형 트리를 대체하는 확률적 대안(A Probabilistic Alternative to Balanced Trees)"으로 제안한 자료구조이다. 기본 아이디어는 단순하다. 정렬된 단일 연결 리스트는 구현이 쉽지만 탐색이 O(n)으로 느리다. 여기에 한 칸씩 건너뛰는 상위 레벨 리스트를 얹으면 탐색 범위를 절반씩 좁힐 수 있고, 이를 여러 층으로 반복하면 이진 탐색과 유사한 효과를 연결 리스트만으로 달성한다. 각 노드가 몇 층까지 올라갈지는 동전 던지기(확률 p)로 결정하므로, 트리처럼 입력 순서에 따라 구조가 치우치지 않고 기댓값 차원에서 항상 균형을 유지한다.
핵심 통찰은 "균형을 강제로 맞추지 않고 확률적으로 기대한다"는 점이다. AVL·레드-블랙 트리는 삽입·삭제 때마다 불변식을 복구하려고 회전과 색칠을 수행하는데, 이 로직은 구현이 까다롭고 특히 동시성 환경에서 광범위한 잠금을 유발한다. 스킵 리스트는 재균형 연산 자체가 없어 코드가 짧고, 각 노드가 지역적인 포인터 몇 개만 바꾸므로 잠금 범위가 좁아 병행성에 유리하다. 이 성질 덕분에 Redis·LevelDB·HBase 등 다수의 실무 시스템이 핵심 인덱스로 채택했다.
나. 등장 배경과 필요성
정렬 데이터에 대한 탐색·범위 질의·순서 유지가 동시에 필요한 상황은 데이터베이스 인덱스, 인메모리 저장소, 우선순위 큐 등에서 보편적이다. 전통적 해법인 균형 이진 탐색 트리(B-Tree·레드-블랙 트리)는 최악에도 O(log n)을 보장하지만, 삽입·삭제 시 재균형(회전·분할·병합) 로직이 복잡하다. 이 복잡성은 버그의 온상이 될 뿐 아니라, 멀티코어 환경에서 구조 변경이 상위 노드까지 전파되면서 잠금 경합을 키운다. 즉 "정확한 균형"의 대가로 "구현·병행성 비용"을 치른다.
스킵 리스트는 이 지점을 겨냥한다. 완벽한 균형 대신 확률적 균형을 택함으로써, 재균형 코드를 통째로 제거하고도 평균 O(log n)을 얻는다. 특히 삽입·삭제가 인접한 소수의 포인터만 수정하므로, 노드 단위의 세밀한 잠금(fine-grained locking)이나 무잠금(lock-free) 구현이 트리보다 훨씬 수월하다. 해시 테이블이 순서를 보존하지 못해 범위 질의에 부적합한 반면, 스킵 리스트는 하위 레벨이 완전한 정렬 리스트이므로 범위 스캔(range scan)과 순차 접근이 자연스럽다. "구현 단순성 + 범위 질의 + 병행성"이라는 세 요구가 겹치는 자리에서 스킵 리스트가 실무의 선택지로 떠오른 배경이다.
2. 구조와 탐색 원리
스킵 리스트는 하단에 모든 원소를 담은 완전한 정렬 연결 리스트(레벨 1)를 두고, 그 위에 원소의 일부만 포함하는 상위 레벨들을 쌓은 다층 연결 리스트이다. 각 노드는 자신의 레벨 수만큼 전방 포인터(forward pointer) 배열을 가지며, 맨 왼쪽의 머리(head) 노드는 최대 레벨까지의 포인터를 보유해 탐색의 진입점이 된다.
flowchart LR
subgraph L3["레벨 3 (가장 희소한 지름길)"]
H3["HEAD"] --> N6_3["30"] --> NIL3["NIL"]
end
subgraph L2["레벨 2"]
H2["HEAD"] --> N2_2["10"] --> N6_2["30"] --> N9_2["60"] --> NIL2["NIL"]
end
subgraph L1["레벨 1 (모든 원소 포함)"]
H1["HEAD"] --> A["5"] --> B["10"] --> C["20"] --> D["30"] --> E["45"] --> F["60"] --> G["75"] --> NIL1["NIL"]
end
위 그림에서 값 10·30·60은 상위 레벨까지 승격되어 지름길 역할을 한다. 상위 레벨은 아래로 갈수록 포함 원소가 늘어나 피라미드 형태를 이루며, 이상적으로는 레벨 k의 노드 수가 레벨 k−1의 약 p배(통상 p=1/2이면 절반)가 되도록 설계한다. 이 "층마다 절반으로 줄어드는" 구조가 이진 탐색의 로그 깊이를 만들어 낸다.
탐색(Search)은 최상위 레벨의 머리에서 출발해, 현재 레벨에서 목표값을 넘지 않는 한 오른쪽으로 전진하고, 더 가면 목표를 지나치는 지점에서 한 레벨 아래로 내려간다. 이 과정을 레벨 1에 도달할 때까지 반복하면, 넘겨짚기(지름길)로 탐색 공간을 계단식으로 좁혀 평균 O(log n)에 목표에 도달한다.
flowchart TB
S["탐색 시작: HEAD 최상위 레벨"] --> C1{"오른쪽 노드 키 < 찾는 키?"}
C1 -->|"예"| R["오른쪽으로 전진 (지름길 사용)"]
R --> C1
C1 -->|"아니오 (넘침)"| C2{"현재 레벨 > 1?"}
C2 -->|"예"| DN["한 레벨 아래로 하강"]
DN --> C1
C2 -->|"아니오 (레벨 1 도달)"| CHK{"다음 노드 키 == 찾는 키?"}
CHK -->|"예"| FOUND["탐색 성공"]
CHK -->|"아니오"| NOT["탐색 실패 (존재하지 않음)"]
예를 들어 값 45를 찾는다고 하자. 레벨 3에서 머리 다음은 30이고 30<45이므로 30으로 전진하지만, 30의 레벨 3 다음은 NIL이라 더 못 가므로 레벨 2로 내려간다. 레벨 2에서 30의 다음은 60이고 60>45이므로 레벨 1로 내려간다. 레벨 1에서 30→45로 한 칸 전진해 45를 찾는다. 단일 연결 리스트라면 5·10·20·30·45까지 다섯 번 비교해야 하지만, 지름길 덕분에 비교 횟수가 줄어든다는 것을 알 수 있다.
3. 삽입·삭제와 레벨 결정의 확률 모델
삽입·삭제의 공통 전제는 먼저 탐색을 수행하되, 각 레벨에서 "내려가기 직전의 노드"를 update[] 배열에 기록해 두는 것이다. 이 배열은 새 노드를 끼워 넣거나 떼어낼 때 포인터를 갱신할 이웃들의 목록이 된다.
삽입(Insert)은 세 단계로 이뤄진다. 첫째, 목표 위치를 탐색하며 각 레벨의 update[]를 기록한다. 둘째, 새 노드의 레벨을 확률적으로 결정한다 — 레벨 1에서 시작해 동전을 던져 앞면(확률 p)이 나오는 동안 레벨을 1씩 올리고, 뒷면이 나오면 멈춘다. 셋째, 결정된 레벨 수만큼 update[i]의 전방 포인터를 새 노드로 잇고, 새 노드의 포인터는 원래 update[i]가 가리키던 노드로 잇는다. 이처럼 삽입은 결정된 레벨 수(기댓값 상수)만큼의 포인터만 수정하므로 회전 같은 광역 연산이 없다.
삭제(Delete) 역시 탐색으로 update[]를 채운 뒤, 삭제 대상 노드가 참여하는 각 레벨에서 선행 노드의 포인터를 대상 노드의 다음으로 우회시키는 것으로 끝난다. 모든 레벨에서 대상이 떨어져 나가면, 상위 레벨이 비게 될 경우 리스트의 현재 최대 레벨을 낮춰 둘 수 있다. 삭제가 건드리는 포인터 역시 대상의 레벨 수(기댓값 상수)에 비례한다.
구체적인 삽입 예로 값 50을 레벨 3짜리로 끼워 넣는 경우를 보자. 먼저 머리에서부터 50의 자리를 탐색하며, 레벨 3·2·1 각각에서 "50보다 작은 마지막 노드"를 update[3], update[2], update[1]에 기록한다. 새 노드의 레벨을 동전 던지기로 3으로 결정했다면, 레벨 1·2·3 세 층에서 update[i]의 전방 포인터를 50으로 바꾸고 50의 세 포인터를 각각 원래 update[i]가 가리키던 노드로 연결한다. 트리라면 균형 복구를 위해 상위로 회전이 전파될 수 있지만, 여기서는 정확히 세 쌍의 포인터만 재배선하면 끝난다는 점이 구조 변경의 지역성을 잘 보여 준다.
레벨 결정의 확률 모델은 스킵 리스트 성능의 근거다. 노드가 레벨 k 이상으로 올라갈 확률은 p^(k−1)이므로, p=1/2일 때 노드의 약 1/2은 레벨 1, 1/4은 레벨 2 이상, 1/8은 레벨 3 이상에만 존재한다. 노드 하나의 기대 레벨 수(포인터 개수)는 1/(1−p)로, p=1/2이면 평균 2개에 불과하다. 즉 추가 메모리는 원소당 평균 포인터 한 개 남짓으로 공간 복잡도는 여전히 O(n)이다. 리스트의 기대 최대 레벨은 log_(1/p) n이며, 탐색의 기대 비교 횟수는 (log_(1/p) n)/p 수준으로 분석되어 평균 O(log n)이 유도된다. 다만 이는 기댓값이며, 운이 나쁘면 한 노드가 과도하게 높은 레벨을 뽑아 성능이 흔들릴 수 있어, 구현상 최대 레벨에 상한(MaxLevel)을 둔다.
| 연산 | 평균 시간복잡도 | 최악 시간복잡도 | 비고 |
|---|---|---|---|
| 탐색(Search) | O(log n) | O(n) | 최악은 모든 노드가 레벨 1일 때 |
| 삽입(Insert) | O(log n) | O(n) | 탐색 + 상수 개 포인터 수정 |
| 삭제(Delete) | O(log n) | O(n) | 탐색 + 상수 개 포인터 수정 |
| 범위 질의 | O(log n + k) | O(n) | k는 결과 원소 수, 하위 레벨 순차 스캔 |
| 공간 | O(n) | O(n log n) | 기대 포인터 n/(1−p)개 |
표에서 보듯 최악 복잡도는 O(n)이지만, 이는 모든 노드가 우연히 레벨 1만 뽑는 확률적으로 극히 희박한 사건이며, 레벨이 입력값과 무관하게 난수로 정해지므로 악의적 입력으로 최악을 강제할 수 없다는 점이 트리의 편향 입력 취약성과 대비된다.
4. 균형 트리와의 비교 및 적용 사례
스킵 리스트를 균형 이진 탐색 트리(특히 레드-블랙 트리·AVL)와 비교하면 선택 기준이 분명해진다. 둘 다 평균 O(log n)을 제공하지만, 차이는 "균형을 보장하는 방식"에서 발생하고 그 차이가 실무 함의로 이어진다. 트리는 불변식을 엄격히 지켜 최악에도 O(log n)을 보장하는 대신 재균형 로직이 복잡하고 구조 변경이 상위로 전파된다. 스킵 리스트는 균형을 확률에 맡겨 최악 보장을 포기하는 대신 코드가 단순하고 변경이 지역적이다.
| 구분 | 스킵 리스트 | 레드-블랙 트리 | B+Tree |
|---|---|---|---|
| 균형 방식 | 확률적(난수 레벨) | 결정적(색·회전) | 결정적(분할·병합) |
| 평균 탐색 | O(log n) | O(log n) | O(log n) |
| 최악 탐색 | O(n) (희박) | O(log n) 보장 | O(log n) 보장 |
| 구현 난이도 | 낮음 | 높음 | 높음 |
| 병행성(동시성) | 유리(지역적 수정) | 불리(광역 잠금) | 중간(노드 잠금) |
| 범위 질의 | 우수(하위 레벨 스캔) | 중위 순회 필요 | 우수(리프 연결) |
| 캐시 지역성 | 포인터 추적으로 낮음 | 낮음 | 높음(블록 단위) |
이 비교에서 실무적 함의가 드러난다. 디스크 기반 데이터베이스 인덱스는 한 번의 I/O로 많은 키를 읽어야 해 블록 단위 캐시 지역성이 뛰어난 B+Tree가 지배적이다. 반면 인메모리 환경에서는 포인터 추적 비용이 상대적으로 작고 구현 단순성·병행성 이점이 커져 스킵 리스트가 경쟁력을 갖는다. 즉 "어디에 저장하느냐(디스크 대 메모리)"가 선택을 가르는 핵심 변수다.
수치로 체감해 보면 지름길의 위력이 분명해진다. 1,000만(n=10⁷) 명이 참여하는 게임 리더보드에서 특정 사용자의 순위를 조회한다고 하자. 단일 정렬 리스트라면 평균 500만 번의 비교가 필요하지만, p=1/2인 스킵 리스트는 기대 레벨이 log₂(10⁷)≈23층에 불과해 수십 번의 비교로 목표에 도달한다. 점수 상위 100명을 뽑는 범위 질의(ZRANGE)도 진입점까지 O(log n)으로 내려간 뒤 하위 레벨을 100칸 순차 스캔하면 되므로 O(log n + k)에 끝난다. 이처럼 "정렬 유지 + 순위·범위"가 동시에 필요한 워크로드에서 스킵 리스트는 해시·배열이 주지 못하는 조합을 제공한다.
적용 사례는 이 원리를 뒷받침한다. 첫째, Redis의 정렬 집합(Sorted Set, ZSET)은 점수 기준 정렬·순위 조회·범위 질의를 위해 스킵 리스트를 해시 테이블과 병행 사용한다 — 해시로 멤버→점수를 O(1)에 찾고, 스킵 리스트로 점수 순 범위·순위(ZRANGE·ZRANK)를 O(log n)에 처리한다. 리더보드 순위 조회가 대표적 활용이다. 둘째, LevelDB·RocksDB의 멤테이블(MemTable)은 디스크로 내려가기 전 쓰기를 메모리에 모으는 구조로 스킵 리스트를 쓰는데, 다수의 쓰기 스레드가 동시에 삽입해도 잠금 경합이 작고 정렬 상태로 유지돼 이후 SSTable로 순차 flush하기에 적합하기 때문이다. 셋째, Apache HBase의 MemStore와 Java 표준 라이브러리의 ConcurrentSkipListMap/ConcurrentSkipListSet도 동일한 이유로 스킵 리스트 기반 동시성 정렬 자료구조를 제공한다. 이들은 모두 "정렬 유지 + 높은 동시 쓰기"라는 공통 요구를 가진다.
5. 심화: 무잠금·병행 스킵 리스트와 설계 변형
스킵 리스트가 현대 시스템에서 각광받는 결정적 이유는 병행성 친화성이다. 트리의 재균형은 회전이 루트 방향으로 전파되어 넓은 범위를 잠가야 하지만, 스킵 리스트의 삽입·삭제는 인접한 선행 노드들의 포인터만 바꾸므로 세밀한 잠금 또는 무잠금(lock-free) 구현이 가능하다. Java의 ConcurrentSkipListMap은 CAS(Compare-And-Swap) 연산만으로 포인터를 갱신하는 무잠금 알고리즘을 채택해, 잠금 없이도 선형화(linearizable) 가능한 정렬 맵을 제공한다. 삭제 시에는 노드를 즉시 떼지 않고 논리적 삭제 표시(marker)를 둔 뒤 나중에 물리적으로 정리하는 기법으로 동시 접근의 정합성을 지킨다. 이처럼 "구조 변경의 지역성"이 곧 "동시성의 확장성"으로 직결된다는 점이 트리 대비 본질적 차별점이다.
설계 변형도 다양하다. 확률 p를 1/4로 낮추면 노드당 평균 포인터가 1/(1−p)=4/3개로 줄어 메모리를 아끼는 대신 레벨이 얕아져 탐색 비교가 다소 늘고, p를 1/2로 두면 탐색이 빨라지는 대신 포인터가 늘어 공간을 더 쓴다 — 즉 p는 시간·공간의 조율 손잡이다. 결정론이 필요한 환경에서는 난수 대신 규칙으로 레벨을 부여해 최악 O(log n)을 보장하는 결정적 스킵 리스트(Deterministic Skip List)가 제안되었고, 캐시 효율을 높이려 한 노드에 여러 원소를 담는 언롤드(unrolled)·B-스킵 리스트 변형도 연구된다. 최근에는 인메모리·실시간 분석 수요가 커지면서, 로그 구조 저장소(LSM-Tree)의 메모리 계층 표준 자료구조로서 스킵 리스트의 위상이 더욱 공고해지고 있다.
6. 고려사항 및 시사점
스킵 리스트를 기술사 관점에서 적용·평가할 때는 다음을 종합적으로 고려해야 한다.
저장 매체에 따른 선택 전략이 선행되어야 한다. 포인터 추적은 캐시 미스를 유발하므로, 블록 단위 I/O가 지배하는 디스크 인덱스에는 B+Tree가, 포인터 비용이 작고 구현·동시성 이점이 큰 인메모리 구조에는 스킵 리스트가 적합하다. 매체 특성을 무시한 채 자료구조를 고르면 성능이 역전될 수 있다.
최악 복잡도 보장이 필수인 영역에는 신중해야 한다. 스킵 리스트는 평균 O(log n)이지만 최악은 O(n)이다. 확률적으로 희박하더라도 경성 실시간(hard real-time)·안전필수 시스템처럼 최악 지연 상한을 계약해야 하는 도메인에서는, 결정적 균형 트리나 결정적 스킵 리스트를 검토하는 편이 안전하다.
확률 파라미터 p와 MaxLevel을 데이터 규모에 맞춰 조율한다. p는 시간·공간의 트레이드오프를 결정하고, MaxLevel은 예상 최대 원소 수 n에 대해 log_(1/p) n 이상으로 잡아야 지름길 효과가 보장된다. 난수원이 편향되면 이론적 균형이 깨지므로 양질의 난수 생성기를 써야 한다.
병행성 요구가 높을수록 스킵 리스트의 상대 이점이 커진다. 다수 스레드의 동시 삽입·삭제가 빈번한 인메모리 저장소·캐시·메시지 큐에서는 무잠금 스킵 리스트가 트리보다 확장성 면에서 유리하다. 반대로 단일 스레드·읽기 지배 워크로드라면 캐시 지역성이 좋은 자료구조가 더 나을 수 있어, 워크로드 특성(읽기/쓰기 비율·동시성 수준)을 선택 기준으로 삼아야 한다.
범위 질의·순위 연산 요구를 함께 설계한다. 해시 테이블은 멤버십·점(point) 조회에 강하지만 순서·범위에 약하다. 리더보드·시계열 범위 조회처럼 순서가 핵심인 워크로드에서는 Redis ZSET처럼 해시와 스킵 리스트를 병행 배치해 각 연산을 최적 자료구조로 처리하는 하이브리드 설계가 효과적이다.
종합하면 스킵 리스트는 "완벽한 균형을 확률적 균형으로 대체"해 구현 단순성·병행성·범위 질의라는 실질 이득을 얻는 공학적 절충의 전형이다. 디스크 영역에서는 B+Tree에 자리를 내주지만, 인메모리·고동시성·정렬 유지라는 현대 데이터 인프라의 요구가 커질수록 그 활용 가치는 오히려 확대되고 있으며, 저장 매체·최악 보장 요구·병행성 수준·질의 패턴을 축으로 트리 계열과 비교해 적합한 자리에 배치하는 것이 설계의 핵심이다.
참고자료
- William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, 1990. https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
- Redis Documentation, "Redis sorted sets". https://redis.io/docs/latest/develop/data-types/sorted-sets/
- Java Platform SE, "ConcurrentSkipListMap". https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html
- Google LevelDB source, "skiplist.h". https://github.com/google/leveldb/blob/main/db/skiplist.h
한 줄 요약: 스킵 리스트는 정렬 연결 리스트 위에 확률적으로 지름길 포인터를 쌓아 평균 O(log n) 탐색·삽입·삭제를 재균형 없이 달성하는 자료구조로, 구현 단순성과 병행성·범위 질의 이점 덕에 Redis ZSET·LevelDB 멤테이블 등 인메모리 고동시성 시스템의 핵심 인덱스로 쓰인다.