使用Go复刻skiplist核心功能

万万哇  金牌会员 | 5 天前 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 833|帖子 833|积分 2499

0、引言

正好做LC逐日一题要求实现一个跳表，于是学习了redis的扩展skiplist，并使用Go进行复刻学习。学习参考了文章：Redis内部数据布局详解(6)——skiplist - 铁蕾的个人博客
因为作者本领有限，本文只是对跳表的核心功能：创建节点与跳表、插入节点、删除节点、获取节点rank、根据rank获取节点、获取分数区间的ele集合进行复刻，其余的需要自己去实现。
1、跳表核心布局

源码的数据布局定义如下：
  1. #define ZSKIPLIST_MAXLEVEL 32
  2. #define ZSKIPLIST_P 0.25
  4. /* ZSETs use a specialized version of Skiplists */
  5. typedef struct zskiplistNode {
  6.     sds ele;
  7.     double score;
  8.     struct zskiplistNode *backward;
  9.     struct zskiplistLevel {
  10.         struct zskiplistNode *forward;
  11.         unsigned long span;
  12.     } level[];
  13. } zskiplistNode;
  15. typedef struct zskiplist {
  16.     struct zskiplistNode *header, *tail;
  17.     unsigned long length;
  18.     int level;
  19. } zskiplist;
复制代码

  • 定义了两个常量，一个是跳表的最大层数ZSKIPLIST_MAXLEVEL，一个是当前节点含有i+1层的概率ZSKIPLIST_P
  • 跳表节点zskiplistNode：

    • ele，为string范例，存放的是节点的数据
    • score，存放数据对应的值
    • backward指向前一个跳表节点，只存在第一层链接中
    • level存放多层指向下一个节点的指针forawrd，同时含有一个span用于表示当前指针超过了多少个节点，用于实现通过排名查询。注意，span是表示当前层，从header到当前节点跨过的指针数，它不包罗指针的起始节点，但是包罗终点节点。

  • 跳表本身zskiplist：

    • header和tail，指向跳表首尾的指针
    • length跳表总节点数
    • level跳表当前的层数

复刻：
  1. package goskiplist
  3. const (
  4.         SKIPLIST_MAXLEVEL = 32
  5.         SKIPLIST_P        = 0.25
  6. )
  8. type GskiplistLevel struct {
  9.         forward *GskiplistNode
  10.         span    uint64
  11. }
  12. type GskiplistNode struct {
  13.         ele      string
  14.         score    float64
  15.         backward *GskiplistNode
  16.         level    []GskiplistLevel
  17. }
  18. type Gskiplist struct {
  19.         header *GskiplistNode
  20.         tail   *GskiplistNode
  21.         length uint64
  22.         level int
  23. }
复制代码
2、创建跳表节点与跳表

创建跳表节点源码：
  1. zskiplistNode *zslCreateNode(int level, double score, sds ele) {
  2.     zskiplistNode *zn =
  3.         zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
  4.     zn->score = score;
  5.     zn->ele = ele;
  6.     return zn;
  7. }
复制代码
复刻：
  1. func createNode(level int, score float64, ele string) *GskiplistNode{
  2.         node := &GskiplistNode{
  3.                 ele:      ele,
  4.                 score:    score,
  5.                 level:    make([]GskiplistLevel, level),
  6.                 backward: nil,
  7.         }
  8.         return node
  9. }
复制代码
创建跳表源码：
  1. /* Create a new skiplist. */
  2. zskiplist *zslCreate(void) {
  3.     int j;
  4.     zskiplist *zsl;
  6.     zsl = zmalloc(sizeof(*zsl));
  7.     zsl->level = 1;
  8.     zsl->length = 0;
  9.     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
  10.     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
  11.         zsl->header->level[j].forward = NULL;
  12.         zsl->header->level[j].span = 0;
  13.     }
  14.     zsl->header->backward = NULL;
  15.     zsl->tail = NULL;
  16.     return zsl;
  17. }
复制代码
初始化设置了跳表的层数为1、节点数为0、初始化头节点指针，分配内存。注意，头节点并不计算在length中。
颠末初始化，创建的跳表如下：

3、向跳表插入节点

源码：
  1. zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
  2.     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  3.     unsigned long rank[ZSKIPLIST_MAXLEVEL];
  4.     int i, level;
  6.     serverAssert(!isnan(score));
  7.     x = zsl->header;
  8.     for (i = zsl->level-1; i >= 0; i--) {
  9.         /* store rank that is crossed to reach the insert position */
  10.         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
  11.         while (x->level[i].forward &&
  12.                 (x->level[i].forward->score < score ||
  13.                     (x->level[i].forward->score == score &&
  14.                     sdscmp(x->level[i].forward->ele,ele) < 0)))
  15.         {
  16.             rank[i] += x->level[i].span;
  17.             x = x->level[i].forward;
  18.         }
  19.         update[i] = x;
  20.     }
  21.     /* we assume the element is not already inside, since we allow duplicated
  22.      * scores, reinserting the same element should never happen since the
  23.      * caller of zslInsert() should test in the hash table if the element is
  24.      * already inside or not. */
  25.     level = zslRandomLevel();
  26.     if (level > zsl->level) {
  27.         for (i = zsl->level; i < level; i++) {
  28.             rank[i] = 0;
  29.             update[i] = zsl->header;
  30.             update[i]->level[i].span = zsl->length;
  31.         }
  32.         zsl->level = level;
  33.     }
  34.     x = zslCreateNode(level,score,ele);
  35.     for (i = 0; i < level; i++) {
  36.         x->level[i].forward = update[i]->level[i].forward;
  37.         update[i]->level[i].forward = x;
  39.         /* update span covered by update[i] as x is inserted here */
  40.         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
  41.         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
  42.     }
  44.     /* increment span for untouched levels */
  45.     for (i = level; i < zsl->level; i++) {
  46.         update[i]->level[i].span++;
  47.     }
  49.     x->backward = (update[0] == zsl->header) ? NULL : update[0];
  50.     if (x->level[0].forward)
  51.         x->level[0].forward->backward = x;
  52.     else
  53.         zsl->tail = x;
  54.     zsl->length++;
  55.     return x;
  56. }
复制代码
zslInsert重要实现了向跳表中插入一个节点，节点的值为ele，分数为score。
解析：
（1）创建数组与断言检查
  1. zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  2. unsigned long rank[ZSKIPLIST_MAXLEVEL];
  3. int i, level;
  4. serverAssert(!isnan(score));
  5. x = zsl->header;
复制代码

  • *update[]用于记录每一层插入的位置，update表示节点在第i层，应该插入在update节点之后。
  • rank[]用于记录每一层的跨度，rank表示从第i层，跳到update节点的跨度。使用了前缀和的头脑。
  • *x用于节点的遍历
  • serverAssert用于判断数值是否非常
（2）查找插入位置
  1. for (i = zsl->level-1; i >= 0; i--) {
  2.         /* store rank that is crossed to reach the insert position */
  3.         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
  4.         while (x->level[i].forward &&
  5.                 (x->level[i].forward->score < score ||
  6.                     (x->level[i].forward->score == score &&
  7.                     sdscmp(x->level[i].forward->ele,ele) < 0)))
  8.         {
  9.             rank[i] += x->level[i].span;
  10.             x = x->level[i].forward;
  11.         }
  12.         update[i] = x;
  13.     }
复制代码
i从当前跳表的最高层向下遍历。在每一次遍历中：
<ul>rank初始赋值上一层的结果，若为最高层则赋值0
若当<strong>前层的当前节点存在下一节点，并且分数 zsl->level) {        for (i = zsl->level; i < level; i++) {            rank = 0;            update = zsl->header;            update->level.span = zsl->length;        }        zsl->level = level;    }[/code]使用zslRandomLevel函数设定新节点的最高层数。假如这个最高层数大于目前跳表的层数，那么就需要设定新高层的rank和update。
zslRandomLevel的实现如下：
  1. level = zslRandomLevel();
  2.     if (level > zsl->level) {
  3.         for (i = zsl->level; i < level; i++) {
  4.             rank[i] = 0;
  5.             update[i] = zsl->header;
  6.             update[i]->level[i].span = zsl->length;
  7.         }
  8.         zsl->level = level;
  9.     }
复制代码
调整每一层的要插入的位置的前一个节点的指针指向，并且更新span。
假设在第i层，我们称update为pre，未更新前pre的下一个节点未next，那么因为要在pre和next之间插入新的节点，更新pre的span为pre到next的距离-cur到next的距离。更新cur的span为cur到next的距离。
第二个循环是为了更新当前节点的更高层未更新节点的span值。
颠末这一次调整，如图：

这里我画图用于形象的表示span的计算过程，它采用了前缀和的方式：

（5）更新新节点的前指针
  1. int zslRandomLevel(void) {
  2.     static const int threshold = ZSKIPLIST_P*RAND_MAX;
  3.     int level = 1;
  4.     while (random() < threshold)
  5.         level += 1;
  6.     return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
  7. }
复制代码
假如update[0]不是头节点，那么它就是x的前一个节点。假如x的后节点存在，则更新x的后节点的前指针指向x，否则x是末端节点，让tail指向它。
复刻Go源码：
  1. x = zslCreateNode(level,score,ele);
  2.     for (i = 0; i < level; i++) {
  3.         x->level[i].forward = update[i]->level[i].forward;
  4.         update[i]->level[i].forward = x;
  6.         /* update span covered by update[i] as x is inserted here */
  7.         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
  8.         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
  9.     }
  10. /* increment span for untouched levels */
  11.     for (i = level; i < zsl->level; i++) {
  12.         update[i]->level[i].span++;
  13.     }
复制代码
4、删除跳表节点
  1. x->backward = (update[0] == zsl->header) ? NULL : update[0];
  2.     if (x->level[0].forward)
  3.         x->level[0].forward->backward = x;
  4.     else
  5.         zsl->tail = x;
  6.     zsl->length++;
  7.     return x;
复制代码
先来看zslDelete：它是删除节点的最上层，update的更新方法与插入同等。接着就是删除score和ele相同的节点，其中node参数用于提供保存删除节点的作用。在Go语言的复刻中，我们可以直接返回node和是否删除成功。
再看zslDeleteNode，它是删除节点的下游详细实现，详细细节如下：

  • 逐层删除x，假如当前层有x，则需要将前一个节点的后指针指向x的后指针，然后更新前一个节点的span；否则只用更新span
  • 假如x的后节点存在，则更新后节点的backward指针，否则修改跳表的tail。
  • 假如存在高层，在删除x后为空层，要修改跳表的层数。
  • 减去一个length
Go复刻如下：
  1. // 向跳表插入一个节点，同时返回插入好的节点。
  2. // ele不能为空串，否则返回nil。
  3. func (this *Gskiplist) Insert(score float64, ele string) *GskiplistNode {
  4.         if ele == "" {
  5.                 return nil
  6.         }
  7.         update := make([]*GskiplistNode, SKIPLIST_MAXLEVEL)
  8.         rank := make([]uint64, SKIPLIST_MAXLEVEL)
  9.         var x *GskiplistNode
  11.         x = this.header
  12.         //更新update以及rank
  13.         for i := this.level - 1; i >= 0; i-- {
  14.                 rank[i] = 0
  15.                 if i != this.level-1 {
  16.                         rank[i] = rank[i+1]
  17.                 }
  18.                 for x.level[i].forward != nil &&
  19.                         (x.level[i].forward.score < score ||
  20.                                 (x.level[i].forward.score == score && x.level[i].forward.ele < ele)) {
  21.                         rank[i] += x.level[i].span
  22.                         x = x.level[i].forward
  23.                 }
  24.                 update[i] = x
  25.         }
  26.         level := this.randomLevel()
  27.         //更新最大层数
  28.         if level > this.level {
  29.                 for i := this.level; i < level; i++ {
  30.                         rank[i] = 0
  31.                         update[i] = this.header
  32.                         update[i].level[i].span = this.length
  33.                 }
  34.                 this.level = level
  35.         }
  36.         x = createNode(level, score, ele)
  38.         //插入操作
  39.         for i := 0; i < level; i++ {
  40.                 x.level[i].forward = update[i].level[i].forward
  41.                 update[i].level[i].forward = x
  42.                 //更新x和前一个节点的span
  43.                 x.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
  44.                 update[i].level[i].span = (rank[0] - rank[i]) + 1
  45.         }
  47.         //更新更高层
  48.         for i := level; i < this.level; i++ {
  49.                 update[i].level[i].span++
  50.         }
  52.         //更新前节点指针指向
  53.         x.backward = nil
  54.         if update[0] != this.header {
  55.                 x.backward = update[0]
  56.         }
  57.         if x.level[0].forward != nil {
  58.                 x.level[0].forward.backward = x
  59.         } else {
  60.                 this.tail = x
  61.         }
  62.         this.length++
  63.         return x
  64. }
复制代码
5、获取节点的rank
  1. void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
  2.     int i;
  3.     for (i = 0; i < zsl->level; i++) {
  4.         if (update[i]->level[i].forward == x) {
  5.             update[i]->level[i].span += x->level[i].span - 1;
  6.             update[i]->level[i].forward = x->level[i].forward;
  7.         } else {
  8.             update[i]->level[i].span -= 1;
  9.         }
  10.     }
  11.     if (x->level[0].forward) {
  12.         x->level[0].forward->backward = x->backward;
  13.     } else {
  14.         zsl->tail = x->backward;
  15.     }
  16.     while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
  17.         zsl->level--;
  18.     zsl->length--;
  19. }
  21. int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
  22.     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  23.     int i;
  25.     x = zsl->header;
  26.     for (i = zsl->level-1; i >= 0; i--) {
  27.         while (x->level[i].forward &&
  28.                 (x->level[i].forward->score < score ||
  29.                     (x->level[i].forward->score == score &&
  30.                      sdscmp(x->level[i].forward->ele,ele) < 0)))
  31.         {
  32.             x = x->level[i].forward;
  33.         }
  34.         update[i] = x;
  35.     }
  36.     /* We may have multiple elements with the same score, what we need
  37.      * is to find the element with both the right score and object. */
  38.     x = x->level[0].forward;
  39.     if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
  40.         zslDeleteNode(zsl, x, update);
  41.         if (!node)
  42.             zslFreeNode(x);
  43.         else
  44.             *node = x;
  45.         return 1;
  46.     }
  47.     return 0; /* not found */
  48. }
复制代码
从高层逐个寻找，找到即返回。
6、根据排名获取节点
  1. //删除节点，返回这个节点以及是否成功
  2. func (this *Gskiplist) Delete(score float64, ele string) (*GskiplistNode, bool) {
  3.         update := make([]*GskiplistNode, SKIPLIST_MAXLEVEL)
  4.         var x *GskiplistNode
  6.         x = this.header
  7.         for i := this.level - 1; i >= 0; i-- {
  8.                 for x.level[i].forward != nil &&
  9.                         (x.level[i].forward.score < score ||
  10.                                 (x.level[i].forward.score == score && x.level[i].forward.ele < ele)) {
  11.                         x = x.level[i].forward
  12.                 }
  13.                 update[i] = x
  14.         }
  16.         x = x.level[0].forward
  17.         //从底层删除
  18.         if x != nil && x.score == score && x.ele == ele {
  19.                 this.deleteNode(x, update)
  20.                 return x, true
  21.         }
  22.         //未找到对应节点
  23.         return nil, false
  24. }
  26. func (this *Gskiplist) deleteNode(x *GskiplistNode, update []*GskiplistNode) {
  27.         for i := 0; i < this.level; i++ {
  28.                 if update[i].level[i].forward == x {
  29.                         //在这一层，存在x
  30.                         update[i].level[i].span += x.level[i].span - 1
  31.                         update[i].level[i].forward = x.level[i].forward
  32.                 } else {
  33.                         //不存在则只更新span
  34.                         update[i].level[i].span--
  35.                 }
  36.         }
  37.         if x.level[0].forward != nil {
  38.                 x.level[0].forward.backward = x.backward
  39.         } else {
  40.                 this.tail = x.backward
  41.         }
  43.         //若x独占高层，需要逐个清除
  44.         for this.level > 1 && this.header.level[this.level-1].forward == nil {
  45.                 this.level--
  46.         }
  47.         this.length--
  48. }
复制代码
Go复刻：
[code]// 根据排名获取节点func (this *Gskiplist) GetElementByRank(rank uint64) *GskiplistNode {        return this.getElementByRankFromNode(this.header, this.level-1, rank)}func (this *Gskiplist) getElementByRankFromNode(startNode *GskiplistNode, startLevel int, rank uint64) *GskiplistNode {        x := startNode        var traversed uint64        for i := startLevel; i >= 0; i-- {                for x.level.forward != nil && traversed+x.level.span = 0; i-- {                for x.level.forward != nil && x.level.forward.score < low {                        x = x.level.forward                }        }        x = x.level[0].forward        for x != nil && x.score

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

万万哇

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表