스킵 리스트
정렬된 연결 리스트는 삽입과 삭제가 쉽지만 원하는 값을 찾으려면 처음부터 하나씩 지나야 해서 탐색이 O(n)입니다. 배열은 이진 탐색으로 O(log n)에 찾지만 중간에 끼워 넣으려면 원소를 밀어야 합니다. 스킵 리스트(skip list)는 정렬된 연결 리스트 위에 "빠른 길"을 여러 층 얹어, 위층에서 크게 건너뛰며 탐색을 평균 O(log n)으로 줄인 자료구조입니다.
핵심은 각 노드가 몇 층까지 올라갈지를 동전 던지기로 정한다는 점입니다. 앞면이 나오는 동안 한 층씩 올라가므로 위층으로 갈수록 노드 수가 대략 절반씩 줄고, 이 분포가 이진 탐색과 비슷한 구조를 확률적으로 만들어 줍니다. 균형 트리처럼 회전이나 재배치 규칙이 없어 구현이 단순하다는 것이 장점입니다. 이 토픽에서는 층이 쌓이는 과정, 탐색 경로, 삽입 때 고치는 포인터를 단계별로 봅니다.
핵심 개념
층(레벨)
맨 아래층(L1)은 모든 노드를 이은 정렬된 연결 리스트이고, 위층은 그 일부만 골라 이은 리스트입니다. 위층일수록 노드가 적어 한 번에 더 멀리 건너뜁니다.
핵심 개념
머리 노드
모든 층에 걸쳐 있는 맨 앞 노드로, 탐색은 항상 여기서 맨 위층부터 시작합니다. 층마다 다음 노드를 가리키는 포인터를 하나씩 가집니다.
핵심 개념
동전 던지기로 높이 결정
새 노드는 앞면이 나오는 동안 한 층씩 올라가고 뒷면에서 멈춥니다. 앞면 확률이 1/2이면 높이가 k 이상일 확률은 1/2의 (k-1)제곱입니다.
핵심 개념
탐색
맨 위층에서 시작해, 오른쪽 다음 노드가 찾는 키보다 작으면 오른쪽으로 가고 아니면 한 층 내려갑니다. 맨 아래층에서 다음 노드가 찾는 키인지 확인합니다.
핵심 개념
삽입과 삭제
탐색하며 층마다 바로 앞 노드를 기록해 두고, 그 노드들의 포인터를 새 노드로 이어 붙이거나 건너뛰게 바꿉니다. 삽입은 노드 높이만큼의 층에서 포인터 두 개(앞 노드와 새 노드)씩, 삭제는 층마다 앞 노드의 포인터 하나씩만 고칩니다.
핵심 개념
확률적 균형
균형이 입력 순서가 아니라 동전 던지기 결과에 달려 있어, 정렬된 입력이 들어와도 기대 성능이 유지됩니다. 대신 보장은 평균과 높은 확률 수준이고 최악은 O(n)입니다.
스킵 리스트의 배경
스킵 리스트는 윌리엄 퓨(William Pugh)가 1990년 논문 "Skip Lists: A Probabilistic Alternative to Balanced Trees"에서 소개했습니다. 균형 트리는 삽입과 삭제 때 구조를 복잡하게 바로잡아야 하지만, 확률을 이용하면 훨씬 단순한 알고리즘으로 비슷한 성능을 낼 수 있다는 것이 논문의 주장입니다. 이후 인메모리 저장소와 데이터베이스의 정렬된 구조에 쓰이게 되었습니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
스킵 리스트는 어떻게 O(log n) 탐색을 하나요?
정렬된 연결 리스트 위에 점점 성긴 층을 쌓아, 위층에서 크게 건너뛰고 아래층에서 범위를 좁힙니다. 층 수가 log n 정도라 평균 O(log n)입니다.
면접 질문
노드의 높이는 어떻게 정하나요?
동전을 던져 앞면이면 한 층 올리고 뒷면이면 멈춥니다. 위층으로 갈수록 노드 수가 절반씩 줄어드는 분포가 평균적으로 만들어집니다.
면접 질문
균형 트리와 비교하면?
구현이 단순하고 삽입이 국소적이라 동시성에 유리합니다. 대신 성능 보장이 확률적입니다.
면접 질문
어디에 쓰이나요?
Redis의 정렬 집합(Sorted Set)이 원소가 많아지면 스킵 리스트를 쓰고, 자바의 ConcurrentSkipListMap이 동시성을 지원하는 정렬 맵으로 제공됩니다. LevelDB 같은 저장소의 메모리 테이블에도 쓰입니다.
실제 시스템에서는
함께 보면 좋은 토픽
참고 자료
Python — 스킵 리스트 탐색과 삽입
import random class Node: def __init__(self, key, level): self.key = key self.next = [None] * level # next[i]는 레벨 i의 다음 노드 class SkipList: MAX_LEVEL = 16 def __init__(self, seed=None): self.head = Node(None, self.MAX_LEVEL) self.level = 1 # 지금 쓰는 최대 레벨 self.rng = random.Random(seed) def _random_level(self): lv = 1 while lv < self.MAX_LEVEL and self.rng.random() < 0.5: lv += 1 # 앞면이면 한 레벨 올린다 return lv def search(self, key): node = self.head for i in range(self.level - 1, -1, -1): while node.next[i] and node.next[i].key < key: node = node.next[i] # 오른쪽으로 이동 node = node.next[0] # 맨 아래층에서 확인 return node is not None and node.key == key def insert(self, key): update = [self.head] * self.MAX_LEVEL node = self.head for i in range(self.level - 1, -1, -1): while node.next[i] and node.next[i].key < key: node = node.next[i] update[i] = node # 레벨 i에서 key 바로 앞 노드 lv = self._random_level() self.level = max(self.level, lv) new = Node(key, lv) for i in range(lv): new.next[i] = update[i].next[i] update[i].next[i] = new sl = SkipList(seed=7) for k in [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]: sl.insert(k) print(sl.search(21), sl.search(14)) # True False sl.insert(14) print(sl.search(14)) # True
각 노드는 레벨 수만큼의 next 포인터 배열을 가지고, 머리 노드는 모든 레벨에 걸쳐 있습니다. search는 맨 위 레벨에서 시작해 오른쪽 다음 노드의 키가 찾는 키보다 작으면 오른쪽으로 가고, 아니면 한 레벨 내려갑니다. 맨 아래 레벨에서 다음 노드가 찾는 키인지 확인하면 끝납니다. 시각화의 탐색 탭이 그리는 경로와 같은 알고리즘입니다(노드의 높이는 시각화의 고정값과 다릅니다). insert는 같은 방식으로 내려가며 레벨마다 key 바로 앞 노드를 update 배열에 기록합니다. 동전 던지기로 새 노드의 레벨을 정하고, 그 레벨들에서만 앞 노드와 새 노드의 포인터를 이어 붙입니다. 연결 리스트의 삽입과 같은 포인터 두 개 수정이어서 회전이 없습니다. 21은 있고 14는 넣기 전에는 없으므로 True False이고, 14를 넣은 뒤에는 True입니다. 시드를 7로 고정해서 실행할 때마다 같은 구조가 만들어집니다.
Python — 레벨 분포 확인
import random rng = random.Random(1) N = 100000 counts = [0] * 20 for _ in range(N): lv = 1 while rng.random() < 0.5: # 앞면이면 한 레벨 올린다 lv += 1 for i in range(lv): counts[i] += 1 # 레벨 i 이하에 노드가 있다 print(counts[:6]) # [100000, 50171, 24929, 12464, 6127, 3071] print(round(sum(counts) / N, 2)) # 2.0 (노드당 평균 포인터 수)
노드 10만 개에 동전 던지기로 높이를 정하면 레벨 1에는 10만 개, 레벨 2에는 약 절반인 5만 개, 레벨 3에는 약 2만 5천 개가 남습니다. 위 레벨로 갈수록 노드 수가 대략 절반씩 줄어드는 것이 시각화의 레벨 구성 탭에서 본 모양입니다. 레벨 수는 대략 log2(n)이고, 노드당 평균 포인터 수는 1 + 1/2 + 1/4 + ... = 2에 가깝습니다. 그래서 포인터 수는 연결 리스트의 두 배 정도이고, 탐색은 층마다 평균 두 번쯤(오른쪽 약 1번, 아래 1번)만 움직입니다. 확률이 1/2 대신 1/4이면 평균 포인터 수가 약 1.33으로 줄고, 레벨당 이동은 늘지만 레벨 수가 줄어 기대 탐색 비용은 비슷합니다. 논문은 1/4를 권장합니다.
Java — ConcurrentSkipListMap 사용
import java.util.concurrent.ConcurrentSkipListMap; ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>(); map.put(30, "c"); map.put(10, "a"); map.put(20, "b"); map.put(40, "d"); System.out.println(map.firstKey()); // 10 System.out.println(map.floorKey(25)); // 20 (25 이하 중 가장 큰 키) System.out.println(map.ceilingKey(25)); // 30 (25 이상 중 가장 작은 키) System.out.println(map.subMap(10, 30)); // {10=a, 20=b} (10 이상 30 미만)
자바의 ConcurrentSkipListMap은 스킵 리스트를 바탕으로 한 정렬된 맵으로, 여러 스레드가 동시에 읽고 써도 안전하도록 설계되어 있습니다. 키를 정렬된 순서로 유지하므로 firstKey, floorKey, ceilingKey, subMap 같은 범위 질의를 쓸 수 있습니다. TreeMap과 인터페이스가 비슷하지만 TreeMap은 동기화가 없어서 여러 스레드가 함께 쓰려면 바깥에서 잠금을 걸어야 합니다. 스킵 리스트는 삽입이 포인터 몇 개를 바꾸는 국소적인 일이라, 락 없이 비교 후 교체(CAS) 방식으로 동시성을 다루기 쉬운 구조입니다. 정렬이 필요 없고 단일 스레드라면 해시 맵이 평균 O(1)로 더 빠르므로, 정렬된 순서와 동시 접근이 함께 필요한 곳에 고르는 것이 일반적입니다.
Q1
스킵 리스트가 평균적으로 O(log n) 탐색을 달성하는 방법은?
Q2
스킵 리스트에서 새 노드가 몇 개 레벨에 걸쳐 존재할지는 어떻게 정할까?
Q3
스킵 리스트가 실제로 사용되는 예로 알맞은 것은?