Skip List는 어떤 아이디어로 빠른 탐색을 제공하나요?

Skip List는 정렬된 연결 리스트 위에 여러 단계의 빠른 길을 확률적으로 추가해 평균 O(log n) 탐색을 제공하는 자료구조입니다. 균형 트리처럼 정렬 순서를 유지하면서도 구현 아이디어가 비교적 단순합니다.

핵심 개념

• 가장 아래 레벨은 모든 원소를 포함한 정렬 연결 리스트입니다.
• 위 레벨은 일부 원소만 포함해 고속도로처럼 여러 노드를 건너뜁니다.
• 삽입 시 동전 던지기 같은 확률 과정으로 노드 높이를 정해 평균 균형을 유지합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

Level 3: 1 -------------------- 17
Level 2: 1 -------- 9 --------- 17
Level 1: 1 --- 4 -- 9 --- 12 -- 17
Level 0: 1 2 4 6 9 11 12 15 17

15 검색: 높은 레벨에서 크게 이동하고, 지나치기 직전에 아래로 내려감

실무에서 주의할 점

• 확률적 구조이므로 최악의 경우 O(n)이 가능하지만, 적절한 난수와 확률이면 평균적으로 안정적입니다.
• 포인터가 많아 메모리 오버헤드가 있습니다.
• 동시성 환경에서는 레벨별 포인터 갱신을 안전하게 처리해야 합니다.

실무 적용 가이드

• 정렬된 key-value 저장소, range scan, in-memory index에서 사용됩니다.
• Redis Sorted Set 내부 구현처럼 score 기준 정렬과 빠른 범위 탐색에 적합합니다.
• Balanced tree보다 구현 단순성이 중요한 환경에서 좋은 선택지가 될 수 있습니다.

함께 연결해서 보면 좋은 키워드

Skip List, Sorted Set, Probabilistic, Range Search

정리

Skip List는 정렬된 연결 리스트 위에 여러 단계의 빠른 길을 확률적으로 추가해 평균 O(log n) 탐색을 제공하는 자료구조입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.