Redis 질서 있 는 집합 유형의 조작동력 노드 자바 대학 정리

오늘 레 디 스 의 마지막 데이터 유형 인'질서 있 는 집합 유형'을 말씀 드 리 겠 습 니 다.전에 배 운 몇 가지 데이터 구 조 를 돌 이 켜 보면 감탄 할 지 모 르 겠 습 니 다.오픈 소스 의 세계 가 정말 좋 습 니 다.이런 코드 를 쓰 는 친절 한 사람 은 정말 평생 평안 해 야 합 니 다.우리 가 생각 하지 못 했 던 것 이 이 세상 에 이미 존재 합 니 다.언젠가.우 리 는 모든 데 이 터 를 데이터 구조 모델 로 구성 한 후에 메모리 에 주입 하고 싶 습 니 다.그러나 메모리 공유 방식 에 이 르 기 위해 서 는 이 메모리 를 따로 배치 해 야 합 니 다.또한 어떻게 직렬 화 하 는 지,언제 서열 이 서로 다른 지 를 고려 해 야 합 니 다.번 거 로 운 일이 너무 많 습 니 다.나중에 야 redis 라 는 것 을 알 게 되 었 습 니 다.고급,저급한 데이터 구 조 를 공유 메모리(Redis)에 따로 포장 할 수 있 습 니 다.고급 데이터 구 조 는 바로 본 편 에서 말 한'질서 있 는 집합'입 니 다.       
1:질서 있 는 집합(SortedSet)
Sorted Set 집합 을 처음 접 한 사람들 은 이 집합 을 사용 하 는 장면 은 어떤 것들 이 있 습 니까?라 고 말 할 수 있 습 니 다."범위 찾기"의 천적 은"질서 있 는 집합"이 라 고 명확 하 게 말 할 수 있 습 니 다.모든 빅 데 이 터 를 통 해 한 범 위 를 찾 는 시간 복잡 도 는 영원히 O[(LogN)+M]입 니 다.그 중에서 M:돌아 오 는 요소 갯 수 입 니 다.
　　 쉬 운 것 부터 어 려 운 것 까지,우 리 는 먼저 redis 수첩 을 보고,우리 가 자주 사용 하 는 몇 가지 방법 을 골 라 서 참관 효 과 를 관찰 하 는 것 이 좋 겠 다. 　
　　　
위의 17 개 명령 중에서 자주 사용 하 는 명령 은 ZADD,ZREM,ZRANGEBYSCORE,ZRANGE 이다. 
1. ZADD

ZADD key score member [[score member] [score member] ...]

하나 이상 의 member 요소 와 score 값 을 질서 있 는 집합 key 에 추가 합 니 다.
이것 은 공식 적 인 해석 입 니 다.할당 방식 과 hashtable 의 차이 가 많 지 않 습 니 다.다만 이곳 의 key 는 질서 가 있 을 뿐 입 니 다.다음은 제 가 예 를 들 겠 습 니 다.저 는 fruits 집합 이 있 는데 그 중에서 모든 과일의 price 를 기록 한 다음 에 price 의 각종 조작 에 따라 해당 하 는 과일 정 보 를 얻 었 습 니 다.

위의 기본 정보 가 있 습 니 다.그 다음 에 저 는 그들 을 Sorted Set 에 보 내 드 리 겠 습 니 다.다음 그림 은 다음 과 같 습 니 다.

위의 그림 에서 당신 은 어떤 이상 을 발 견 했 는 지 모 르 겠 습 니 다.?적어도 두 가지 가 있다.
<1>부동 소수점 유사 치 문제,예 를 들 어 grape,내 가 add 에 적 었 을 때 2.8 이 라 고 썼 는데 redis 에서 나 에 게 유사 치 2.79999 를 보 여 주 었 다........................................................
<2>  기본적으로 SortedSet 은 key 의 오름차 순 정렬 방식 으로 저 장 됩 니 다. 
2.  ZRANGE，ZREVRANGE

ZRANGE key start stop [WITHSCORES]

질서 있 는 집합 키 에서 지정 한 구간 의 구성원 을 되 돌려 줍 니 다.
그 중 구성원 의 위 치 는 score 값 이 증가(어 릴 때 부터)에 따라 정렬 된다.
  위 는 바로 ZRange 의 형식 모델 입 니 다.앞에서 제 가 ZAdd 를 말 할 때 사실은 저도 말 했 습 니 다.그런데 이것 은 중요 한 것 이 아 닙 니 다.ZRange 를 말 할 때 문 제 를 남 겼 습 니 다.바로 ZRange 기본 값 은 key 오름차 순 으로 정렬 된 것 입 니 다.그 렇 죠?그럼 거꾸로 표시 하고 싶 으 면 어떻게 하 시 겠 습 니까?사실 ZRange 의 미 러 법 ZREVRANG 을 사용 할 수 있어 요. 바로 다음 그림 입 니 다. 

3. ZRANGEBYSCORE

ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]

질서 있 는 집합 키 를 되 돌려 줍 니 다.모든 score 값 은 min 과 max 사이(min 또는 max 포함)에 있 는 구성원 입 니 다.질서 있 는 집합 구성원 은 score 값 증가(작은 것 부터 큰 것 까지)순서에 따라 배열 합 니 다.
 이것 은 Sorted Set 에 있어 서 가장 중요 한 방법 이 라 고 할 수 있 습 니 다.글 의 처음에 저도 말 했 습 니 다.질서 있 게 집합 하 는 것 이 범위 찾기 에 가장 유리 합 니 다.찾 는 것 이 니 조건 이 있어 야 합 니 다.그 렇 죠?다음은 제 가 예 를 들 겠 습 니 다. 
  <1>  나 는 1-4 원 짜 리 과일 종 류 를 찾 아야 한다.당연 하 다.나 는[포도,사과]를 찾 을 것 이다.다음 과 같은 그림 이다.

 127.0.0.1:6379> zrangebyscore fruits 1 4 withscores
 1) "grape"
 2) "2.7999999999999998"
 3) "apple"
 4) "3.5"
 127.0.0.1:6379> 

  <2>  1-4 구간 중 4 조각 에 가장 가 까 운 과일 은 무엇 입 니까?이 문 제 는 애플 이라는 옵션 을 찾 는 것 입 니 다.그럼 찾 으 면 요??생각해 보면 내 가 이렇게 할 수 있 는데,
　  　   1-4 구간 의 모든 수 를 거꾸로 첫 번 째 데 이 터 를 취하 면 됩 니 다.그 렇 죠?다음 그림:

127.0.0.1:6379> zrevrangebyscore fruits 4 1 withscores
1) "apple"
2) "3.5"
3) "grape"
4) "2.7999999999999998"
127.0.0.1:6379> zrevrangebyscore fruits 4 1 withscores limit 0 1
1) "apple"
2) "3.5"
127.0.0.1:6379>

4. ZREM

ZREM key member [member ...]

질서 있 는 집합 키 의 하나 이상 의 구성원 을 제거 하면 존재 하지 않 는 구성원 은 무 시 됩 니 다.
키 가 존재 하지만 질서정연 한 집합 형식 이 아 닐 때 오 류 를 되 돌려 줍 니 다.
다른 방법 과 마찬가지 로 zrem 의 목적 은 지정 한 value 구성원 을 삭제 하 는 것 입 니 다.예 를 들 어 여기 서 scores=3.5 의 애플 기록 을 삭제 하 겠 습 니 다.

127.0.0.1:6379> zrem fruits apple
(integer) 1
127.0.0.1:6379> zrange fruits 0 -1 withscores
1) "grape"
2) "2.7999999999999998"
3) "pear"
4) "4.0999999999999996"
5) "banana"
6) "5"
7) "nut"
8) "9.1999999999999993"
127.0.0.1:6379>

너 는 이미 애플 의 관련 기록 이 없다 는 것 을 알 게 될 것 이다.왜냐하면 이미 내 가 삭 제 했 기 때문이다. 
2.탐색 원리
간단 한 조작 은 이미 시연 이 끝 났 습 니 다.그 다음 에 sortedset 이 어떤 데이터 구조 로 지탱 되 는 지 연구 해 보 겠 습 니 다.여러분 은 이미 들 었 을 것 입 니 다.sortedset 은 CURD 의 노점 분석 에 있어 모두 Log(N)의 복잡 도 이 고 균형 이 잡 힌 이 진 트 리 와 견 줄 수 있 습 니 다.이것 이 바로 1987 년 에 나 온 신형 효율 적 인 데이터 구조 인'도약 표(SkipList)'입 니 다.SkipList 소의 부분 은 나무 모형 의 사고 에서 벗 어 나 다 층 링크 의 모델 로 Log(N)의 시간 복잡 도,층 의 높이 증가 여부,임 의 수의 모델 을 구 축 했 는데 이것 은'Treap 나무'의 사상 과 마찬가지 로'나무'또는'링크'의 균형 을 유지 했다.
     자세 한 건 말씀 드 리 지 않 겠 습 니 다.그렇지 않 으 면 또 하나의 글 입 니 다.굳이 알 고 싶다 면 바 이 두 백 과 를 참고 하 세 요.저 는 백과 에 그 려 진 이 그림 을 대충 봤 습 니 다.아래 와 같이:

이 그림 에는 세 개의 체인 이 있 는데 SkipList 에 서 는 모든 체인 의 데 이 터 를 질서 있 게 해 야 합 니 다.이것 은 필수 입 니 다. 
1.level 1 층 에서 노드 6 을 찾 으 려 면 한 번 씩 옮 겨 다 녀 야 6 번 찾 아야 데 이 터 를 정확하게 찾 을 수 있 습 니 다.
2.level 2 층 에서 노드 6 을 찾 으 면 4 번 이 걸 려 야 찾 을 수 있 습 니 다.
3.level 3 층 에서 노드 6 을 찾 으 면 세 번 이면 찾 을 수 있 습 니 다... 
현재 거시적인 이해 에 있어 서 level 의 층수 가 높 을 수록 데 이 터 를 찾 는 횟수 가 적 다 는 느낌 이 들 지 않 습 니까?이것 이 바로 점프 표 의 사상 입 니 다.그렇지 않 으 면 어떻게 뛰 는 지 보 겠 습 니 다.그 다음 에 redis 에서 이 skiplist 를 어떻게 정의 하 는 지 보 겠 습 니 다.그의 소스 코드 는 redis.h 에 있 습 니 다.

/* ZSETs use a specialized version of Skiplists */
 typedef struct zskiplistNode {
  robj *obj;
  double score;
  struct zskiplistNode *backward;
  struct zskiplistLevel {
   struct zskiplistNode *forward;
   unsigned int span;
  } level[];
 } zskiplistNode;
 typedef struct zskiplist {
  struct zskiplistNode *header, *tail;
  unsigned long length;
  int level;
 } zskiplist;

원본 코드 에서 다음 과 같은 몇 가 지 를 볼 수 있다.
<1>   zskiplist node 는 skiplist 의 node 노드 입 니 다.노드 에 level[]배열 이 있 습 니 다.똑똑 하 다 면 이 level[]은 위의 그림 에 저 장 된 것 임 을 알 아야 합 니 다.
         의 level 1,level 2,level 3 세 개의 체인. 
<2>   level[]안 에는 zskiplist Level 실체 가 있 습 니 다.이 실체 에는*forward 포인터 가 있 습 니 다.이 지침 은 같은 층 의 후속 노드 를 가리 키 는 것 입 니 다. 
<3>   zskiplist Level 에 하나 더 있어 요. robj 형식의*obj 포인터,이것 이 바로 RedisObject 대상 입 니 다.안에 저 장 된 것 이 바로 우리 의 value 값 입 니 다.그 다음 에 하나 더 있 습 니 다. score 속성,이게 키 값 이 야...skiplist 는 그것 에 따라 정렬 된 것 입 니 다. 
<4>  다음은 두 번 째 매 거 진 zskiplist 입 니 다.이것 은 재미 가 없습니다.순수한 포장 층 입 니 다.예 를 들 어 안의 length 는 skiplist 중의 노드 개 수 를 기록 하고 level 은 skiplist 를 기록 합 니 다. 현재 층수,*header,*tail 로 skiplist 의 첫 번 째 노드 와 끝 노드 를 기록 합 니 다.그 뿐 이 야...