《Redis 设计与实践》读书笔记系列六:跳跃表

仅为本书对Redis中跳跃表的介绍和实现。基本定义和算法会重开一篇。zset结构体代码在 7.6 章中。查找思想根据二分法,分跨度,查分值定位。大部分常用操作,如增删改查,排名,时间复杂度为平均O(logN),最坏O(N)N为跳跃表长度。

大部分情况下效率可和平衡树媲美。因其实现相较平衡树较为简单,故不少程序以跳跃表来代替平衡树。

它是有序集合的底层实现之一。当元素数量较多或元素member为较长字符串时,会以跳跃表来作为zset的底层实现。

跳跃表在Redis中两处地方用到,其一是作为有序集合底层实现之一,其二是集群节点中用作内部数据结构。

一个跳跃表zskipList结构,拥有多个跳跃表节点,zskiplistNode

zskipList 和 zskiplistNode 源码

typeof struct zskiplist{
    //书中写作structz。头尾指针
    struct skiplistNode *header,*tail;
    //节点数量,不包含头节点
    unsigned long length;
    //最大节点层数,不包含头节点
    int level;
}zskiplist;

typeof struct zskiplistNode{
    //后退指针。即上一个节点的指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象,即实际值的指针
    robj *obj;
    //层
    struct zskiplistLevel{
        //前进指针,即下一个节点的指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    }level[];
}zskiplistNode;

跳跃表与节点示意图

  1. L xx代表第几层,L1代表第一层。
  2. 绿色指针和BW代表回退指向,是backward属性。用于表尾向表头查找。
  3. o1 o2 o3 代表保存的值(member),1.0,2.0,3.0代表分值,已经由小到大排好序。
  4. 层有两个属性,1 个是前进指针,指向下一个层。2 个是跨度,到达下一个节点,垮了几个节点。层与层中间的连线则为指针方向,上面的数字,则代表跨度。前进指针用于表头向表尾查找。
  5. 表头节点也是zskiplistNode,相较其他节点,部分属性不会被用到,故没在图中体现。
  6. 紫色虚线为表头至表尾的遍历路线。

跳跃表与节点其结构特征的作用

层 level

层越多,访问速度就会越快。新创建跳跃表节点时,会随机造层,根据幂次定律,即越大出现的数概率越小,生成一个1-32之间的值作为层数。层数即索引。

前进指针 forward

用于表头向表尾访问节点,一直访问到NULL值结束。

通过header找到表头,表头与下一个节点中,取层数最少的最高层来遍历,确保跨度均为1。上述示意图紫色虚线就是遍历路线。

为什么是这个路线,而不是一直从L1L1,毕竟L1是每个节点必然都有的。而按照上述路线,还需要经过计算?

这涉及到跳表的查找顺序。例如插入一个节点,就需要先查询,这个查询会从头节点起,按最高层索引指向的层数开始二分查找,对比分值,选择插入节点。若从L1开始查找则会丧失二分查找特性。

即不可说专为遍历至表尾,而是通过这种查找方式,才能实现二分查找。非遍历,而是查找。

跨度 span

跨度实际作用用于排位(rank)在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排名。

后退指针 backward

用于从表尾访问表头的遍历,一直访问到NULL值结束。每次只能退回到上一个节点,即跨度必然为1。

分值和成员 score & obj

跳跃表中已由分值小到大排好序。obj必然为字符串对象指针,指向一个SDS值。obj必然唯一。分值可以不唯一,分值相同的节点按照obj在字典序中的大小来排序。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!