Redis深度解析，有哪些疑问？

Redis数据结构之Zset 目录 一、zset数据结构 二、跳表skipList 什么是跳表？ 1.跳表的查找 2.跳表的插入 3.跳表的删除 4.跳表的更新 一、zset数据结构 相比于set，sorted set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列，还可以通过 score 的范围来获取元素的列表。 zset有两种不同的实现，分别是zipList和skipList。 zipList： 满足以下两个条件： 1)、[score,value]键值对数量少于128个； 2)、每个元素的长度小于64字节； skipList: 不满足以上两个条件时使用跳表（组合了hash和skipList） 1)、hash用来存储value到score的映射，这样就可以在O(1)时间内找到value对应的分数； 2)、skipList按照从小到大的顺序存储分数； 3)、skipList每个元素的值都是[score,value]对 Redis 中 zset 不是单一结构完成，是跳表和哈希表共同完成。 实现方式：Redis sorted set的内部使用HashMap和跳跃表(skipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score，使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。 使用zipList的示意图如下所示： 使用跳表时的示意图： zset 结构中，既支持按单个元素查询，又支持范围查询。 二、跳表skipList 什么是跳表？ 对链表进行改造，在链表上建索引，即每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引。这种链表加多级索引的结构，就是跳表 跳表的特点: 1)、由许多层结构组成。 2)、每一层都是一个有序的链表。 3)、最底层 (Level 1) 的链表包含所有元素。 4)、如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。 5)、每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。 跳表的优点： 跳表可以保证增、删、查等操作时的时间复杂度为O(logN)，且维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要Rebalance来重新调整结构平衡。 跳表的缺点： 跳表占用的空间比较大（多级索引），其实就是一种空间换时间的思想。 1.跳表的查找 跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。 2.跳表的插入 为跳表插入数据，首先需要找到插入的位置，然后执行插入操作。 可以通过图看一下插入的过程： 如果我们不停的向跳表中插入元素，就可能会造成两个索引点之间的结点过多的情况。结点过多的话，我们建立索引的优势也就没有了。所以我们需要维护索引与原始链表的大小平衡，也就是结点增多了，索引也相应增加，避免出现两个索引之间结点过多的情况，查找效率降低。 跳表是通过一个随机函数来维护这个平衡的，当我们向跳表中插入数据的的时候，我们可以选择同时把这个数据插入到索引里，那我们插入到哪一级的索引呢，这就需要随机函数，来决定我们插入到哪一级的索引中。 这样可以很有效的防止跳表退化，而造成效率变低。 3.跳表的删除 1)、自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O(logN） 2)、删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O(logN） 总体上，跳跃表删除操作的时间复杂度是O(logN)。 整个删除过程，可以简化理解为：先找到，断关联，删内存 4.跳表的更新 当我们调用zadd方法时，如果对应的value不存在，那就是插入过程。如果这个value 已经存在了，只是调整一下 score 的值，那就需要走一个更新的流程。假设这个新的score 值不会带来排序位置上的改变，那么就不需要调整位置，直接修改元素的 score 值就可以了。但是如果排序位置改变了，那就要调整位置。