redis 跳跃表

跳跃表可以看作是对有序链表的改进,我们知道对链表中元素查找的时间复杂度时O(n),但是,如果我们可以知道中间节点的大小,就可以判断元素是在链表的前半段还是后半段,将查找范围减半,通过这种思想,就可以把链表的查找时间复杂度降低到O(lgn)
跳跃表就是借助这种思想,但是因为链表中的元素数随着插入元素和删除元素的减少,很难定位中位数在哪里,所以,跳跃表采用随机的方法来定义每个节点的层数。

跳跃表类定义

redis 中跳跃表主要有两个结构zskiplist和zskiplistNode
zskiplist保存跳跃表的头尾节点以及跳跃表的节点最大层高
zskiplistNode 保存跳跃表中的具体数据

typedef struct zskiplistNode {
	//成员对象
    sds ele;

	//分值
    double score;

	// 后退指针
    struct zskiplistNode *backward;
  	// 层
    struct zskiplistLevel {
    	//跨度指针
        struct zskiplistNode *forward;
        
        //跨度
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {

	//表头结点和表尾节点
    struct zskiplistNode *header, *tail;
    
    //表中节点数量
    unsigned long length;
    
    //表中层数最大的节点层数
    int level;
} zskiplist;

跳跃表结构

如下图所示:
有32层的时跳跃表创建的时候创建的头节点,这个节点不保存数据
第一个数据score为1.0,存储的数据时O1,层数是4
第二个数据score为2.0, 存储数据为O2, 层数为2
第三个数据score为3.0,存储数据为O3, 层数为5
《redis 跳跃表》
分析查找score为2.0的节点的过程

  • 首先从zskiplist可以得到当前存在节点中最大的层数为5
  • 查看header的第5层指向的节点的score,得到score为3,比2大,所以当前节点还是header节点
  • 查看header的第四层指向的节点的score,得到score为1,比2小,当前节点为O1
  • 查看O1的第四层指向的节点的score值,得到score为3,比2大,当前节点为O1
  • 查看O1的第三层指向的节点的score值,得到score为2,等于2,返回

总结

  • redis有zskiplist和zsdkiplistNode两个结构组成,zskiplist保存跳跃表的表头、表尾节点,长度等信息,zskiplistNode保存具体的数据
  • 跳跃表是按照score的升序排列的,score的值可以相同,如果score的值相同,就按照value的字典升序排列
  • 每个跳跃表的层数是1~32的一个随机数
    原文作者:qq_35728402
    原文地址: https://blog.csdn.net/qq_35728402/article/details/109106839
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞