요약
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/
'misc' 카테고리의 다른 글
[스크랩][Reference] REST API References (0) | 2024.08.02 |
---|---|
[발표자료] 개발자의 관점에서 바라본 UX 이론 - 220718 매쓰팡 사내 세션 (0) | 2022.08.21 |
[Git] 이전에 작업한 브랜치로 바꾸기:`git checkout -` (0) | 2022.01.10 |
프로그래밍의 본질 - from 개발자의 평생공부 칼럼 (0) | 2021.08.21 |