TL;DR

  • 스킵 리스트(Skip List)는 확률적 계층형 연결 리스트로, HNSW와 벡터 데이터베이스 인덱싱 등에 사용되며 평균 검색·삽입·삭제 시간 복잡도가 O(log n)임.
  • 일반 연결 리스트는 임의 접근이 불가능해 원하는 위치를 찾는 데 O(n) 시간이 들고, 가운데로 바로 이동하기 어려움.
  • 스킵 리스트는 정렬된 연결 리스트 위에 더 성긴 계층을 구성하고, 각 계층에서 오른쪽으로 이동하거나 아래 계층으로 내려가며 검색함.
  • 새 노드의 삽입 위치를 찾을 때 계층별 선행 노드를 기록하고, p = 1/2 동전 던지기로 노드의 높이를 무작위 결정함.
  • 삭제할 노드를 검색한 뒤 각 계층에서 제거하고, 선행 노드가 삭제된 노드 다음 노드를 가리키도록 연결함.

연결 리스트의 단점

  • 연결 리스트(Linked List)는 값이 비연속 메모리에 저장된 노드로 구성되는 동적 자료 구조이며, 각 노드는 메모리 포인터로 다음 노드를 참조함.
  • 필요한 메모리 크기를 미리 추정하지 않아도 되는 장점이 있음.
  • 배열은 임의 접근이 빠르지만, 삽입·삭제 때 공간을 만들거나 빈틈을 메우려고 요소를 이동해야 하므로 느림.
  • 연결 리스트는 올바른 위치를 찾은 뒤에는 삽입·삭제가 빠르지만, 임의 접근이 없어 해당 위치까지 이동하는 데 시간이 듦.
  • 일반 연결 리스트의 주요 한계는 다음과 같음.
  • O(n)보다 빠른 검색이 어려우며, 예를 들어 이진 검색을 적용할 수 없음.
  • 가운데 위치로 바로 이동하기 어려움.
  • 스킵 리스트는 이 연결 리스트의 검색 한계를 해결해 검색 시간을 O(log n)으로 낮추는 구조임.

스킵 리스트 자료 구조

  • 스킵 리스트는 여러 계층의 연결 리스트로 구성되는 확률적 자료 구조임. 무작위 동전 던지기로 구조를 만들기 때문에 확률적 자료 구조라고 부름.
  • 가장 아래 계층은 정렬된 요소를 순서대로 연결하는 일반 연결 리스트임.
  • 위쪽 계층마다 고정된 확률에 따라 아래 계층의 일부 요소를 제외해 더 성긴 리스트를 구성함.

스킵 리스트의 검색 방식

  • 검색은 가장 위 계층에서 시작해 해당 연결 리스트를 따라 수평으로 이동함.
  • 위 계층에서 목표 요소를 찾으면 즉시 반환함. 성긴 계층에서 요소를 일찍 찾을수록 확인해야 하는 노드 수가 줄어들어 시간 복잡도가 낮아짐.
  • 키 k를 검색할 때의 동작은 다음과 같음.
  • k가 현재 키와 같으면 검색을 마침.
  • k가 다음 키보다 작으면 한 계층 아래로 내려감.
  • k가 다음 키 이상이면 오른쪽으로 이동함.
  • 이 방식으로 스킵 리스트는 검색, 삽입, 삭제 모두 평균 O(log n) 시간 복잡도를 제공함.
  • 예시로 70 찾기가 제시됨.
  • 이해를 돕는 애니메이션 설명 영상도 언급됨.

스킵 리스트의 삽입 방식

  • 새 키를 삽입할 위치를 찾기 위해 먼저 가장 아래 계층에서 검색을 수행함.
  • 검색 중 계층별로 마지막에 방문한 노드를 기록함. 이 선행 노드들이 삽입 후 새 노드를 가리키게 됨.
  • 아래 계층에서 더 오른쪽으로 이동할 수 없는 위치를 찾으면 그 위치의 오른쪽에 새 값을 삽입함.
  • 새 노드를 위 계층에도 추가할지는 공정한 동전 던지기(p = 1/2)로 결정함.
  • 앞면이면 한 계층 위로 올림.
  • 뒷면이면 승격을 멈춤.
  • 앞면 뒤 뒷면이 나오면 노드는 Level 1까지 도달함.
  • 동전 던지기가 노드의 높이를 무작위로 결정하므로 스킵 리스트는 확률적 구조임.
  • 예시로 67 삽입이 제시됨.

스킵 리스트의 삭제 방식

  • 먼저 검색을 수행해 삭제할 노드의 위치를 찾음.
  • 노드를 찾으면 모든 계층에서 제거함.
  • 삭제 전에 계층별 선행 노드를 기록하고, 삭제된 노드의 선행 노드가 그 다음 노드를 직접 가리키도록 연결함.
  • 예시로 70 삭제와 31 삭제가 제시됨.