[Redis] Sorted Set의 자료구조 - Skip list & Hash table

요약

Skip list와 Hash table이 포함된 dual ported 자료구조

시간 복잡도

Skip List를 써서 ZRANGE의 시간 복잡도는 O(log(n) + m) 이다. 시작하는 값을 log(n) 시간에 찾고, 찾는 노드 개수 m만큼 추가로 탐색하기 때문이다.

대대수 연산의 시간 복잡도는 log(n)이다. Skip List이기 때문으로 추정된다

Hash table은 왜 쓰는가?

The hash table provides fast access to elements based on their value, while the skip list maintains the sorted order of the elements based on their scores.

hash table은 value로 요소 접근, skip list는 score로 정렬된 요소를 접근하기 위해서 사용한다.
value로 요소를 접근하는 예로는 ZSCORE가 있다. ZSCORE는 멤버 이름을 입력하면 score를 반환하는데, 이를 구현하기 위해서 value => score 형태의 Hash table을 사용할 것 같다.

참고 자료

https://redis.io/docs/latest/develop/data-types/sorted-sets/

https://redis.io/glossary/redis-sorted-sets/

https://www.geeksforgeeks.org/skip-list/

https://en.wikipedia.org/wiki/Skip_list