스킵 리스트 원리 쉽게 이해하기: 동전 던지기로 O(log n) 검색을 만드는 자료구조

핵심 메시지

• 정렬된 연결 리스트는 삽입과 삭제가 상수 시간으로 값싸지만, 검색은 앞에서부터 하나씩 훑어야 해서 O(n)이 된다.
• 값의 절반만 담은 '급행 차선'을 위에 얹고 이를 반복해 쌓으면, 층마다 남은 구간이 절반으로 줄어 O(log n) 검색이 된다.
• 층을 정확히 2분의 1로 유지하려면 삽입·삭제마다 위층까지 연쇄 수정이 필요해, 균형 이진 트리의 회전과 같은 부담이 생긴다.
• 1990년 윌리엄 퓨는 구조를 관리하지 않는 해법을 택했다. 새 값이 들어오면 동전을 던져 앞면이 나오는 동안 위층으로 올린다.
• 재조정 로직 없이도 확률적으로 log n 높이가 유지되며, 레디스·레벨DB·록스DB·자바 표준 라이브러리가 실제로 이 구조를 쓴다.

쉽게 이해하기

정렬된 연결 리스트는 순서를 지키는 자료구조 중에서 가장 유연한 축에 속한다. 어느 위치든 값을 끼워 넣거나 빼내는 일이 상수 시간에 끝나고, 다른 원소를 복사하거나 밀어낼 필요도 없다. 문제는 검색이다. 특정 값을 찾으려면 맨 앞에서 시작해 한 칸씩 이동하며 값을 비교하는 방법밖에 없다. 영상의 예시에서 55를 찾는 데 여섯 칸을 지나쳐야 했는데, 원소가 100만 개라면 최악의 경우 100만 번 비교하게 된다.

해법의 출발점은 리스트 위에 또 하나의 리스트를 얹는 것이다. 아래층 값 중 한 칸 건너 하나씩만 담은 '급행 차선'을 만들고, 급행 노드마다 아래층의 같은 값으로 내려가는 포인터와 다음 급행 노드로 가는 포인터를 둔다. 55를 찾을 때 급행 차선을 타고 3에서 19, 42까지 건너뛰다가 다음 정거장인 67이 목표를 지나쳐 버리면 그 자리에서 아래층으로 내려와 한 칸만 걸으면 된다. 작업량이 대략 절반으로 줄어든 셈이다.

같은 일을 반복하지 못할 이유가 없다. 급행 차선 위에 다시 절반만 담은 층을 올리고, 그 위에 또 한 층을 올린다. 층을 올라갈수록 값이 절반씩 성기게 배치된 탑이 만들어지고, 검색은 지그재그 모양이 된다. 맨 위 왼쪽에서 시작해 다음 값이 목표보다 작거나 같은 동안 오른쪽으로 가다가, 목표를 넘어서는 순간 한 층 내려가 다시 시도한다. 층마다 남은 작업이 절반으로 줄어들기 때문에 log n번의 층을 거치면 답에 도달한다. 연결 리스트 위에서 O(log n) 검색이 나온 것이다.

다만 이 구조에는 심각한 문제가 하나 있다. '정확히 한 칸 건너 하나'라는 배치를 유지하려면 값이 하나 삽입되거나 삭제될 때마다 위층 전체가 연쇄적으로 흔들린다. 균형 이진 트리가 회전으로 겪는 골칫거리와 성격이 같다. 1990년에 스킵 리스트를 고안한 윌리엄 퓨는 여기서 방향을 틀었다. 구조를 관리하려 들지 말자는 것이다. 새 값이 들어오면 동전을 던져 앞면이면 한 층 올리고, 또 앞면이면 한 번 더 올리고, 뒷면이 나오면 멈춘다. 탑의 높이는 전적으로 우연이 정한다.

무작위로 정한 높이가 어떻게 제 역할을 하는지는 분포를 보면 드러난다. 높이가 1일 확률은 2분의 1, 2일 확률은 4분의 1, 3일 확률은 8분의 1이고, 일반적으로 높이 k일 확률은 2의 k제곱분의 1인 기하분포를 따른다. 노드의 평균 높이는 2 정도지만, 노드가 n개 있으면 가장 높은 탑은 사실상 확실하게 log n에 도달한다. 재조정 로직을 한 줄도 쓰지 않고도 구조가 log n 높이를 유지하는 이유다.

주요 인사이트

• 스킵 리스트는 검색·삽입·삭제가 모두 O(log n)인데, 균형을 잡는 전략 전체가 동전 던지기 두 줄로 끝난다. 회전 같은 복잡한 불변식 관리 코드를 통째로 지울 수 있다는 뜻이다.
• 이론적 호기심에 그치는 구조가 아니다. 레디스는 정렬 집합(sorted set)을 스킵 리스트로 저장하기 때문에, 리더보드나 시간순 큐 같은 기능은 사실상 이 구조 위에서 돌아간다.
• 레벨DB와 록스DB는 디스크에 쓰기 전 데이터를 모아 두는 인메모리 멤테이블에 스킵 리스트를 쓴다. 자바 표준 라이브러리에도 ConcurrentSkipListMap이 들어 있는데, 균형 트리보다 락 프리로 만들기 쉽다는 점이 이유로 꼽힌다.
• 이 사례의 교훈은 자료구조 하나에 그치지 않는다. 무작위성은 똑똑하지 못해서 택하는 임시방편이 아니라, 불변식 관리 코드를 통째로 걷어내고 더 빠르고 작고 이해하기 쉬운 결과를 만드는 단순화 전략일 수 있다는 것이다.

자주 묻는 질문

관련 AI 소식