스킵 리스트

컴퓨터 과학에서 **스킵 리스트**(skip list) 또는 **스킵리스트**(skiplist)는 n개의 요소로 구성된 정렬된 시퀀스 내에서 탐색에 대해 \mathcal O(\log n) 평균 복잡도를, 삽입에 대해 \mathcal O(\log n) 평균 복잡도를 허용하는 확률적 자료 구조이다. 따라서 정렬된 배열의 가장 좋은 기능(탐색용)을 얻으면서, 정적 배열로는 불가능한 삽입을 허용하는 연결 리스트와 유사한 구조를 유지할 수 있다. 빠른 탐색은 하위 시퀀스의 연결된 계층 구조를 유지함으로써 가능하며, 각 연속적인 하위 시퀀스는 이전 시퀀스보다 더 적은 요소를 건너뛴다(아래 그림 참조). 탐색은 가장 희소한 하위 시퀀스에서 시작하여, 탐색 중인 요소보다 작거나 같거나 큰 두 개의 연속적인 요소를 찾을 때까지 계속된다. 연결된 계층 구조를 통해 이 두 요소는 다음으로 희소한 하위 시퀀스의 요소에 연결되며, 최종적으로 전체 시퀀스에서 탐색이 끝날 때까지 탐색이 계속된다. 건너뛰는 요소는 확률적으로 선택될 수도 있고 결정론적으로 선택될 수도 있지만, 전자가 더 일반적이다.

## 설명
[섬네일|400px|스킵 리스트 자료 구조의 개략도. 화살표가 있는 각 상자는 포인터를 나타내고, 한 행은 희소 하위 시퀀스를 제공하는 [연결 리스트이며, 아래의 번호가 매겨진 상자(노란색)는 정렬된 데이터 시퀀스를 나타낸다. 탐색은 최상단의 가장 희소한 하위 시퀀스에서 시작하여, 탐색 요소를 둘러싸는 연속적인 요소가 발견될 때까지 아래로 진행한다.]]

스킵 리스트는 여러 계층으로 구성된다. 가장 아래 계층 1은 일반적인 정렬된 연결 리스트이다. 각 상위 계층은 아래 리스트에 대한 "고속 차선" 역할을 하며, 계층 i의 요소는 특정 고정 확률 p(일반적으로 1/2 또는 1/4)로 계층 i+1에 나타난다. 평균적으로 각 요소는 1/(1-p)개의 리스트에 나타나며, 가장 높은 요소(일반적으로 스킵 리스트의 맨 앞에 있는 특수 헤드 요소)는 모든 리스트에 나타난다. 스킵 리스트는 \log_{1/p}n\,(즉, n의 1/p를 밑으로 하는 로그)개의 리스트를 포함한다.

대상 요소를 탐색하는 것은 최상위 리스트의 헤드 요소에서 시작하여, 현재 요소가 대상보다 크거나 같을 때까지 수평으로 진행된다. 현재 요소가 대상과 같으면 발견된 것이다. 현재 요소가 대상보다 크거나, 탐색이 연결 리스트의 끝에 도달하면, 이전 요소로 돌아가서 다음 하위 리스트로 수직으로 내려간 후 절차가 반복된다. 각 연결 리스트에서 예상되는 단계 수는 최대 1/p이며, 이는 대상에서 다음 상위 리스트에 나타나는 요소에 도달하거나 현재 리스트의 시작에 도달할 때까지 탐색 경로를 역추적함으로써 알 수 있다. 따라서 p가 상수일 때 탐색의 총 예상 비용은 \tfrac{1}{p}\log_{1/p}n이며, 이는 \mathcal O(\log n)\,이다. p의 다른 값을 선택함으로써 탐색 비용과 저장 비용을 교환할 수 있다. 예를 들어, p=1/e 값은 스킵 리스트의 평균 탐색 시간을 최소화하는 반면, p=1/2 값은 구현을 단순화한다.

### 구현 세부 사항
섬네일|400px|스킵 리스트에 요소 삽입
스킵 리스트에 사용되는 요소는 여러 리스트에 참여할 수 있으므로 두 개 이상의 포인터를 포함할 수 있다.

삽입 및 삭제는 해당 연결 리스트 연산과 매우 유사하게 구현되지만, "높은" 요소는 하나 이상의 연결 리스트에 삽입되거나 삭제되어야 한다는 점이 다르다.

오름차순으로 모든 노드를 방문해야 하는 \mathcal O(n) 연산(예: 전체 리스트 인쇄)은 스킵 리스트의 레벨 구조를 최적으로 비확률화하여 \mathcal O(\log n) 탐색 시간을 가져올 기회를 제공한다. (i번째 유한 노드의 레벨은 i가 홀수가 되기 전에 2로 반복적으로 나눌 수 있는 횟수에 1을 더한 값으로 선택한다. 또한 음의 무한 헤더의 경우 i=0인데, 이는 음의 및 양의 무한 노드에 대해 가능한 가장 높은 레벨을 선택하는 일반적인 특수 사례가 있기 때문이다.) 그러나 이것은 또한 누군가가 레벨 1보다 높은 모든 노드가 어디에 있는지 알고 삭제할 수 있도록 허용한다.

대안적으로, 레벨 구조는 다음과 같이 준-무작위로 만들 수 있다.

 모든 노드를 레벨 1로 설정한다.
 j ← 1
 **while** 레벨 j의 노드 수가 1보다 클 **동안**
     **for** 레벨 j의 각 i번째 노드 **에 대해**
         **if** i가 홀수 **이고** i가 레벨 j의 마지막 노드가 아닌 **경우**
             레벨 j+1로 승격할지 무작위로 선택한다.
         **else if** i가 짝수 **이고** 노드 i-1이 승격되지 않은 **경우**
             레벨 j+1로 승격한다.
         **end if**
     **반복**
     j ← j + 1
 **반복**

비확률화된 버전과 마찬가지로, 준-무작위화는 \mathcal O(n) 연산(모든 노드를 방문하는)을 실행해야 하는 다른 이유가 있을 때만 수행된다.

이 준-무작위화의 장점은 비확률화된 버전만큼 적대적 사용자에게 레벨 구조 관련 정보를 많이 알려주지 않는다는 점이다. 이는 적대적 사용자가 최하위 레벨이 아닌 노드를 알 수 있다면 상위 레벨 노드를 단순히 삭제함으로써 성능을 악화시킬 수 있기 때문에 바람직하다. (그러나 베티아(Bethea)와 라이터(Reiter)는 그럼에도 불구하고 적대적 사용자가 확률적 및 타이밍 방법을 사용하여 성능 저하를 강요할 수 있다고 주장한다.) 탐색 성능은 여전히 로그 시간으로 보장된다.

"다음으로 각 i번째에 대해..."라는 부분에서 각 짝수-홀수 쌍에 대해 동전 던지기를 하는 것을 잊고, 짝수만 승격할지 홀수만 승격할지를 결정하기 위해 동전을 한 번만 던지는 "최적화"를 하고 싶은 유혹이 있을 수 있다. 이렇게 하면 \mathcal O(n \log n)번의 동전 던지기 대신 \mathcal O(\log n)번만 던지게 된다. 불행하게도 이것은 적대적 사용자에게 (레벨 1 이상에 있는) 짝수 번호 노드들이 모두 레벨 1보다 높다고 추측할 경우 50/50의 정확도를 제공한다. 이는 특정 노드가 정수 N인 레벨 N에 있다고 추측할 확률이 매우 낮다는 특성에도 불구하고 그렇다.

스킵 리스트는 더 전통적인 균형 트리 자료 구조와 같은 절대적인 최악의 경우 성능 보장을 제공하지 않는다. 스킵 리스트를 구축하는 데 사용되는 동전 던지기가 심하게 불균형한 구조를 생성할 가능성(매우 낮지만)이 항상 있기 때문이다. 그러나 스킵 리스트는 실제로 잘 작동하며, 무작위 균형 조정 방식은 균형 이진 탐색 트리에서 사용되는 결정론적 균형 조정 방식보다 구현하기 쉽다고 주장되어 왔다. 스킵 리스트는 병렬 컴퓨팅에서도 유용하며, 자료 구조의 전역적인 재균형 조정 없이 스킵 리스트의 다른 부분에 삽입을 병렬로 수행할 수 있다. 이러한 병렬 처리는 애드혹 무선망에서 자원 발견에 특히 유리할 수 있는데, 무작위 스킵 리스트는 단일 노드의 손실에 대해 견고하게 만들 수 있기 때문이다.

### 인덱싱 가능한 스킵 리스트
위에서 설명한 바와 같이 스킵 리스트는 정렬된 시퀀스에서 값을 \mathcal O(\log n) 시간으로 빠르게 삽입하고 제거할 수 있지만, 시퀀스의 주어진 위치에서 값을 찾는 데는 \mathcal O(n) 시간이 걸린다(즉, 500번째 값 반환). 그러나 약간의 수정으로 임의 접근 인덱싱 조회 속도를 \mathcal O(\log n)으로 향상시킬 수 있다.

모든 링크에 대해 링크의 너비도 저장한다. 너비는 각 상위 계층 "고속 차선" 링크가 이동하는 최하위 계층 링크의 수로 정의된다.

예를 들어, 페이지 상단 예시에서 링크의 너비는 다음과 같다.

    1                               10
  o---> o---------------------------------------------------------> o    최상위 레벨
    1           3              2                    5
  o---> o---------------> o---------> o---------------------------> o    레벨 3
    1        2        1        2              3              2
  o---> o---------> o---> o---------> o---------------> o---------> o    레벨 2
    1     1     1     1     1     1     1     1     1     1     1
  o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    최하위 레벨
 Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
       Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

상위 레벨 링크의 너비는 그 아래에 있는 구성 링크의 합과 같다(예: 너비 10 링크는 바로 아래의 너비 3, 2, 5 링크를 포함한다). 결과적으로 모든 너비의 합은 모든 레벨에서 동일하다(10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

스킵 리스트를 인덱싱하고 i번째 값을 찾으려면, 스킵 리스트를 탐색하면서 각 이동된 링크의 너비를 세어 내려간다. 다가오는 너비가 너무 크면 한 레벨 아래로 내려간다.

예를 들어, 다섯 번째 위치(노드 5)의 노드를 찾으려면 최상위 레벨에서 너비 1의 링크를 이동한다. 이제 네 단계가 더 필요하지만 이 레벨의 다음 너비는 10으로 너무 크므로 한 레벨 아래로 내려간다. 너비 3의 링크 하나를 이동한다. 너비 2의 또 다른 단계는 너무 멀 것이므로 최하위 레벨로 내려간다. 이제 너비 1의 마지막 링크를 이동하여 목표 총합 5(1+3+1)에 도달한다.

 **function** lookupByPositionIndex(i)
     node ← head
     i ← i + 1                           # 헤드를 단계로 세지 않는다.
     **for** level **from** top **to** bottom **do**
         **while** i ≥ node.width[level] **do** # 다음 단계가 너무 멀지 않으면
             i ← i - node.width[level]  # 현재 너비를 뺀다.
             node ← node.next[level]    # 현재 레벨에서 앞으로 이동한다.
         **repeat**
     **repeat**
     **return** node.value
 **end function**

이 인덱싱 구현 방법은 윌리엄 푸(William Pugh)의 "A skip list cookbook"에 자세히 설명되어 있다.

## 역사
스킵 리스트는 1989년 윌리엄 푸에 의해 처음 기술되었다.

저자의 말을 인용하자면:

## 활용
스킵 리스트를 사용하는 응용 프로그램 및 프레임워크 목록:
* 아파치 포터블 런타임은 스킵 리스트를 구현한다.
* MemSQL은 잠금 없는 스킵 리스트를 데이터베이스 기술의 주요 인덱싱 구조로 사용한다.
* 리눅스 커널용 MuQSS는 스킵 리스트를 기반으로 구축된 CPU 스케줄러이다.
* Cyrus IMAP 서버는 "스킵 리스트" 백엔드 DB 구현을 제공한다.
* Lucene은 스킵 리스트를 사용하여 델타 인코딩된 포스팅 리스트를 로그 시간에 탐색한다.
* Qt의 "QMap" 키/값 딕셔너리(Qt 4까지) 템플릿 클래스는 스킵 리스트로 구현된다.
* 레디스는 Posix 시스템용 ANSI-C 오픈 소스 영구 키/값 저장소로, 정렬된 집합 구현에 스킵 리스트를 사용한다.
* 디스코드는 스킵 리스트를 사용하여 서버의 멤버 목록을 저장하고 업데이트한다.
* 자바는 ConcurrentSkipListSet 및 ConcurrentSkipListMap에 스킵 리스트를 사용한다.
* RocksDB는 기본 Memtable 구현에 스킵 리스트를 사용한다.

스킵 리스트는 분산 응용 프로그램(노드가 물리적 컴퓨터를 나타내고 포인터가 네트워크 연결을 나타내는)에서도 사용되며, 잠금 경합이 적은 고도로 확장 가능한 동시 우선순위 큐를 구현하는 데 사용된다. 또는 잠금 없이도, 잠금 없는 동시 딕셔너리 구현에도 사용된다. 스킵 리스트를 사용하여 (잠금 없는) 우선순위 큐 및 동시 딕셔너리를 구현하기 위한 여러 미국 특허도 있다.

## 같이 보기
* 블룸 필터
* 스킵 그래프

## 각주

## 외부 링크

* 알고리즘 및 자료 구조 사전의 "스킵 리스트" 항목
* 스킵 리스트 강의 (MIT OpenCourseWare: 알고리즘 개론)
* 오픈 자료 구조 - 챕터 4 - 스킵 리스트, 팻 모린
* 스킵 트리의 분산 버전인 스킵 트리 그래프
* 스킵 트리의 분산 버전인 스킵 트리 그래프에 대한 추가 정보

분류:연결 리스트
분류:확률적 자료 구조