大厂高频面试剖析 之 Redis跳跃表

内容纲要

跳跃表的优点

  • 可以快速查找到需要的节点

  • 可以在O(1)的时间复杂度下,快速获得跳跃表的头节点、尾结点、长度和高度

跳跃表的应用场景

跳跃表是Redis有序集合(sorted-set)类型的底层实现,效率高,实现简单。

跳跃表的思想

跳跃表是将有序链表中的部分节点提取出来分层,每一层都是一个有序链表。如图所示

file

简单讲:链表加多级索引的结构,就叫做跳跃表。使用多级索引在跳跃表中查找元素,可以提升查询效率。

跳跃表的查找

在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针指向null,则从当前节点下降一层继续向后查找。

举例:

file

查找元素9,按道理我们需要从头结点开始遍历,一共遍历8个结点才能找到元素9。

第一次分层:遍历5次找到元素9(红色的线为查找路径)

file

第二次分层:遍历4次找到元素9

file

第三层分层:遍历4次找到元素9

file

这种数据结构,就是跳跃表,它具有二分查找的功能。

跳跃表的插入

上面例子中,9个结点,一共4层,是理想的跳跃表。

可以通过抛硬币(概率1/2)的方式来决定新插入结点跨越的层数

  • 正面:插入上层

  • 背面:不插入

跳跃表的删除

通过找到指定元素并删除每层的该元素即可。

跳跃表的特点

  • 每层都是一个有序链表

  • 查找次数近似于层数(1/2)

  • 底层包含所有元素

  • 空间复杂度 O(n) 扩充了一倍

Redis跳跃表的实现

//跳跃表节点
typedef struct zskiplistNode {

     sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示,
    但是在redis4.0.1中直接使用sds类型表示 */
     double score;//存储排序的分值
     struct zskiplistNode *backward;//后退指针
    /*
    层,柔性数组,随机生成1-64的值
    */
     struct zskiplistLevel {
         struct zskiplistNode *forward; //指向本层下一个节点

         unsigned int span;//本层下个节点到本节点的元素个数
    } level[];
} zskiplistNode;

//链表
typedef struct zskiplist{
    //表头节点和表尾节点
    structz skiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;

}zskiplist;

完整的跳跃表结构,如下图所示

file

赞(0) 打赏
未经允许不得转载:魔豆IT » 大厂高频面试剖析 之 Redis跳跃表
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!