컴퓨터공학 300 주제 시리즈의 057번째 글이다. 전체 지도는 여기.

한 줄 요약

스킵 리스트는 정렬된 연결 리스트 위에 “몇 칸씩 건너뛰는” 고속 차선을 여러 층 쌓은 구조로, 각 노드의 층 수를 동전 던지기로 정해 회전 없이도 탐색·삽입·삭제를 기대 O(log n) 에 해낸다.

왜 필요한가

정렬된 연결 리스트는 삽입·삭제 자체는 쉽지만, 위치를 찾느라 처음부터 따라가야 해서 O(n) 이다. 균형 트리는 O(log n) 이지만 레드블랙 트리 편에서 봤듯 회전과 색 규칙이 복잡하다. 특히 여러 스레드가 동시에 고치는 환경에서 회전은 한 번에 여러 포인터를 바꿔야 해서 락 없이 구현하기가 매우 어렵다.

1990년 William Pugh 는 “균형을 규칙으로 강제하지 말고 확률로 얻자”는 제안을 했다. 논문 제목이 그대로 “스킵 리스트: 균형 트리의 확률적 대안”이다(Pugh, CACM 1990). 구조는 연결 리스트 몇 겹이 전부라 이해와 구현이 쉽고, 삽입이 국소적이라 동시성 구현에도 유리하다. 그래서 Redis 의 정렬 집합, LevelDB 의 메모리 테이블, 자바의 ConcurrentSkipListMap 같은 곳에서 쓰인다.

핵심 개념

층을 쌓은 연결 리스트

맨 아래 0층은 모든 원소를 담은 정렬 연결 리스트다. 그 위 층은 아래 층 원소 중 일부만 담는다. 위로 갈수록 듬성듬성해진다.

3층  H ─────────────────────────────────────▶ 50 ─────────────▶ ∅
2층  H ──────────────▶ 20 ──────────────────▶ 50 ─────────────▶ ∅
1층  H ──────▶ 10 ──▶ 20 ──────▶ 35 ────────▶ 50 ──────▶ 70 ──▶ ∅
0층  H ─▶ 5 ─▶ 10 ─▶ 20 ─▶ 30 ─▶ 35 ─▶ 40 ─▶ 50 ─▶ 60 ─▶ 70 ─▶ ∅

탐색: 오른쪽으로, 안 되면 아래로

40 을 찾는다고 하자. 맨 위층 머리(H)에서 시작해 다음 노드가 40 보다 작으면 오른쪽으로 가고, 크거나 끝이면 한 층 내려간다.

3층: H → (50 > 40) 내려감
2층: H → 20 → (50 > 40) 내려감
1층: 20 → 35 → (50 > 40) 내려감
0층: 35 → 40  찾음

위층은 고속도로, 아래층은 일반 도로다. 멀리는 위층으로 빨리 가고, 가까워지면 아래층으로 정밀하게 다가간다. 이진 탐색이 매번 범위를 반으로 줄이는 것과 비슷한 효과를 연결 리스트에서 낸다.

삽입: 층 수는 동전으로

새 노드를 넣을 때, 탐색하면서 각 층에서 “새 노드 바로 앞이 될 노드”를 기억해 둔다. 그리고 새 노드의 층 수를 무작위로 정한다. 확률 p(보통 1/2 이나 1/4)로 “한 층 더”를 반복한다.

층 수 확률 (p = 1/4)
1 3/4
2 3/16
3 3/64
k (1/4)^(k−1) · 3/4

그런 다음 각 층의 연결 리스트에 끼워 넣는다. 다른 노드는 건드리지 않는다. 회전도, 재배치도 없다. 삭제도 각 층에서 앞 노드의 포인터만 바꾸면 끝이다.

왜 O(log n) 인가

층 k 에 있는 노드 수의 기댓값은 n · p^(k−1) 이다. 그래서 층 수는 기대 log_{1/p} n 정도가 된다. Pugh 는 탐색 비용의 기댓값이 대략 (1/p) · log_{1/p} n 에 작은 상수를 더한 값 이하임을 보였다. 각 층에서 오른쪽으로 평균 1/p 칸 정도만 움직이고 내려가기 때문이다. 중요한 점은 이것이 입력과 무관한 기댓값이라는 것이다. 정렬된 입력이 와도 나빠지지 않는다. 운이 극도로 나쁘면 느려질 수 있지만, 그 확률은 n 이 커질수록 무시할 만큼 작아진다.

노드당 포인터 수의 기댓값은 1/(1−p) 다. p = 1/2 이면 2개, p = 1/4 이면 약 1.33개로, 균형 트리의 노드당 포인터 2개보다 적을 수도 있다. p 를 작게 하면 메모리가 줄고 탐색은 조금 길어진다.

균형 트리와 비교

항목 스킵 리스트 레드블랙 트리
보장 기대 O(log n) (확률적) 최악 O(log n)
구현 난이도 쉬움 어려움 (특히 삭제)
갱신의 국소성 앞 노드 포인터만 수정 회전으로 여러 노드 수정
동시성 락 없는 구현이 비교적 쉬움 어려움
범위 순회 0층을 그대로 따라감 중위 순회
캐시 효율 연결 리스트라 보통 보통

직접 해 보기

p = 1/4 인 스킵 리스트를 구현하고, 20만 개를 넣어 층 수 분포와 탐색 비용을 잰다.

import random, math
from collections import Counter

MAX_LEVEL, P = 32, 0.25

class Node:
    __slots__ = ("key", "next")
    def __init__(self, key, level):
        self.key, self.next = key, [None] * level

class SkipList:
    def __init__(self, seed=0):
        self.head = Node(None, MAX_LEVEL)   # 머리 노드는 모든 층에 걸쳐 있다
        self.level = 1
        self.rng = random.Random(seed)
        self.steps = 0

    def _random_level(self):                # 동전 던지기: 확률 P 로 한 층 더
        lv = 1
        while lv < MAX_LEVEL and self.rng.random() < P:
            lv += 1
        return lv

    def _find_prev(self, key):
        """각 층에서 key 직전 노드를 모은다 (위층부터 내려오며)."""
        update, x = [None] * MAX_LEVEL, self.head
        for i in range(self.level - 1, -1, -1):
            while x.next[i] and x.next[i].key < key:
                x = x.next[i]; self.steps += 1
            update[i] = x
        return update

    def contains(self, key):
        nxt = self._find_prev(key)[0].next[0]
        return nxt is not None and nxt.key == key

    def insert(self, key):
        update = self._find_prev(key)
        if update[0].next[0] and update[0].next[0].key == key:
            return
        lv = self._random_level()
        if lv > self.level:
            for i in range(self.level, lv):
                update[i] = self.head
            self.level = lv
        node = Node(key, lv)
        for i in range(lv):                  # 각 층 연결 리스트에 끼워 넣기
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

    def delete(self, key):
        update = self._find_prev(key)
        x = update[0].next[0]
        if x is None or x.key != key:
            return False
        for i in range(len(x.next)):
            update[i].next[i] = x.next[i]
        while self.level > 1 and self.head.next[self.level - 1] is None:
            self.level -= 1
        return True

    def keys(self):
        x, out = self.head.next[0], []
        while x:
            out.append(x.key); x = x.next[0]
        return out

sl = SkipList()
for k in [30, 10, 50, 20, 40]:
    sl.insert(k)
sl.delete(20)
print(sl.keys(), sl.contains(40), sl.contains(20))

N = 200_000
keys = random.Random(1).sample(range(10**9), N)
sl = SkipList(seed=2)
for k in keys:
    sl.insert(k)
assert sl.keys() == sorted(keys)
levels = Counter()
x = sl.head.next[0]
while x:
    levels[len(x.next)] += 1; x = x.next[0]
print("층 수 분포:", {lv: levels[lv] for lv in sorted(levels)})
print("평균 포인터 수/노드:", round(sum(lv * c for lv, c in levels.items()) / N, 3))
sl.steps = 0
for k in keys[:10_000]:
    sl.contains(k)
print(f"N={N:,}  최고 층={sl.level}  검색 1회 평균 전진 {sl.steps/10_000:.1f}회  log2 N={math.log2(N):.1f}")

[10, 30, 40, 50] True False
층 수 분포: {1: 150306, 2: 37334, 3: 9299, 4: 2318, 5: 548, 6: 158, 7: 29, 8: 5, 9: 3}
평균 포인터 수/노드: 1.331
N=200,000  최고 층=9  검색 1회 평균 전진 23.0회  log2 N=17.6

층 수가 대략 4분의 1씩 줄어드는 기하 분포를 그대로 따른다. 1층짜리가 75.2%, 2층이 18.7% 다. 노드당 포인터는 1.331 개로 이론값 1/(1−1/4) ≈ 1.333 과 맞는다. 20만 개에서 최고 층은 9 로 log₄ 200000 ≈ 8.8 과 비슷하고, 검색 한 번에 오른쪽으로 평균 23번 움직였다. 0층 리스트가 정렬과 정확히 일치한다는 것도 assert 로 확인했다.

현업에서는

  • Redis 정렬 집합. Redis 문서는 정렬 집합(ZSET)이 스킵 리스트와 해시 테이블을 함께 쓰는 이중 구조로 구현되어 원소 추가가 O(log N) 이고, 이미 정렬되어 있어 정렬된 결과를 요청할 때 추가 작업이 없다고 설명한다(Redis — Sorted sets). 해시 테이블은 원소 → 점수 조회를, 스킵 리스트는 점수 순서와 범위 질의를 맡는다. 리더보드, 지연 작업 큐, 시간순 인덱스에 많이 쓴다.
  • LSM 트리의 메모리 테이블. LevelDB 는 디스크에 쓰기 전 쓰기를 모아 두는 메모리 테이블을 스킵 리스트로 구현한다. 소스 주석은 쓰기에는 외부 동기화가 필요하지만 읽기는 내부 락 없이 진행된다고 적고 있고, 층을 올릴 확률 분모 kBranching 은 4 다(LevelDB skiplist.h).
  • 자바 동시성 맵. ConcurrentSkipListMap 문서는 이 클래스가 스킵 리스트의 동시성 변형으로 get·put·remove 에 기대 평균 log(n) 시간을 제공하며, 여러 스레드가 동시에 안전하게 실행할 수 있다고 적는다(Java SE 21 ConcurrentSkipListMap). 정렬된 동시성 맵이 필요하면 이것이 표준 선택이다.
  • 확률적 보장의 의미. “기대 O(log n)” 은 공격자가 입력을 골라도 깨지지 않는다(난수를 모르는 한). 해시 테이블의 HashDoS 와 비교하면, 난수 생성기가 예측 가능하지 않은 것이 전제다.

확인 문제

  1. p = 1/2 인 스킵 리스트에서 노드가 정확히 3층일 확률은?
  2. 위 그림에서 60 을 찾을 때 각 층에서 어떻게 움직이는가?
  3. 스킵 리스트 삽입에 회전 같은 재배치가 필요 없는 이유는?
  4. p 를 1/2 에서 1/4 로 바꾸면 메모리와 탐색 비용은 각각 어떻게 변하는가?
  5. Redis 정렬 집합이 스킵 리스트와 해시 테이블을 함께 두는 이유는?

풀이

  1. (1/2)² × (1/2) = 1/8. (두 번 연속 “더”, 그다음 “그만”)
  2. 3층: H → 50, 다음이 ∅ 이므로 내려감. 2층: 50 다음 ∅, 내려감. 1층: 50 → (70 > 60) 내려감. 0층: 50 → 60 찾음.
  3. 균형을 구조 규칙이 아니라 무작위 층 수로 얻기 때문이다. 새 노드는 각 층 리스트에 끼워 넣기만 하고 다른 노드의 층은 바꾸지 않는다.
  4. 노드당 포인터 기댓값이 2 → 약 1.33 으로 줄어 메모리가 줄고, 층마다 옆으로 더 많이 움직여 탐색은 조금 길어진다.
  5. 원소로 점수를 찾는 조회는 해시 테이블로 O(1), 점수 순서·순위·범위 질의는 스킵 리스트로 O(log N) 에 하려고.

더 읽을거리 (References)