Skip List: 확률적 O(log N) 정렬 구조
Skip List, 스킵 리스트
정의
Skip List 는 정렬된 연결 리스트를 여러 층으로 쌓아 확률적으로 O(log N) 탐색을 제공합니다.
각 노드는 확률 1/2 로 더 높은 층에 승격됩니다. 상위 층은 아래 층의 축소판 인덱스 역할.
특징
- 삽입/삭제/탐색: 기댓값 O(log N), 최악 O(N)
- 균형 트리 (AVL, Red-Black) 대비 구현 훨씬 단순
- 락 없는 (lock-free) 동시성 구현 쉬움
- Redis Sorted Set 내부 구조 (ziplist 임계값 초과 시)
참고
이 글의 용어 (3개)
- [Redis] Sorted Set: Skiplist + Dict, 리더보드, 우선순위 큐database-internals
- 정의 Redis Sorted Set (ZSet) 은 멤버 + 점수 (score) 의 순서 보존 unique 집합. score 기준 정렬 + 멤버 기준 O(1) 조회 가 동시에 가…
- BBST (Splay Tree, Treap)algorithm
- 정의 BBST (Balanced Binary Search Tree) 는 균형이 amortized / expected 로 보장되는 이진 탐색 트리. PS 에서는 split / me…
- Binary Search Tree (BST): 정렬된 이진 트리algorithm
- 정의 Binary Search Tree (BST) 는 각 노드가 다음을 만족하는 이진 트리입니다. - 왼쪽 서브트리의 모든 키 < 노드 키 - 오른쪽 서브트리의 모든 키 > 노드…
💬 댓글