Redis skip list结构分析

1
MySQL Redis C/C++ Go 12774 次浏览

  如何实现一个海量用户的实时排名系统?或许可以用 mysql 搞一个纠结的方案;但要是选择了 redis,那绝对是既简单又优雅。Redis 的 zset 本身就是一种支持排序的集合,而 zset 的实现,则使用了 skip list 数据结构。Skip list 是一种多层次的有序链表,通过随机地选择层数来实现插入、查找和删除都是O(logn)的时间复杂度(和平衡树同样的效率,但实现比平衡树简单很多)。关 于 skip list 的具体介绍可以参见 William Pugh 的论文:Skip Lists: A Probabilistic Alternative to Balanced Trees 。下面我们来分析一下 redis 中 skip list 的实现。

  Redis 中 skip list 主要有 zskiplist 和 zskiplistNode 两个数据结构:

      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;

  其中 zskiplistNode 中包含一个 zskiplistLevel 数组,数组的大小根据节点所在的层数(level)决定。backward 指针是为了方便向后遍历而对 skip list 做的改进。

  主要的 API 有:

  zslCreate            创建一个 zskiplist,并添加一个具有最高层数 ZSKIPLIST_MAXLEVEL(代码中定义为32)的节点来管理分层的链表。

  zslInsert              插入一个节点到 zskiplist,并调整每一个层级的链表都是有序的。

  zslDelete            从 zskiplist 删除一个节点,并调整剩余节点在每个层级都是有序的。

  zslRandomLevel 为新加入的节点随机产生一个不超过 ZSKIPLIST_MAXLEVEL 的层数。

  zslInsert 和 zslDelete 函数都需要首先查找到合适的位置或节点,查找的代码很简单,直接包含在了这两个函数内:

  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 &&

                compareStringObjects (x->level[i].forward->obj,obj) < 0))) {

             rank[i] += x->level[i].span;

             x = x->level[i].forward;

         }

         update[i] = x;

      }

  查找是从 zskiplist 现有的最高层开始向前,并在查找的过程中根据规则转向低层的链表继续,一直到 skip list 的最低层为止。同时看到 redis 的实现中允许相同的 score 存在(这时按对象的字符串进行比较),但不允许具有相同值的对象并存(集合的特性)。

  下面通过一个例子来说明 skip list 的建立过程。

  按顺序执行下列语句:

      zslInsert (zsl, 5, obj1);              //level=1;

      zslInsert (zsl, 3, obj2);              //level=2;

      zslInsert (zsl, 4, obj3);              //level=1;

      zslInsert (zsl, 1, obj4);              //level=3;

      zslInsert (zsl, 2, obj5);              //level=1;

  现在的 zsl 结构如下图所示,其中 level array 的数组下标是为了图例更直观,实际不占存储空间。为了保证图例的简洁,backward 的指针没有画出,对应 level 0 红色指针相反方向的指针。

Redis skip list结构分析

  祝大家玩儿的开心!
      来自: rdc.taobao.com

请尽量让自己的答案能够对别人有帮助

0个答案

默认排序 按投票排序