文章目录一、zset数据结构二、跳表什么是skipList跳表？ 1 .查找跳转表2 .插入跳转表3 .删除跳转表4 .更新跳转表
一. zset数据结构
由于sorted set比set添加了权重参数score，因此可以在score中组织集合中的元素，也可以从score范围中检索元素列表。
zset有两个不同的实现：zipList和skipList。
zipList：
满足以下两个条件：
[score，value]键和值对的数量小于128； 每个元素的长度小于64字节；skipList:
不满足上述两个条件时使用跳转表(3358www.Sina.com/和hash组合) )。
混列用于存储value到score的映射，可以在o(1)小时内找到value的对应分数。 skipList按照从小到大的顺序存储得分； skipList中的每个元素的值为[score，value]，对Redis的zset而言不是单一结构，而是skipList。
实现方式：在Redis sorted set内部，使用HashMap和跳转表skipList保证数据的存储和有序。 HashMap包含成员到score的映射，但跳转表中存储了所有成员。 排序依据是存储在HashMap中的score，使用跳转表结构可以获得相对较高的搜索效率。 使用跳转表的结构可以获得更高的搜索效率
以下是使用跳表和哈希表的图像。
使用跳转表时的图像：
zset结构既支持单元素查询，也支持范围查询。
二、跳表什么是skipList跳表？ 改造链表，在链表中建立索引。 也就是说，每两个节点将一个节点提取到更高级别。 提取的级别称为索引。 http://www.Sina.com/http://www.Sina.com /
由很多层结构组成。 每层都是有序的链表。 最底层(Level 1)的链表包含所有元素。 如果元素位于级别I的链表中，则它也显示在级别I下的链表中。 每个节点包含两个指针，指向同一链表中的下一个元素及其下一级元素。zipList
跳表能保证增加、删除、调查等操作时的时间复杂度为o(logn )，且维持结构平衡的成本比较低，是随机依赖的。 在多次插入和删除四元树后，需要使用Rebalance来重新调整结构平衡。
这种链表加多级索引的结构，就是跳表。
跳台占用的空间比较大，实际上是跳表的特点：的思想。
跳表的优点：
由很多层结构组成。 每层都是有序的链表。 最底层(Level 1)的链表包含所有元素。 如果元素位于级别I的链表中，则它也显示在级别I下的链表中。 每个节点包含两个指针，指向同一链表中的下一个元素及其下一级元素。 1 .跳表查找跳表查找从顶层链表开头的元素开始，然后遍历链表，直到找到元素大于或等于目标元素的节点。 如果当前元素正好等于目标，则直接返回。 如果当前元素小于目标元素，则垂直向下一个级别继续搜索。 如果当前元素大于目标，或到达链表末尾，则移动到上一个节点的位置，垂直下降到下一个级别。
2 .插入跳转表是跳转表插入数据，必须首先找到要插入的位置，然后执行插入操作。
可以在图中看到插入的过程。
如果继续在跳转表中插入元素，则两个索引点之间的节点可能太多。 如果节点过多，创建索引的好处也将消失。 因此，必须保持索引和原始链表的大小平衡。 也就是说，当节点增加时，索引也会相应增加，以避免两个索引之间的节点过多而降低搜索效率。
跳表通过随机函数保持了这个平衡。 在跳转表中插入数据时，也可以同时将此数据插入索引中。 在中，需要随机函数来确定要插入到哪个级别的索引中。
这样，可以有效防止跳跃式仪表劣化，效率降低。
3 .删除跳表自上而下，查找第一个出现的节点的索引，按层次找到对应的节点。 删除在o(logn )层次结构中找到的节点，如果该层次结构中只剩下一个节点，则删除除原始链表以外的整个层次结构。 作为o(logn )整体，跳表的删除操作的时间复杂度为o ) logn。跳表的缺点：
4 .调用更新跳表zadd方法时，如果对应的value不存在，则为插入过程。 如果此值已经存在，并且只是调整score的值，则必须遵循更新流程。 假设这个新的score值不引起排序位置的改变，则不需要调整位置，直接修改元素的score值就可以了。 但是，排序位置改变后，必须调整位置。