스킵 리스트 (Skip List)
쉽게 풀면
완행열차만 다니는 노선에서 특정 역을 찾으려면 한 정거장씩 세면서 가야 합니다. 그런데 그 위에 급행열차 노선을 하나 더 놓고, 그 위에 더 빠른 초급행 노선까지 놓는다면 목적지 근처까지 빠르게 이동한 뒤 마지막에만 완행으로 갈아타면 됩니다. 스킵 리스트가 바로 이런 구조입니다. 기본은 순서대로 나열된 연결 리스트이지만, 일부 노드를 무작위로 골라 한 단계 위 지름길 리스트에도 포함시키고, 그 위에 또 무작위로 골라 지름길의 지름길을 만드는 식으로 여러 층을 쌓습니다. 그 결과 이진탐색트리처럼 복잡한 회전 로직 없이도 평균적으로 로그 시간(log n)에 검색·삽입·삭제가 가능합니다.
왜 중요한가
스킵 리스트는 회전 연산 없이도 로그 시간 성능을 제공하기 때문에, 동시성 제어와 분산 시스템처럼 자료구조 수정이 잦고 병렬 접근이 빈번한 연구 분야에서 균형 트리의 실용적 대안으로 자주 다뤄집니다. 또한 구조가 단순해 정확성 증명이나 락-프리(lock-free) 알고리즘 설계 연구의 기반 자료구조로도 널리 채택되어, 데이터베이스 인덱싱과 인메모리 스토리지 시스템 연구와도 밀접하게 연결됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 여러 스레드가 동시에 데이터를 읽고 쓰는 시스템에서, 트리 회전처럼 복잡한 재조정 작업이 필요 없는 스킵 리스트가 병렬 처리에 더 유리하다는 설계 근거를 설명한 것입니다. 데이터베이스 인덱스(예: Redis의 정렬 집합), 분산 시스템, 동시성 자료구조 연구에서 자주 언급됩니다.
동시성 알고리즘 논문에서는 스킵 리스트가 락-프리 자료구조 설계의 대표적인 실험 대상으로 쓰이며, CAS 같은 원자적 연산과 결합해 잠금 없는 구현이 가능한지를 검증하는 데 활용된다.
데이터베이스 시스템 논문에서는 스킵 리스트의 원리를 다차원 데이터 인덱싱에 확장 적용해, 범위 검색 성능을 개선하는 목적으로도 인용된다.
조금 더 깊게 보면
스킵 리스트의 성능은 각 노드가 상위 층에 포함될 확률(흔히 1/2 또는 1/4)에 따라 달라지며, 이 확률값이 층의 개수와 탐색 속도 사이의 트레이드오프를 결정합니다. 동시성 환경에서 구현할 때는 노드를 삽입·삭제하는 동안 다른 스레드가 중간 상태를 관찰하지 않도록 하는 것이 중요한데, 이를 위해 컴페어-앤-스왑(CAS) 같은 원자적 연산을 활용한 락-프리 구현이 널리 연구되고 있습니다. 이런 특성 때문에 스킵 리스트는 이론적 논문뿐 아니라 실제 시스템 구현 논문에서도 자주 비교 대상으로 등장합니다.
주의할 점
스킵 리스트의 빠른 성능은 "무작위로 층을 정한다"는 확률적 특성에 기반합니다. 즉 최악의 경우(운이 매우 나쁘면) 성능이 일반 연결 리스트만큼 느려질 수도 있지만, 그 확률은 매우 낮습니다. 이 점에서 항상 균형을 보장하는 이진탐색트리와는 달리, 스킵 리스트는 "평균적으로" 빠른 것이지 "항상" 빠른 것을 수학적으로 보장하지는 않습니다.