Skip List의 정의
Skip List(스킵 리스트)는 정렬된 데이터를 빠르게 탐색하기 위해 고안된 확률적 자료구조입니다. 이름 그대로 일부 노드를 ‘건너뛰면서(skip)’ 탐색 속도를 높이는 방식인데, 기본적으로는 연결 리스트(Linked List)를 여러 층으로 쌓아 올린 구조라고 이해하면 됩니다. 일반 연결 리스트는 원하는 값을 찾으려면 처음부터 하나씩 확인해야 해서 탐색에 O(n)의 시간이 걸리지만, Skip List는 평균적으로 O(log n)의 탐색 성능을 제공합니다. 그러면서도 균형 이진 트리처럼 복잡한 회전 로직 없이 구현할 수 있다는 장점이 있습니다.
동작 원리와 예시
Skip List를 이해하는 가장 쉬운 비유는 ‘지하철 완행열차와 급행열차’입니다. 완행열차는 모든 역에 정차하지만, 급행열차는 주요 역만 골라서 정차합니다. 목적지가 급행 정차역 근처라면 급행을 타고 빠르게 이동한 뒤, 마지막에 완행으로 갈아타면 훨씬 빠르게 도착할 수 있습니다.
Skip List도 마찬가지로 여러 ‘레벨(층)’의 리스트를 가지고 있습니다. 맨 아래 레벨(Level 0)에는 모든 데이터가 정렬된 상태로 연결되어 있고, 위로 올라갈수록 노드 개수가 줄어들며 일부 노드만 연결됩니다. 예를 들어 값이 1, 3, 5, 7, 9, 11인 데이터가 있다면, 상위 레벨에는 1, 5, 9처럼 일부만 존재할 수 있습니다.
탐색은 최상위 레벨에서 시작해서 찾는 값보다 크지 않은 노드까지 이동한 뒤, 더 이상 진행할 수 없으면 한 단계 아래 레벨로 내려가는 방식으로 진행됩니다. 이렇게 하면 불필요한 노드를 여러 개 건너뛸 수 있어 탐색 속도가 크게 향상됩니다. 각 노드가 상위 레벨에 포함될지 여부는 동전 던지기처럼 확률(보통 1/2)로 결정되기 때문에 ‘확률적 자료구조’라고 부릅니다.
실무에서 왜 쓰는가
Skip List는 균형 트리와 비슷한 성능을 제공하면서도 구현이 훨씬 단순하다는 점 때문에 실무에서 널리 쓰입니다. 대표적인 사례가 Redis의 Sorted Set(ZSET)입니다. Redis는 점수(score) 기준으로 정렬된 데이터를 빠르게 추가, 삭제, 범위 검색해야 하는데, 이때 내부적으로 Skip List를 사용합니다.
또한 LevelDB, RocksDB 같은 키-값 저장소의 메모리 내 정렬 구조(MemTable)에서도 Skip List가 활용됩니다. 동시성 환경에서 락(lock) 경합을 최소화하며 삽입과 탐색을 처리하기에 유리하기 때문입니다. 정리하면 Skip List는 ‘단순한 구현으로 로그 시간 복잡도를 얻고 싶을 때’ 선택하는 실용적인 자료구조라고 할 수 있습니다.