当前位置: 首页>数据库>正文

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现

跳跃表简介

跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。

以下是个典型的跳跃表例子(图片来自维基百科):

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现,REdis中跳跃表的层数晋升率是多少 redis跳跃表实现_Redis,第1张

有序链表

如下图所有,有一个有序(按score从小到大排序)双向链表。当我们要在该链表中查找score = 13 的节点时,我们只能从链表的头节点开始,依次向下比较查找(图中红色箭头所示),需要访问7个节点,算法时间复杂度为 O(n)。

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现,REdis中跳跃表的层数晋升率是多少 redis跳跃表实现_跳跃表_02,第2张

在上述链表中,虽然我们知道节点的排列是有序的,但是由于我们每次只能从一个节点访问到相邻的下一个节点,因此我们只能依次遍历每个节点进行查找。

优化

那么,要是有些节点存在不止一个可访问的后继节点呢?这样的话找查找时,我们就不必遍历每一个节点,而是可以跳跃的访问链表中的节点。

如下图所示,我们添加 L2 层访问指针,让其中一些节点不仅可以访问相邻的后继节点,还可以访问第二个后继节点。那么现在我们要查找 score = 13 的节点时,可以先在 L2层上向后查找到可以到达的最右节点 11(score <= 13),然后在 forward 层(也可以称为 L1层)上向后查找,最后找到 score = 13的节点需要访问4个节点。速度快了一倍!!!

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现,REdis中跳跃表的层数晋升率是多少 redis跳跃表实现_跳跃表_03,第3张

所以,要是我们能够在节点上继续往上添加更高层的访问指针(层数越高,节点的跨度越大),那么查找的速度会越来越快,到达 log级别。

跳跃表

跳跃表就是遵循了上述的优化思想,让每个节点拥有一个指针数组,使它们能够进行多级的跳跃,从而将查找的时间复杂度降低为O(log n)。

跳跃表节点的定义:

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward; //后向指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;//每一层中的前向指针
        unsigned int span;//x.level[i].span 表示节点x在第i层到其下一个节点需跳过的节点数。注:两个相邻节点span为1
    } level[];
} zskiplistNode;

用图像表示就是这样:

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现,REdis中跳跃表的层数晋升率是多少 redis跳跃表实现_skiplist_04,第4张

其中,我们将指针数组的最大长度设置为32。多个zskiplistNode就组成了一个跳跃表。

我们使用zskiplist数据结构来表示跳跃表:

#define ZSKIPLIST_MAXLEVEL 32 //最大层数
#define ZSKIPLIST_P 0.25 // 1/P

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; //头节点, 尾节点
    unsigned long length;//节点总数
    int level;//总层数
} zskiplis

随机算法

跳跃表中,每个节点的指针数组长度是不一样的,是一个在[1,32]之间的随机整数,随机算法如下:

int zslRandomLevel(void) {
    int level = 1;
    // TODO 了解这个公式背后的数学原理
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

使用随机算法,在概率上可以保证上一层的节点数为下一层的1/P。那么SkipList可以看成是一棵平衡的P叉树,从最顶层开始查找某个节点需要的时间是O(logpN)。
每个跳跃表节点中的指针数组中的每一层,都指向随后一个指针数组大小大于等于该节点指针数据大小的节点。

一次典型的跳跃表查询过程

REdis中跳跃表的层数晋升率是多少 redis跳跃表实现,REdis中跳跃表的层数晋升率是多少 redis跳跃表实现_指针数组_05,第5张

如上图所示,在上述跳跃表中查找 score = 7的节点过程为:

  • 在L4层上找到满足条件(score <= 7)的最右节点 1,1 < 7 所以继续向下层查找。
  • 在L3层上找到满足条件(score <= 7)的最右节点 6,6 < 7 所以继续向下层查找。
  • 在L2层上找到满足条件(score <= 7)的最右节点 6,6 < 7 所以继续向下层查找。
  • 在L1层上找到满足条件(score <= 7)的最右节点 7,7 = 7 查找完毕。



https://www.xamrdz.com/database/6z41962852.html

相关文章: