Redis的设计与实现（三）

左手的ㄟ右手 2022-02-25 01:06 175阅读 0赞

# 跳跃表 #

### 跳跃表基本概念？ ###

*  跳跃表是（skiplist）是一种有序的数据结构，通过在每个节点中维持多个指向其他节点的指针，从而使查找更加迅速。
 *  跳跃表的查找时间复杂度平均O（logN），最坏O（n）。
 *  跳跃表可以看作为是一个升级版的链表，从原理来推的话也有些像是从二叉树演变过来的。
 *  Redis中有序集合键的底层实现之一就是跳跃表（有序集合元素数量比较多，有序集合元素的成员是比较长的字符串）

快速了解跳跃表的底层推荐一篇博客（很简洁明了）：[https://blog.csdn.net/bigtree\_3721/article/details/51291974][https_blog.csdn.net_bigtree_3721_article_details_51291974]。

### 跳跃表的实现 ###

前边提到过，跳跃表可以称得上是一个进化版的链表，跳跃表中每一层的每一个节点都有一个前进指针，和跨度（就是当前指针指的节点和现在节点的距离），当然还有回退指针等，下边就来详细的分析以下它的底层数据结构和设计思路。

##### 跳跃表节点的设计思路 #####

typedef struct zskiplistNode{
        //后退
        struct zskiplistNode *backward;
        //分值
        double score;
        //成员对象
        robj *obj;
        //层
        struct zskiplistLevel{
            //前进指针
            struct zskiplistNode *forward;
            //跨度
            unsigined int span;
        } level[];
    }zskiplistNode;
    
    前进指针：比如我们需要遍历所有的跳跃表节点，那就使用前进指针来一步一步向前遍历（指向的节点跨度为1就相当于遍历了）
    
    后退指针：可以进行从后往前的遍历，从上边的结构体可以看到，每一个节点只有一个backward指针，因此，从后往前的遍历结过也一定是唯一的。
    
    跨度就相当于现实生活中的路程，也可以说成为里程，或者是排位。指向null的所有节点的跨度都为0.
    
    obj：是指向一个SDS类型的指针，它就是保存的值
    
    在我们使用有序集合的时候，它的有序性就是利用score来决定的，因此score是有序性的保证。
    
    层的实现是一个数组，为什么是一个数组有没有想过？
    我认为它是为了在查找过程中从上往下，从大跨度到小跨度，缩小范围的时候就层数减一进入下一层搜索。
    level可以包含多个元素，每一个元素都包含一个zskiplistLevel的结构体（指向其他节点的指针）：可以理解为level是某一个SDS值存的指向其他SDS值的指针。
    每次创建新的跳跃表节点时，程序根据幂等定律（越大的数出现的概率越少）随机生成一个1到32层的值作为level数组的大小。

#### 跳跃表 ####

跳跃表就是多个跳跃表节点组成，通过一个跳跃表节点来标记和记录一些跳跃表的信息（zskiplist）。

typedef struct zskiplist{
      
        //表头和表尾
        struct skiplistNode *header,*tial;
      
        //表中节点数量
        unsigined long length;
      
        //表中最大的层数 
        int level;
    
    }zskiplist;

理解了前面的，这个就只是一个头节点记录一些东西罢了。  
跳跃表虽然实现不难，但是对于有序查找效率还是极高的！

[https_blog.csdn.net_bigtree_3721_article_details_51291974]: https://blog.csdn.net/bigtree_3721/article/details/51291974