? ? ? ? ?跳躍表(zskiplist)在redis中作為sorted set的底層實現，今天來學習一下。

/* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode {//跳躍表節點sds ele; // 成員對象[必須唯一]double score; // 分值[用來排序][可以相同]struct zskiplistNode *backward; // 后退指針用于從表頭向表尾遍歷struct zskiplistLevel { // 層struct zskiplistNode *forward; // 前進指針unsigned long span;// 跨度} level[]; //數組} zskiplistNode;typedef struct zskiplist { //跳躍表struct zskiplistNode *header, *tail; // 指向表頭節點和表尾節點unsigned long length; // 表中節點的數量int level; // 表中層數最大的節點的層數 } zskiplist;

zskiplist中有頭指針和尾指針，尾指針方便從尾部遍歷。zskiplistNode中有個結構體zskiplistLevel，這個結構體是跳躍表的實現，level是個結構體數組，其中forward指針有用跨度，可以指向非相鄰的結點。span表示forward指向的結點距離本結點多遠。

/* Create a new skiplist. */ zskiplist *zslCreate(void) {//創建并返回一個新的跳躍表int j;zskiplist *zsl;zsl = zmalloc(sizeof(*zsl));//跳躍表zsl->level = 1;zsl->length = 0;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; }

剛開始默認結點最大層級是1，指針賦空。

int zslRandomLevel(void) {//返回一個隨機值，用作新跳躍表節點的層數int level = 1; //0xFFFF 65535 //random()返回一個[0...1)的隨機數while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))//random()&0xFFFF始終小于65535level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }

random是一個偽隨機數，執行多次之后，返回的level也是一個固定的序列，后面會測試一下。

/* Insert a new node in the skiplist. Assumes the element does not already* exist (up to the caller to enforce that). The skiplist takes ownership* of the passed SDS string 'ele'. */ //創建一個成員為 ele ，分值為 score 的新節點,并將這個新節點插入到跳躍表 zsl 中 zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { //mapanzskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;unsigned int rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));x = zsl->header; //取出頭for (i = zsl->level-1; i >= 0; i--) {//在各個層查找節點的插入位置/* store rank that is crossed to reach the insert position */rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];//沿著前進指針遍歷跳躍表//首先比較分值while (x->level[i].forward &&(x->level[i].forward->score < score || (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0) )){rank[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;// 記錄將要和新節點相連接的節點}/* we assume the element is not already inside, since we allow duplicated* scores, reinserting the same element should never happen since the* caller of zslInsert() should test in the hash table if the element is* already inside or not. */level = zslRandomLevel();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,ele);// 將前面記錄的指針指向新節點，并做相應的設置for (i = 0; i < level; i++) { //1x->level[i].forward = update[i]->level[i].forward;// 設置新節點的 forward 指針update[i]->level[i].forward = x;// 將沿途記錄的各個節點的 forward 指針指向新節點/* update span covered by update[i] as x is inserted here */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 */// 未接觸的節點的 span 值也需要增一，這些節點直接從表頭指向新節點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;elsezsl->tail = x;zsl->length++;return x; }

跳躍表的插入函數，我們寫一個程序測試一下：

int t_zsetTest() //mapan {zskiplist *p = zslCreate();zslInsert(p,1.1,"a");zslInsert(p,3.3,"b");zslInsert(p,2.2,"c");zslInsert(p,4.4,"d");zslInsert(p,0.9,"e");zslInsert(p,3.8,"f");zslInsert(p,5.5,"g");printf("----------------\n");zslInsert(p,1.3,"h");return 0; }

先看一下，執行對應插入操作所獲取的層級：

mapan@mapan-virtual-machine:~/redis-5.0.5/src$ ./redis-server level=1,score=1.100000 level=2,score=3.300000 level=1,score=2.200000 level=1,score=4.400000 level=1,score=0.900000 level=1,score=3.800000 level=1,score=5.500000 ---------------- level=2,score=1.300000 mapan@mapan-virtual-machine:~/redis-5.0.5/src$ ./redis-server level=1,score=1.100000 level=2,score=3.300000 level=1,score=2.200000 level=1,score=4.400000 level=1,score=0.900000 level=1,score=3.800000 level=1,score=5.500000 ---------------- level=2,score=1.300000

你每次運行所對應的層級是一個固定的序列。3.3和1.3對應的層級是2，其他都是1。當執行到zslInsert(p,5.5,"g")時，我們看一下跳躍表的結構。

最下面一層對應都是L1。這時候在執行zslInsert(p,1.3,"h");操作，就會先遍歷L2對應的那層，在遍歷L1對應的那層。

/* Delete an element with matching score/element from the skiplist.* The function returns 1 if the node was found and deleted, otherwise* 0 is returned.** If 'node' is NULL the deleted node is freed by zslFreeNode(), otherwise* it is not freed (but just unlinked) and *node is set to the node pointer,* so that it is possible for the caller to reuse the node (including the* referenced SDS string at node->ele). *///從跳躍表 zsl 中刪除包含給定節點 score 并且帶有指定對象 ele 的節點 int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;int i;x = zsl->header;for (i = zsl->level-1; i >= 0; i--) { //逐層遍歷,遍歷完后要么x指向對應節點，要么找不到while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&sdscmp(x->level[i].forward->ele,ele) < 0))){x = x->level[i].forward;}update[i] = x;// 記錄沿途節點printf("score=%lf,i=%d\n",update[i]->score,i);}/* 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;if (x && score == x->score && sdscmp(x->ele,ele) == 0) {printf("x->score=%lf\n",x->score);zslDeleteNode(zsl, x, update);if (!node)zslFreeNode(x);else*node = x; //node用來保存結點，用于重復使用return 1;}return 0; /* not found */ }

刪除結點首先也要遍歷結點。

/* Update the score of an elmenent inside the sorted set skiplist.* Note that the element must exist and must match 'score'.* This function does not update the score in the hash table side, the* caller should take care of it.** Note that this function attempts to just update the node, in case after* the score update, the node would be exactly at the same position.* Otherwise the skiplist is modified by removing and re-adding a new* element, which is more costly.** The function returns the updated element skiplist node pointer. *///更新排序后的跳躍表中元素的score。 zskiplistNode *zslUpdateScore(zskiplist *zsl, double curscore, sds ele, double newscore) {zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;int i;/* We need to seek to element to update to start: this is useful anyway,* we'll have to update or remove it. */x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {while (x->level[i].forward &&(x->level[i].forward->score < curscore ||(x->level[i].forward->score == curscore &&sdscmp(x->level[i].forward->ele,ele) < 0))){x = x->level[i].forward;}update[i] = x;}/* Jump to our element: note that this function assumes that the* element with the matching score exists. */x = x->level[0].forward;serverAssert(x && curscore == x->score && sdscmp(x->ele,ele) == 0); //確保找到對應的結點printf("assert\n");/* If the node, after the score update, would be still exactly* at the same position, we can just update the score without* actually removing and re-inserting the element in the skiplist. */if ((x->backward == NULL || x->backward->score < newscore) &&(x->level[0].forward == NULL || x->level[0].forward->score > newscore)) //newscore修正后，要注意集合的順序{x->score = newscore;return x;}/* No way to reuse the old node: we need to remove and insert a new* one at a different place. */zslDeleteNode(zsl, x, update); zskiplistNode *newnode = zslInsert(zsl,newscore,x->ele);/* We reused the old node x->ele SDS string, free the node now* since zslInsert created a new one. */x->ele = NULL;zslFreeNode(x);return newnode; }

更新跳躍表中的元素時，要保證更新后還是有序的，這就可能需要刪除原來的階段，重新插入新的結點。

總結

以上是生活随笔為你收集整理的redis之zskiplist的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。