REDIS 정렬 된 집합을 사용하여 특정 시간 연산의 복잡도는 얼마입니까?

Question

REDIS 설명서에서 정렬 된 집합에 대한 삽입 및 업데이트 작업이 O (log (n))임을 나타냅니다.

이 부분은 question이며 기본 데이터 구조에 대한 자세한 내용은 skip list입니다.

그러나 익숙하지 않은 REDIS 구현에 의존하는 몇 가지 특별한 경우가 있습니다.

• 정렬 된 세트의 머리 또는 꼬리에 추가하는 것은 아마 O (로그 (N)) 작업,하지만 O (1), right?이 질문은 예약에 동의하는 것 같다되지 않습니다.
• 주문이 변경되지 않더라도 회원 점수를 업데이트하는 것은 여전히 ​​O (log (n))입니다. 요소를 가져 와서 약간 다른 점수로 다시 삽입하거나, 순서는 변경되지 않으므로 차이점은 삽입 또는 업데이트 점수 사이의 상수 연산에만 있습니다. 권리? 나는이 경우에 내가 틀렸다고 정말로 희망한다.

모든 통찰력을 환영합니다.

Answer 1

참고 : 목록이 특정 크기 (max_ziplist_entries) 이상으로 커지면 건너 뛰기 목록이 사용되며, 그 아래에는 우편 번호 목록이 사용됩니다.

Re. 첫 번째 질문 - 건너 뛰기 목록이 이진 트리의 한 유형이므로 머리글/꼬리 노드가

Re라는 보장이 없으므로 여전히 O (log (n))라고 생각합니다. - 두번째 질문 소스에 따라 점수를 변경 제거 및 회원 재 부가로 구현됩니다 위키 피 디아에서 스킵리스트 항목에서 https://github.com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1233 & https://github.com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1272