网站建设最关键的两个素材,公司建网站一般多少钱,企业邮箱购买,注册安全工程师报名时间2022官网目录
前言
Sorted Set 基本结构
跳表的设计与实现
跳表数据结构
跳表结点查询
跳表结点层数设置
哈希表和跳表的组合使用 前言 有序集合#xff08;Sorted Set#xff09;是 Redis 中一种重要的数据类型#xff0c;它本身是集合类型#xff0c;同时也可以支持集合中…目录
前言
Sorted Set 基本结构
跳表的设计与实现
跳表数据结构
跳表结点查询
跳表结点层数设置
哈希表和跳表的组合使用 前言 有序集合Sorted Set是 Redis 中一种重要的数据类型它本身是集合类型同时也可以支持集合中的元素带有权重并按权重排序为什么 Sorted Set 能同时提供以下两种操作接口以及它们的复杂度分别是 O(logN)M 和 O(1) 呢 ZRANGEBYSCORE按照元素权重返回一个范围内的元素ZSCORE返回某个元素的权重值实际上这个问题背后的本质是为什么 Sorted Set 既能支持高效的范围查询同时还能以O(1) 复杂度获取元素权重值这其实就和 Sorted Set 底层的设计实现有关了Sorted Set 能支持范围查询这是因为它的核心数据结构设计采用了跳表而它又能以常数复杂度获取元素权重这是因为它同时采用了哈希表进行索引那么Sorted Set 是如何把这两种数据结构结合在一起的它们又是如何进行协作的呢 Sorted Set 基本结构 要想了解 Sorted Set 的结构就需要阅读它的代码文件这里需要注意的是在 Redis 源码中Sorted Set 的代码文件和其他数据类型不太一样它并不像哈希表的 dict.c/dict.h或是压缩列表的 ziplist.c/ziplist.h具有专门的数据结构实现和定义文件Sorted Set 的实现代码在t_zset.c文件中包括 Sorted Set 的各种操作实现同时 SortedSet 相关的结构定义在server.h文件中如果想要了解学习 Sorted Set 的模块和操作注意要从 t_zset.c 和 server.h 这两个文件中查找在知道了 Sorted Set 所在的代码文件之后可以先来看下它的结构定义Sorted Set 结构体的名称为 zset其中包含了两个成员分别是哈希表 dict 和跳表 zsl如下所示 Sorted Set 这种同时采用跳表和哈希表两个索引结构的设计思想是非常值得学习的因为这种设计思想充分利用了跳表高效支持范围查询如ZRANGEBYSCORE 操作以及哈希表高效支持单点查询如 ZSCORE 操作的特征这样一来就可以在一个数据结构中同时高效支持范围查询和单点查询这是单一索引结构比较难达到的效果不过既然 Sorted Set 采用了跳表和哈希表两种索引结构来组织数据在实现 Sorted Set 时就会面临以下两个问题 跳表或是哈希表中各自保存了什么样的数据跳表和哈希表保存的数据是如何保持一致的 跳表的设计与实现 首先来了解下什么是跳表skiplist跳表其实是一种多层的有序链表为了便于说明把跳表中的层次从低到高排个序最底下一层称为 level0依次往上是 level1、level2 等下图展示的是一个 3 层的跳表其中头结点中包含了三个指针分别作为 leve0 到 level2上的头指针 可以看到在 level 0 上一共有 7 个结点分别是 3、11、23、33、42、51、62这些结点会通过指针连接起来同时头结点中的 level0 指针会指向结点 3然后在这 7 个结点中结点 11、33 和 51 又都包含了一个指针同样也依次连接起来且头结点的 level 1 指针会指向结点 11这样一来这 3 个结点就组成了 level 1 上的所有结点最后结点 33 中还包含了一个指针这个指针会指向尾结点同时头结点的 level 2 指针会指向结点 33这就形成了 level 2只不过 level 2 上只有 1 个结点 33在对跳表有了直观印象后再来看看跳表实现的具体数据结构 跳表数据结构 先来看下跳表结点的结构定义如下所示 首先因为 Sorted Set 中既要保存元素也要保存元素的权重所以对应到跳表结点的结构定义中就对应了 sds 类型的变量 ele以及 double 类型的变量 score此外为了便于从跳表的尾结点进行倒序查找每个跳表结点中还保存了一个后向指针*backward指向该结点的前一个结点然后因为跳表是一个多层的有序链表每一层也是由多个结点通过指针连接起来的因此在跳表结点的结构定义中还包含了一个 zskiplistLevel 结构体类型的 level 数组level 数组中的每一个元素对应了一个 zskiplistLevel 结构体也对应了跳表的一层而zskiplistLevel 结构体定义了一个指向下一结点的前向指针*forward这就使得结点可以在某一层上和后续结点连接起来同时zskiplistLevel 结构体中还定义了跨度这是用来记录结点在某一层上的*forward指针和该指针指向的结点之间跨越了 level0 上的几个结点来看下面这张图其中就展示了 33 结点的 level 数组和跨度情况可以看到33 结点的level 数组有三个元素分别对应了三层 level 上的指针此外在 level 数组中level 2、level1 和 level 0 的跨度 span 值依次是 3、2、1 最后因为跳表中的结点都是按序排列的所以对于跳表中的某个结点可以把从头结点到该结点的查询路径上各个结点在所查询层次上的*forward指针跨度做一个累加这个累加值就可以用来计算该结点在整个跳表中的顺序另外这个结构特点还可以用来实现Sorted Set 的 rank 操作比如 ZRANK、ZREVRANK 等了解了跳表结点的定义后可以来看看跳表的定义在跳表的结构中定义了跳表的头结点和尾结点、跳表的长度以及跳表的最大层数如下所示 因为跳表的每个结点都是通过指针连接起来的所以在使用跳表时只需要从跳表结构体中获得头结点或尾结点就可以通过结点指针访问到跳表中的各个结点当在 Sorted Set 中查找元素时就对应到了 Redis 在跳表中查找结点而此时查询代码是否需要像查询常规链表那样逐一顺序查询比较链表中的每个结点呢其实是不用的因为这里的查询代码可以使用跳表结点中的 level 数组来加速查询 跳表结点查询 事实上当查询一个结点时跳表会先从头结点的最高层开始查找下一个结点而由于跳表结点同时保存了元素和权重所以跳表在比较结点时相应地有两个判断条件 当查找到的结点保存的元素权重比要查找的权重小时跳表就会继续访问该层上的下一个结点当查找到的结点保存的元素权重等于要查找的权重时跳表会再检查该结点保存的SDS类型数据是否比要查找的 SDS 数据小如果结点数据小于要查找的数据时跳表仍然会继续访问该层上的下一个结点但是当上述两个条件都不满足时跳表就会用到当前查找到的结点的 level 数组跳表会使用当前结点 level 数组里的下一层指针然后沿着下一层指针继续查找这就相当于跳到了下一层接着查找这部分的代码逻辑如下所示因为在跳表中进行查找、插入、更新或删除操作时都需要用到查询的功能可以重点了解下 跳表结点层数设置 这样一来有了 level 数组之后一个跳表结点就可以在多层上被访问到了而一个结点的level 数组的层数也就决定了该结点可以在几层上被访问到所以当要决定结点层数时实际上是要决定 level 数组具体有几层一种设计方法是让每一层上的结点数约是下一层上结点数的一半就像下面这张图展示的第 0 层上的结点数是 7第 1 层上的结点数是 3约是第 0 层上结点数的一半而第 2 层上的结点就 33 一个约是第 1 层结点数的一半 这种设计方法带来的好处是当跳表从最高层开始进行查找时由于每一层结点数都约是下一层结点数的一半这种查找过程就类似于二分查找查找复杂度可以降低到 O(logN)但这种设计方法也会带来负面影响那就是为了维持相邻两层上结点数的比例为 2:1一旦有新的结点插入或是有结点被删除那么插入或删除处的结点及其后续结点的层数都需要进行调整而这样就带来了额外的开销先来举个例子看下不维持结点数比例的影响这样虽然可以不调整层数但是会增加查询复杂度首先假设当前跳表有 3 个结点其数值分别是 3、11、23如下图所示 接着假设现在要插入一个结点 15如果不调整其他结点的层数而是直接插入结点 15的话那么插入后跳表 level 0 和 level 1 两层上的结点数比例就变成了为 4:1如下图所示 而假设持续插入多个结点但是仍然不调整其他结点的层数这样一来level0 上的结点数就会越来越多如下图所示 相应的如果要查找大于 11 的结点就需要在 level 0 的结点中依次顺序查找复杂度就是 O(N) 了所以为了降低查询复杂度就需要维持相邻层结点数间的关系再来看下维持相邻层结点数为 2:1 时的影响比如可以把结点 23 的 level 数组中增加一层指针如下图所示这样一来level 0 和 level 1 上的结点数就维持在了 2:1但相应的代价就是需要给 level 数组重新分配空间以便增加一层指针 类似的如果要在有 7 个结点的跳表中删除结点 33那么结点 33 后面的所有结点都要进行调整 调整后的跳表如下图所示可以看到结点 42 和 62 都要新增 level 数组空间这样能分别保存 3 层的指针和 2 层的指针而结点 51 的 level 数组则需要减少一层也就是说这样的调整会带来额外的操作开销 因此为了避免上述问题跳表在创建结点时采用的是另一种设计方法即随机生成每个结点的层数此时相邻两层链表上的结点数并不需要维持在严格的 2:1 关系这样一来当新插入一个结点时只需要修改前后结点的指针而其他结点的层数就不需要随之改变了这就降低了插入操作的复杂度在 Redis 源码中跳表结点层数是由 zslRandomLevel 函数决定zslRandomLevel 函数会把层数初始化为 1这也是结点的最小层数然后该函数会生成随机数如果随机数的值小于 ZSKIPLIST_P指跳表结点增加层数的概率值为 0.25那么层数就增加 1 层因为随机数取值到[0,0.25) 范围内的概率不超过 25%所以这也就表明了每增加一层的概率不超过25%下面的代码展示了 zslRandomLevel 函数的执行逻辑可以看下 现在就了解了跳表的基本结构、查询方式和结点层数设置方法那么下面接着来学习下Sorted Set 中是如何将跳表和哈希表组合起来使用的以及是如何保持这两个索引结构中的数据是一致的 哈希表和跳表的组合使用 其实哈希表和跳表的组合使用并不复杂首先从刚才介绍的 Sorted Set 结构体中可以看到Sorted Set 中已经同时包含了这两种索引结构这就是组合使用两者的第一步然后还可以在 Sorted Set 的创建代码t_zset.c文件中进一步看到跳表和哈希表被相继创建当创建一个 zset 时代码中会相继调用 dictCreate 函数创建 zset 中的哈希表以及调用 zslCreate 函数创建跳表如下所示 这样在 Sorted Set 中同时有了这两个索引结构以后接下来要想组合使用它们就需要保持这两个索引结构中的数据一致了简单来说这就需要在往跳表中插入数据时同时也向哈希表中插入数据而这种保持两个索引结构一致的做法其实也不难当往 Sorted Set 中插入数据时zsetAdd函数就会被调用所以可以通过阅读 Sorted Set 的元素添加函数 zsetAdd 了解到下面就来分析一下 zsetAdd 函数的执行过程首先zsetAdd 函数会判定 Sorted Set 采用的是 ziplist 还是 skiplist 的编码方式注意在不同编码方式下zsetAdd 函数的执行逻辑也有所区别这一讲重点关注的是skiplist 的编码方式所以接下来就主要来看看当采用 skiplist 编码方式时zsetAdd函数的逻辑是什么样的zsetAdd 函数会先使用哈希表的 dictFind 函数查找要插入的元素是否存在如果不存在就直接调用跳表元素插入函数 zslInsert 和哈希表元素插入函数 dictAdd将新元素分别插入到跳表和哈希表中这里需要注意的是Redis 并没有把哈希表的操作嵌入到跳表本身的操作函数中而是在zsetAdd 函数中依次执行以上两个函数这样设计的好处是保持了跳表和哈希表两者操作的独立性然后如果 zsetAdd 函数通过 dictFind 函数发现要插入的元素已经存在那么 zsetAdd 函数会判断是否要增加元素的权重值如果权重值发生了变化zsetAdd 函数就会调用 zslUpdateScore 函数更新跳表中的元素权重值紧接着zsetAdd 函数会把哈希表中该元素对应哈希表中的 key的 value 指向跳表结点中的权重值这样一来哈希表中元素的权重值就可以保持最新值了下面的代码显示了 zsetAdd 函数的执行流程可以看下 总之可以记住的是Sorted Set 先是通过在它的数据结构中同时定义了跳表和哈希表来实现同时使用这两种索引结构然后Sorted Set 在执行数据插入或是数据更新的过程中会依次在跳表和哈希表中插入或更新相应的数据从而保证了跳表和哈希表中记录的信息一致这样一来Sorted Set 既可以使用跳表支持数据的范围查询还能使用哈希表支持根据元素直接查询它的权重
