Redis 데이터 구조 -- skiplist

점프 표 (skiplist) 는 질서정연 한 데이터 구조 로 각 노드 에서 여러 개의 다른 노드 를 가리 키 는 지침 을 유지 함으로써 노드 에 신속하게 접근 하 는 목적 을 달성한다.
점프 표 는 평균 O (logN), 최 악의 O (N) 복잡 도의 노드 를 찾 을 수 있 고 순서 적 인 조작 을 통 해 노드 를 대량으로 처리 할 수 있 습 니 다.  대부분의 경우 점프 표 의 효율 은 밸 런 스 트 리 와 견 줄 수 있 고 점프 표 의 실현 이 밸 런 스 수 보다 간단 하기 때문에 밸 런 스 트 리 대신 점프 표를 사용 하 는 프로그램 이 많다.  redis 는 점프 표를 질서 있 는 집합 키 의 바 텀 실현 중 하나 로 사용 합 니 다. 질서 있 는 집합 에 포 함 된 요소 의 수량 이 많 거나 질서 있 게 집합 하 는 요소 의 구성원 (member) 이 비교적 긴 문자열 일 때 Redis 는 점프 표를 질서 있 는 집합 키 의 바 텀 으로 사용 합 니 다.
 링크, 사전 등 데이터 구조 가 Redis 내부 에 광범 위 하 게 응용 되 는 것 과 달리 Redis 는 두 곳 만 점프 표를 사 용 했 고 하 나 는 질서 있 는 집합 키 를 실현 하 는 것 이 고 다른 하 나 는 클 러 스 터 노드 에서 내부 데이터 구조 로 사용 되 는 것 이다. 그 밖 에 점프 표 는 Redis 에서 다른 용도 가 없다.

/* 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; //header:          ，tail :          
    unsigned long length;  //        ，   ，            (         )
    int level; //        ，            (            )
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

    hearder 와 tail 지침 은 각각 점프 표 의 표 두 와 표 미 노드 를 가리 키 는데 이 두 개의 지침 을 통 해 프로그램 포 지 셔 닝 표 두 노드 와 표 미 노드 의 복잡 도 는 O (1) 이다.
    length 속성 을 사용 하여 노드 의 수량 을 기록 하면 프로그램 은 O (1) 복잡 도 에서 점프 표 의 길 이 를 되 돌려 줄 수 있 습 니 다.
요약:
    점프 표 는 질서 있 게 집합 하 는 밑바닥 실현 중의 하나 이다.
    Redis 의 점프 표 는 zskiplist 와 zskiplist Node 두 가지 구조 로 구성 되 는데 그 중에서 zskiplist 는 점프 표 정보 (예 를 들 어 표 두 노드, 표 꼬리 노드, 길이) 를 저장 하 는 데 사용 되 고 zskiplist Node 는 점프 표 노드 를 표시 하 는 데 사용 된다.
    모든 점프 표 노드 의 층 고 는 1 에서 32 사이 의 임 의 수 이다.
    같은 점프 표 에서 여러 노드 는 같은 점 수 를 포함 할 수 있 지만 각 노드 의 구성원 대상 은 유일 해 야 한다.
   점프 표 의 노드 는 값 크기 에 따라 정렬 하고 값 이 같 을 때 노드 는 구성원 대상 의 크기 에 따라 정렬 합 니 다.