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

跳跃表的优点

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

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

跳跃表的应用场景

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

跳跃表的思想

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

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

跳跃表的查找

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

举例：

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

第一次分层：遍历5次找到元素9（红色的线为查找路径）

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

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

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

跳跃表的插入

上面例子中，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;

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