Redis下位データ構造のジャンプテーブル

18349 ワード
redis
Redis下位データ構造のジャンプテーブル
1.引用
ジャンプテーブルはWilliam Pughによって1990年に発明され、秩序あるデータ構造であり、バランスツリー、赤黒ツリーのようなデータ構造に類似しており、秩序あるリストを維持することができ、検索しやすい.ジャンプテーブルは平均O(logn)の時間複雑度ルックアップをサポートし,これは平衡ツリーにほぼ匹敵するが,なぜRedisの著者らはジャンプテーブルを選択して秩序化集合を実現したのか.以下の点から説明します.
  • 挿入と削除:バランシングツリーの調整操作はいずれもバランシングを引き起こすノードから上へ調整し、一連の左右回転操作でバランシングを達成する必要があるが、ジャンプテーブルは隣接ノードのポインタを変更するだけでよい点は後述の実装説明では
    • に現れる.
  • メモリ占有量:バランスツリーの各ノードはほぼ2つのポインタを占有するが、ジャンプテーブルのポインタ数はグローバルパラメータPに依存し、ポインタ数N=(1-p)/4、RedisはP=1/4を使用するため、平均1.33ポインタ
    • を占有する.
  • 実現難易度:ジャンプテーブルの実現難易度はバランスツリーよりずっと簡単で、検索時間の複雑度はほぼ同等で、いずれもO(logn)
    • である.
    1.一般ジャンプ表の性質
    まず、ジャンプテーブルの直感的な表現を示します.
  • ジャンプテーブルは多くの層からなり、各層は秩序チェーンテーブル
    • である.
  • の最下層にはすべての要素が含まれており、1つの要素が現れるlevel iではlevel iの下のチェーンテーブルにも
    • が表示されます.
  • 各ノードは、同じ層のチェーンテーブルを指す次の要素
    • を指す2つのポインタを含む.
    通常のジャンプテーブル実装コード(注釈付き):
        #include
    #include
    #define MAX_LEVEL 10
    typedef struct skipNode* Node;
    struct skipNode{
        int key;
        int value;
        Node forward[1];
    };
    typedef struct skiplist{
        Node header; 
        int level;
    }skiplist;

    Node createNode(int level,int key,int value){
        //  malloc  level     ，       key value skipNode   
        skipNode * node = (Node) malloc(sizeof(skipNode) + level * sizeof(Node));
        node->key = key;
        node->value = value;
        return node;
    }

    skiplist * createSkiplist(){
        skiplist *list = (skiplist*)malloc(sizeof(skiplist));
        list->level = 0;
        list->header = createNode(MAX_LEVEL,0,0);
        /*
            levelN      forward[N] = NULL
            levelN-1        forward[N-1] = NULL
            levelN-2        forward[N-2] = NULL
                             . 
            level0      forward[0] = NULL
            header------>
        */ 
        for(int i = 0; i < MAX_LEVEL; i++){
            list->header->forward[i] = NULL;
        }
        return list;
    }

    int randomLevel(){  
        int k=1;  
        while (rand()%2)    
            k++;    
        k=(kreturn k;    
    }  

    /*
           
     */
    bool insertElement(skiplist* list , int key , int value){
        //         key      
        skipNode * update[MAX_LEVEL];
        //    key      ，   level    
        int level = list->level;
        skipNode* head = list->header;
        skipNode* next;
        for(int i = level - 1; i >= 0; i--){
            while((next = head->forward[i])&& (next->key < key)){
                head = next;
            }
            update[i] = head;
        }
        // key     
        if(next && next->key == key){
            //       value 
            head->value = value;
            return false;
        }
         //            
        int nlevel = randomLevel();
        if(nlevel > list->level){
            nlevel = ++list->level;  
            update[level] = list->header;  
        }
        //         
        Node newNode = createNode(nlevel,key,value);
        //         
        for(int i = 0 ; i < nlevel ; i++){
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        } 
        return true;
    }

    /*
          key value
    */  
    skipNode* search(skiplist* list,int key)  
    {  
        skipNode *p,*q=NULL;  
        p = list->header;  
        //         
        int k = list->level;  
        for(int i = k-1; i >= 0; i--){  
            while((q = p->forward[i]) && (q->key <= key)) {  
                if(q->key == key){  
                    return q;  
                }  
                p=q;  
            }  
        }  
        return NULL;  
    }

    /**
               
    **/
    bool deleteElement(skiplist* list , int key, int value){
        skipNode* update[MAX_LEVEL];
        skipNode* x = list->header;
        int level = list->level;
        for(int i = level - 1 ; i >= 0 ; i--){
            while(x->forward[i]->key < key){
                x = x->forward[i]; 
            }
            update[i] = x;
        }
        x = x->forward[0];
        if(x->key != key){
            //           
            return false;
        }else{
            for(int i = 0 ; i < list->level ; i++){
                if(update[i]->forward[i] == x){
                    update[i]->forward[i] = x->forward[i];    
                }
            }
            free(x);
            for(int i = list->level-1 ; i >= 0 ; i--){
                if(list->header->forward[i] == NULL){    
                        list->level--;
                    }
            }
        }
        return true; 
    }

    2.Redisにおけるジャンプテーブルの実現
    zskiplistNodeの定義
    typedef struct zskiplistNode {
        robj *obj;
        double score;
        struct zskiplistNode *backward;
        struct zskiplistLevel {
            struct zskiplistNode *forward;
            unsigned int span;
        } level[];
    } zskiplistNode;

    zskiplist定義
    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level;
    } zskiplist;

    図解:
    性質の説明:
  • 複数のノードは同じscoreを含むことができるが、各ノードのメンバーオブジェクトは一意の
    • である必要がある.
  • ジャンプテーブルはscoreのサイズに従って小さいから大きいまで並べ替えられ、スコアが同じである場合、ノードはメンバーオブジェクトのサイズに従って
    • 並べ替えられる.
    具体的な実装コードはT_zset.cファイル中
    まず、作成と初期化の操作です.
    //    
    zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
        zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
        zn->score = score;
        zn->obj = obj;
        return zn;
    }

    zskiplist *zslCreate(void) {
        int j;
        zskiplist *zsl;
        //  zskiplist
        zsl = zmalloc(sizeof(*zsl));
        zsl->level = 1;
        zsl->length = 0;
        //  header  ，ZSKIPLIST_MAXLEVEL=32，       32
        zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
        //    
        for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
            zsl->header->level[j].forward = NULL;
            zsl->header->level[j].span = 0;
        }
        zsl->header->backward = NULL;
        zsl->tail = NULL;
        return zsl;
    }

    挿入関数zslInsertを見てください:
    zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
        //   Update          
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
        //   rank                   
        unsigned int rank[ZSKIPLIST_MAXLEVEL];
        int i, level;

        redisAssert(!isnan(score));
        x = zsl->header;
        //       
        for (i = zsl->level-1; i >= 0; i--) {
            /*                     ，                    */
            rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
            /*   score           ，      ，               
             *              ，              ， update  
             */
            while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    compareStringObjects(x->level[i].forward->obj,obj) < 0))) {
                /** rank            **/
                rank[i] += x->level[i].span;
                x = x->level[i].forward;
            }
            update[i] = x;
        }

        //             
        level = zslRandomLevel();
        //                    ，   header         
        if (level > zsl->level) {
            for (i = zsl->level; i < level; i++) {
                rank[i] = 0;
                update[i] = zsl->header;
                update[i]->level[i].span = zsl->length;
            }
            zsl->level = level;
        }
        //         
        x = zslCreateNode(level,score,obj);
        //             
        for (i = 0; i < level; i++) {
            x->level[i].forward = update[i]->level[i].forward;
            update[i]->level[i].forward = x;

            /*        rank             */
            x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
            update[i]->level[i].span = (rank[0] - rank[i]) + 1;
        }

        /* increment span for untouched levels */
        for (i = level; i < zsl->level; i++) {
            update[i]->level[i].span++;
        }
        //       
        x->backward = (update[0] == zsl->header) ? NULL : update[0];
        if (x->level[0].forward)
            x->level[0].forward->backward = x;
        else
            zsl->tail = x;
        zsl->length++;
        return x;
    }

    関数を削除する
    /* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    //                
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            //     ，
            update[i]->level[i].span += x->level[i].span - 1;
            //   forward  ，
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            update[i]->level[i].span -= 1;
        }
    }
    //   backward  
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }
    //   level    
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;
}

/* Delete an element with matching score/object from the skiplist. */
int zslDelete(zskiplist *zsl, double score, robj *obj) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    //        ，             ，  update    
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                compareStringObjects(x->level[i].forward->obj,obj) < 0)))
            x = x->level[i].forward;
        update[i] = x;
    }
    /* We may have multiple elements with the same score, what we need
     * is to find the element with both the right score and object. */
    x = x->level[0].forward;
    //        x       ，       ，         
    if (x && score == x->score && equalStringObjects(x->obj,obj)) {
        zslDeleteNode(zsl, x, update);
        zslFreeNode(x);
        return 1;
    }
    return 0; /* not found */
}

    基本的な削除と挿入操作に加えて、Redisジャンプテーブルには、指定ノードのテーブル内の順位zslGetRank関数を取得したり、一定の条件を満たす順位を取得したりするなど、多くの操作が提供されています.ここから、Redisジャンプテーブルにスパンフィールドを設定するメリットがあり、迅速に順位を計算できることがわかります.具体的な実現関数はここでは一つ一つ紹介しませんが、興味のある方はソースコードを参照して調べることができます.
    ASP.NET Page実行手順:OnPreInit()、OnInit()
    ASP.NET基本操作