1. 首頁 > 生活百科 > >

二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現( 三 )

生活百科

結構圖如下：

二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
5.2 創建節點及插入流程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;}// 設置表頭后退指針為NULLzsl->header->backward = NULL;// 初始表尾為NULLzsl->tail = NULL;return zsl;}新增元素：
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {zskiplistNode *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--) {// 存儲排位，便于更新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;}// 隨機生成層高，以25%的概率決定是否出現下一層，越高的層出現概率越低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++) {// 插入新節點，將新節點的當前層前指針更新為被修改節點的前指針x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;// 新節點跨度為后一節點的跨度 - 兩個節點之間的跨度x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}// 新節點加入，更新頂層 spanfor (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}5.3 SkipList與平衡樹的比較skiplist是為了實現sorted set相關功能 ， 紅黑樹也能實現，并且sorted set會存儲更多的冗余數據 。Redis作者antirez曾回答過這個問題，原文見https://news.ycombinator.com/item?id=1171423
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
大致內容如下：
skiplist只需要調整下節點到更高level的概率，就可以做到比B樹更少的內存消耗 。sorted set面對大量的zrange和zreverange操作，作為單鏈表遍歷的實現性能不亞于其它的平衡樹 。實現比較簡單 。
6 參考學習
  • 《Redis 設計與實現》：https://www.w3cschool.cn/hdclil/cnv2lozt.html
  • 雙端列表：https://blog.csdn.net/qq_20853741/article/details/111946054
作者：盛旭

推薦閱讀