Redis Sorted Set은 왜 Skip List를 선택 했을까?

Skip List스킵리스트는 여러 레벨의 연결 리스트를 확률적으로 구성해 평균 O(log N)에 탐색·삽입·삭제를 지원하는 자료구조 장점스킵 리스트는 다중 레벨로 구성된 연결 리스트 구조를 가지므로, 일반 연결 리스트의 탐색·삽입·삭제가 O(N)인 것에 비해 평균 O(log N)에 수행됩니다.범위 탐색이 효율적이다. O(log N + M)B-트리와 달리, 스킵 리스트는 별도의 리밸런싱 과정 없이 노드 간 포인터만 조작하여 삽입과 삭제가 가능하다.단점각 노드가 여러 레벨의 포인터를 갖기 때문에 연결 리스트에 비해 메모리 사용량이 많다.확률적 구조 특성상 최악의 경우에는 일반 연결 리스트와 동일한 O(N)의 시간 복잡도를 가질 수 있습니다. Redis Sorted Set은 왜 Skip List를 선택 했을까..
내생각 2025. 5. 21. 15:36
1