Skip List

스킵리스트란

• Logt시간에 검색, 추가, 제거를 수행할 수 있는 정렬된 자료구조
• 이진검색트리 대체 가능
• 스킵 포인터를 이용해 빠르게 탐색

스킵리스트 아이디어

Skip List는 LinkedLis에서 조금 더 빠르게 데이터를 검색할 수 있기 위해 고안한 자료구조이다.

한 칸씩 skip

• 빠르게 검색하기 위해, 한 칸씩 skip하며 검색을 한다면?
  • 메모리 : 1/2N 만큼 더 사용
  • 검색 : 최대 1/2 + 1 노드 검사

한 번 더 skip

• 한 칸이 아니라, 4칸에 한 번씩(한번 더 skip)을 진행하게 된다면?
  • 메모리 : (1/2 + 1/4) N = 3/4N 만큼 더 사용
  • 검색 : 최대 N/4 + 3 노드를 검사

계속 적용한다면..?

• 2^i번째 노드에 2^i개의 포인터를 가지도록 만든다면?
  • 메모리 : N만큼 더 사용
  • 속도 : O(logN) 개의 노드를 검사
• 이는 이진검색트리와 동일하다.

동적 데이터 구조로서의 한계

• 중간에 노드 추가/삭제시 패턴이 무너지게되 처음부터 포인터를 다시 만들어야함
• 최대 O(N)의 시간이 소요될 수 있음

해결 방법 :

• 포인터 크기의 확률분포를 유지
• 규칙적인 패턴을 유지할 필요가 없어지기에 앞선 문제를 해결할 수 있다.

연결리스트와의 차이점

• 연결리스트는 하나의 next 포인터를 가진다.
• skiplist는 다수의 next포인터를 가지며, 이를 Forward 포인터라고 한다.
• 최상의 경우 O(logn)의 효율을 가지지만, 최악의 경우 O(n)의 복잡도를 가진다.

---

노드 검색

• 가장 상위 리스트부터 검색을 시작한다.
• 현재 위치의 다음 element가 찾으려는 값보다 크면 아래로 내려가고, 아니면 포인터가 가르키는 다음 노드로 이동한다.

노드 삽입

• 노드 삽입시 제일 중요한 건, 노드의 크기(포인터를 몇개 둘 것인지)이다.
• 노드의 크기는 확률적으로 정한다.
• 예를 들어 15를 insert한다고 가정해보자.
  • 15보다 작은 수까지 검색한다.
  • 검색이 종료된 위치를 Predecessor Key라하며, 다음 위치에 15를 합입한다.
  • 삽입할 때 확률로 노드의 크기를 정해 삽입한다.

노드 삭제

• 가장 상위의 포인터부터 순차적으로 제거해준다.

  스킵리스트은 언제 자주 쓰일까?

• 멀테쓰레드 환경에서 자주 수정할 컨테이너가 필요할 때
• 순차적으로 탐색할 필요가 많은 경우
• 정렬이 필요 없으면 HashTable을 쓰는 것이 더 효율적이다.
• Redit, ConcurrentSkipListMap/Set에서 이 원리를 기반으로 적용하였다.

정리

• 스킵리스트는 결국 정렬을 유지하며 빠르게 삽입/삭제/검색을 할 수 있ㄷ록 지원하는 자료구조이다.
• tree와 비슷하게 리밸런싱시 락이 발생할 수 있지만, 트리에 비해서는 확률이 훨씬 적다.

---

참고자료 : Skip List 스킵리스트(Skip List)