跳躍表的定義
跳躍表是一種有序資料結構,它通過在每個結點中維持多個指向其他結點的指針,進而達到快速通路其他結點的目的
跳躍表的結構
關于跳躍表的學習請參考:https://www.jianshu.com/p/ac351674d8eb?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation
跳躍表操作的時間空間複雜度分析
1.跳躍表的結點插入
1)新結點從上到下與各層索引結點逐一比較,确定在原連結清單的插入位置:【O(log N)】
2)确定在原連結清單的插入位置後直接插入:【O(1)】
3)利用随機的方式決定新結點上升為幾層索引結點:【O(log N)】
總體來說,跳躍表的插入操作的時間複雜度是O(log N)
2.跳躍表結點的查詢
1)從上到下與索引結點進行比較,逐漸縮小需要查詢的結點所在的範圍(因為跳躍表是有序的資料結構,類似于二分的思想)【平均:O(log N),最壞為O(N)】
總體來說,跳躍表的查詢操作的時間複雜度為O(log N)
3.跳躍表結點的删除
1)自上而下,查找第一次出現結點的索引,并逐層找到每一層對應的結點:【O(log N)】
2)删除每一層查到的結點,如果該層隻剩一個結點,删除整個一層(原連結清單除外)【O(log N)】
總的來說,跳躍表的删除操作的時間複雜度是O(log N)
4.跳躍表的空間複雜度
對于每層的期待:第一層n,第二層n/2,第三層n/22,...,直到 n/2log n=1。
是以,總空間需求:S = n + n/2 + n/22 + ... + n/2log n < n(1 + 1/2 + 1/22 + ... + 1/2∞) =2n
是以他的空間複雜度為 2n = O(n)
總的來說,跳躍表的空間複雜度為O(N)
5.跳躍表的高度
對每層來說,它會向上增長的機率為1/2,則第m層向上增長的機率為1/2m;
n個元素,則在m層元素數目的期待為Em = n/2m;
當Em = 1,m = log2n即為層數的期待。
故其高度期待為 Eh = O(log n)。
其他知識
1.大多數情況下,跳躍表的效率的平衡樹不相上下, 并且跳躍表的實作更加簡單
2.Redis使用跳躍表作為有序集合鍵的底層實作之一,如果一個有序集合包含的元素數量多,又或者有序集合中元素的成員是比較長的字元串時,Redis就會采用跳躍表來作為有序集合鍵的底層實作
3.Redis隻在兩個地方使用了跳躍表:有序集合鍵和叢集結點中用作内部資料結構
4.跳躍表結點的後退指針隻能後退到原連結清單的前一個結點,每次隻能後推一個結點
5.跳躍表結點按照分值升序排序
6.在同一個跳躍表中,各個結點儲存的成員對象必須是唯一的,但是多個結點儲存的分值可以相同
7.通過跳躍表屬性的記錄,跳躍表可以在O(1)擷取頭尾結點,表長度和層數
8.每個跳躍表結點的層高都是1-32的随機數
9.跳躍表的真正源碼在redis的redis.h檔案和t_zset.c檔案下
源碼分析如下:
zskiplist.h檔案:
#ifndef ZSKIPLIST_H
#define ZSKIPLIST_H
//the last time an object was accessed
#define REDIS_LRU_BITS 24
//zskiplist max level,Should be enough for 2^32 elements
#define ZSKIPLIST_MAXLEVEL 32
//Skiplist P = 1/4
#define ZSKIPLIST_P 0.25
//=====資料結構========//
/*
* Redis 對象
*/
typedef struct redisObject
{
// 類型
unsigned type:4;
// 編碼
unsigned encoding:4;
// 對象最後一次被通路的時間
unsigned lru:
REDIS_LRU_BITS; /* lru time ( ) */
// 引用計數
int refcount;
// 指向實際值的指針
void *ptr;
} robj;
/*
* 跳躍表節點
*/
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;
// 表示開區間/閉區間範圍的結構
typedef struct
{
// 最小值和最大值
double min, max;
// 訓示最小值和最大值是否*不*包含在範圍之内
// 值為 1 表示不包含,值為 0 表示包含
int minex, maxex; /* are min or max exclusive? */
} zrangespec;
//=========== API定義 ===============//
//建立一個新的跳躍表
zskiplist *zslCreate(void);
//釋放給定跳躍表,以及表中所有的結點
void zslFree(zskiplist *zsl);
//将包含給定成員和分值的新結點添加到跳躍表中
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj);
//删除跳躍表中包含給定成員和分值的結點
int zslDelete(zskiplist *zsl, double score, robj *obj);
//傳回包含給定成員和分值的結點在跳躍表中的排位
unsigned long zslGetRank(zskiplist *zsl, double score, robj *o);
//傳回跳躍表在給定排位上的結點
zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank);
//給定一個分值範圍,判斷該分值範圍是否包含在跳躍表的分值範圍内
int zslIsInRange(zskiplist *zsl, zrangespec *range);
//給定一個分值範圍,傳回跳躍表中第一個符合這個範圍的結點
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
//給定一個分值範圍,傳回跳躍表中最後一個符合這個範圍的結點
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);
//給定一個分值範圍,删除跳躍表中所有在這個範圍内的結點
unsigned long zslDeleteRangeByScore(zskiplist *zsl, zrangespec *range);
//給定一個排位範圍,删除跳躍表中所有在這個範圍内的結點
unsigned long zslDeleteRangeByRank(zskiplist *zsl, unsigned int start, unsigned int end);
#endif // ZSKIPLIST_H
zskiplist.c檔案:
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#include "zskiplist.h"
/*
* 建立一個層數為 level 的跳躍表節點,
* 并将節點的成員對象設定為 obj ,分值設定為 score 。
*
* 傳回值為新建立的跳躍表節點
*
* T = O(1)
*/
zskiplistNode *zslCreateNode(int level, double score, robj *obj)
{
// 配置設定空間
//在這裡我沒有使用redis提供的記憶體配置設定函數zmalloc,而是使用c提供的malloc
//zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zskiplistNode *zn = malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
// 設定屬性
zn->score = score;
zn->obj = obj;
return zn;
}
/*
* 建立并傳回一個新的跳躍表
*
* T = O(1)
*/
zskiplist *zslCreate(void)
{
int j;
zskiplist *zsl;
// 配置設定空間
//zsl = zmalloc(sizeof(*zsl));
zsl = malloc(sizeof(*zsl));
// 設定高度和起始層數
zsl->level = 1;
zsl->length = 0;
// 初始化表頭節點
// T = O(1)
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;
}
/*
* 釋放給定的跳躍表節點
*
* T = O(1)
*/
void zslFreeNode(zskiplistNode *node)
{
//對象引用計數-1
//在這裡我将引用計數去掉了,因為隻是為了示範zskiplist,沒有必要,而且加上這個還要引入其他頭檔案才能跑
//decrRefCount(node->obj);
//zfree(node);
//同樣,這裡采用的是c提供的函數,沒有使用redis提供的記憶體函數zfree
free(node);
}
/*
* 釋放給定跳躍表,以及表中的所有節點
*
* T = O(N)
*/
void zslFree(zskiplist *zsl)
{
zskiplistNode *node = zsl->header->level[0].forward, *next;
// 釋放表頭
//zfree(zsl->header);
free(zsl->header);
// 釋放表中所有節點
// T = O(N)
while(node)
{
next = node->level[0].forward;
zslFreeNode(node);
node = next;
}
// 釋放跳躍表結構
//zfree(zsl);
free(zsl);
}
/*
* 傳回一個随機值,用作新跳躍表節點的層數。
*
* 傳回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之間(包含 ZSKIPLIST_MAXLEVEL),
* 根據随機算法所使用的幂次定律,越大的值生成的幾率越小。
*
* T = O(N)
*/
int zslRandomLevel(void)
{
int level = 1;
while ((rand()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
/*
* 建立一個成員為 obj ,分值為 score 的新節點,
* 并将這個新節點插入到跳躍表 zsl 中。
*
* 函數的傳回值為新節點。
*
* T_wrost = O(N), T_avg = O(log N)
*/
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj)
{
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
//redisAssert(!isnan(score));
// 在各個層查找節點的插入位置
// T_wrost = O(N), T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
/* store rank that is crossed to reach the insert position */
// 如果 i 不是 zsl->level-1 層
// 那麼 i 層的起始 rank 值為 i+1 層的 rank 值
// 各個層的 rank 值一層層累積
// 最終 rank[0] 的值加一就是新節點的前置節點的排位
// rank[0] 會在後面成為計算 span 值和 rank 值的基礎
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
// 沿着前進指針周遊跳躍表
// T_wrost = O(N), T_avg = O(log N)
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
// 比對分值
(x->level[i].forward->score == score &&
// 比對成員, T = O(N)
1/* compareStringObjects(x->level[i].forward->obj,obj) < 0*/)))
{
// 記錄沿途跨越了多少個節點
rank[i] += x->level[i].span;
// 移動至下一指針
x = x->level[i].forward;
}
// 記錄将要和新節點相連接配接的節點
update[i] = x;
}
/*
* zslInsert() 的調用者會確定同分值且同成員的元素不會出現,
* 是以這裡不需要進一步進行檢查,可以直接建立新元素。
*/
// 擷取一個随機值作為新節點的層數
level = zslRandomLevel();
// 如果新節點的層數比表中其他節點的層數都要大
// 那麼初始化表頭節點中未使用的層,并将它們記錄到 update 數組中
// 将來也指向新節點
if (level > zsl->level)
{
// 初始化未使用層
// T = O(1)
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);
// 将前面記錄的指針指向新節點,并做相應的設定
// T = O(1)
for (i = 0; i < level; i++)
{
// 設定新節點的 forward 指針
x->level[i].forward = update[i]->level[i].forward;
// 将沿途記錄的各個節點的 forward 指針指向新節點
update[i]->level[i].forward = x;
/* update span covered by update[i] as x is inserted here */
// 計算新節點跨越的節點數量
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
// 更新新節點插入之後,沿途節點的 span 值
// 其中的 +1 計算的是新節點
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* increment span for untouched levels */
// 未接觸的節點的 span 值也需要增一,這些節點直接從表頭指向新節點
// T = O(1)
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;
}
/*
* 内部删除函數,
* 被 zslDelete 、 zslDeleteRangeByScore 和 zslDeleteByRank 等函數調用。
*
* T = O(1)
*/
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update)
{
int i;
// 更新所有和被删除節點 x 有關的節點的指針,解除它們之間的關系
// T = O(1)
for (i = 0; i < zsl->level; i++)
{
if (update[i]->level[i].forward == x)
{
update[i]->level[i].span += x->level[i].span - 1;
update[i]->level[i].forward = x->level[i].forward;
}
else
{
update[i]->level[i].span -= 1;
}
}
// 更新被删除節點 x 的前進和後退指針
if (x->level[0].forward)
{
x->level[0].forward->backward = x->backward;
}
else
{
zsl->tail = x->backward;
}
// 更新跳躍表最大層數(隻在被删除節點是跳躍表中最高的節點時才執行)
// T = O(1)
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
// 跳躍表節點計數器減一
zsl->length--;
}
/*
* 從跳躍表 zsl 中删除包含給定節點 score 并且帶有指定對象 obj 的節點。
*
* T_wrost = O(N^2), T_avg = O(N log N)
*/
int zslDelete(zskiplist *zsl, double score, robj *obj)
{
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
// 周遊跳躍表,查找目标節點,并記錄所有沿途節點
// T_wrost = O(N), T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
// 周遊跳躍表的複雜度為 T_wrost = O(N), T_avg = O(log N)
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
// 比對分值
(x->level[i].forward->score == score &&
// 比對對象,T = O(N)
1/*compareStringObjects(x->level[i].forward->obj,obj) < 0*/)))
// 沿着前進指針移動
x = x->level[i].forward;
// 記錄沿途節點
update[i] = x;
}
/*
* 檢查找到的元素 x ,隻有在它的分值和對象都相同時,才将它删除。
*/
x = x->level[0].forward;
if (x && score == x->score && 1/*equalStringObjects(x->obj,obj)*/)
{
// T = O(1)
zslDeleteNode(zsl, x, update);
// T = O(1)
zslFreeNode(x);
return 1;
}
else
{
return 0; /* not found */
}
return 0; /* not found */
}
/*
* 查找包含給定分值和成員對象的節點在跳躍表中的排位。
*
* 如果沒有包含給定分值和成員對象的節點,傳回 0 ,否則傳回排位。
*
* 注意,因為跳躍表的表頭也被計算在内,是以傳回的排位以 1 為起始值。
*
* T_wrost = O(N), T_avg = O(log N)
*/
unsigned long zslGetRank(zskiplist *zsl, double score, robj *o)
{
zskiplistNode *x;
unsigned long rank = 0;
int i;
// 周遊整個跳躍表
x = zsl->header;
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 &&
// 比對成員對象
1/*compareStringObjects(x->level[i].forward->obj,o) <= 0*/)))
{
// 累積跨越的節點數量
rank += x->level[i].span;
// 沿着前進指針周遊跳躍表
x = x->level[i].forward;
}
/* x might be equal to zsl->header, so test if obj is non-NULL */
// 必須確定不僅分值相等,而且成員對象也要相等
// T = O(N)
if (x->obj && 1/*equalStringObjects(x->obj,o)*/)
{
return rank;
}
}
// 沒找到
return 0;
}
/*
* 根據排位在跳躍表中查找元素。排位的起始值為 1 。
*
* 成功查找傳回相應的跳躍表節點,沒找到則傳回 NULL 。
*
* T_wrost = O(N), T_avg = O(log N)
*/
zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank)
{
zskiplistNode *x;
unsigned long traversed = 0;
int i;
// T_wrost = O(N), T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
// 周遊跳躍表并累積越過的節點數量
while (x->level[i].forward && (traversed + x->level[i].span) <= rank)
{
traversed += x->level[i].span;
x = x->level[i].forward;
}
// 如果越過的節點數量已經等于 rank
// 那麼說明已經到達要找的節點
if (traversed == rank)
{
return x;
}
}
// 沒找到目标節點
return NULL;
}
/*
* 檢測給定值 value 是否大于(或大于等于)範圍 spec 中的 min 項。
*
* 傳回 1 表示 value 大于等于 min 項,否則傳回 0 。
*
* T = O(1)
*/
static int zslValueGteMin(double value, zrangespec *spec)
{
return spec->minex ? (value > spec->min) : (value >= spec->min);
}
/*
* 檢測給定值 value 是否小于(或小于等于)範圍 spec 中的 max 項。
*
* 傳回 1 表示 value 小于等于 max 項,否則傳回 0 。
*
* T = O(1)
*/
static int zslValueLteMax(double value, zrangespec *spec)
{
return spec->maxex ? (value < spec->max) : (value <= spec->max);
}
/* Returns if there is a part of the zset is in range.
*
* 如果給定的分值範圍包含在跳躍表的分值範圍之内,
* 那麼傳回 1 ,否則傳回 0 。
*
* T = O(1)
*/
int zslIsInRange(zskiplist *zsl, zrangespec *range)
{
zskiplistNode *x;
// 先排除總為空的範圍值
if (range->min > range->max ||
(range->min == range->max && (range->minex || range->maxex)))
return 0;
// 檢查最大分值
x = zsl->tail;
if (x == NULL || !zslValueGteMin(x->score,range))
return 0;
// 檢查最小分值
x = zsl->header->level[0].forward;
if (x == NULL || !zslValueLteMax(x->score,range))
return 0;
return 1;
}
/*
* 傳回 zsl 中第一個分值符合 range 中指定範圍的節點。
* Returns NULL when no element is contained in the range.
*
* 如果 zsl 中沒有符合範圍的節點,傳回 NULL 。
*
* T_wrost = O(N), T_avg = O(log N)
*/
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range)
{
zskiplistNode *x;
int i;
/* If everything is out of range, return early. */
if (!zslIsInRange(zsl,range)) return NULL;
// 周遊跳躍表,查找符合範圍 min 項的節點
// T_wrost = O(N), T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
/* Go forward while *OUT* of range. */
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score,range))
x = x->level[i].forward;
}
/* This is an inner range, so the next node cannot be NULL. */
x = x->level[0].forward;
//redisAssert(x != NULL);
/* Check if score <= max. */
// 檢查節點是否符合範圍的 max 項
// T = O(1)
if (!zslValueLteMax(x->score,range)) return NULL;
return x;
}
/*
* 傳回 zsl 中最後一個分值符合 range 中指定範圍的節點。
*
* 如果 zsl 中沒有符合範圍的節點,傳回 NULL 。
*
* T_wrost = O(N), T_avg = O(log N)
*/
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range)
{
zskiplistNode *x;
int i;
/* If everything is out of range, return early. */
// 先確定跳躍表中至少有一個節點符合 range 指定的範圍,
// 否則直接失敗
// T = O(1)
if (!zslIsInRange(zsl,range)) return NULL;
// 周遊跳躍表,查找符合範圍 max 項的節點
// T_wrost = O(N), T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
/* Go forward while *IN* range. */
while (x->level[i].forward &&
zslValueLteMax(x->level[i].forward->score,range))
x = x->level[i].forward;
}
/* This is an inner range, so this node cannot be NULL. */
//redisAssert(x != NULL);
/* Check if score >= min. */
// 檢查節點是否符合範圍的 min 項
// T = O(1)
if (!zslValueGteMin(x->score,range)) return NULL;
// 傳回節點
return x;
}
/* Delete all the elements with score between min and max from the skiplist.
*
* 删除所有分值在給定範圍之内的節點。
*
* Min and max are inclusive, so a score >= min || score <= max is deleted.
*
* min 和 max 參數都是包含在範圍之内的,是以分值 >= min 或 <= max 的節點都會被删除。
*
* Note that this function takes the reference to the hash table view of the
* sorted set, in order to remove the elements from the hash table too.
*
* 節點不僅會從跳躍表中删除,而且會從相應的字典中删除。
*
* 傳回值為被删除節點的數量
*
* T = O(N)
*/
unsigned long zslDeleteRangeByScore(zskiplist *zsl, zrangespec *range/*, dict *dict*/)
{
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned long removed = 0;
int i;
// 記錄所有和被删除節點(們)有關的節點
// T_wrost = O(N) , T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
while (x->level[i].forward && (range->minex ?
x->level[i].forward->score <= range->min :
x->level[i].forward->score < range->min))
x = x->level[i].forward;
update[i] = x;
}
/* Current node is the last with score < or <= min. */
// 定位到給定範圍開始的第一個節點
x = x->level[0].forward;
/* Delete nodes while in range. */
// 删除範圍中的所有節點
// T = O(N)
while (x &&
(range->maxex ? x->score < range->max : x->score <= range->max))
{
// 記錄下個節點的指針
zskiplistNode *next = x->level[0].forward;
zslDeleteNode(zsl,x,update);
//dictDelete(dict,x->obj);
zslFreeNode(x);
removed++;
x = next;
}
return removed;
}
/* Delete all the elements with rank between start and end from the skiplist.
*
* 從跳躍表中删除所有給定排位内的節點。
*
* Start and end are inclusive. Note that start and end need to be 1-based
*
* start 和 end 兩個位置都是包含在内的。注意它們都是以 1 為起始值。
*
* 函數的傳回值為被删除節點的數量。
*
* T = O(N)
*/
unsigned long zslDeleteRangeByRank(zskiplist *zsl, unsigned int start, unsigned int end/*, dict *dict*/)
{
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned long traversed = 0, removed = 0;
int i;
// 沿着前進指針移動到指定排位的起始位置,并記錄所有沿途指針
// T_wrost = O(N) , T_avg = O(log N)
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--)
{
while (x->level[i].forward && (traversed + x->level[i].span) < start)
{
traversed += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
// 移動到排位的起始的第一個節點
traversed++;
x = x->level[0].forward;
// 删除所有在給定排位範圍内的節點
// T = O(N)
while (x && traversed <= end)
{
// 記錄下一節點的指針
zskiplistNode *next = x->level[0].forward;
// 從跳躍表中删除節點
zslDeleteNode(zsl,x,update);
// 從字典中删除節點
//dictDelete(dict,x->obj);
// 釋放節點結構
zslFreeNode(x);
// 為删除計數器增一
removed++;
// 為排位計數器增一
traversed++;
// 處理下個節點
x = next;
}
// 傳回被删除節點的數量
return removed;
}
int main() {}
zskiplist.h和zskiplist.c檔案是我自己取的,跳躍表的真正源碼在redis的redis.h檔案和t_zset.c檔案下