redis中的zset的原理_有序集合 原理

一、zset有序集合的原理
如果有序集合元素个数少于128个且元素值小于64字节，使用压缩列表（新版本已经废弃压缩列表改用listpack数据结构了）
如果不满足上述条件，采用跳表作为redis的底层数据结构

二、压缩列表

1.由连续内存块组成的顺序性数据结构
2.根据数据大小和类型的不同进行数据内存的分配
3.缺点：插入过大或过多的数据会导致“连锁更新”，影响访问性能

三、跳表

1.在链表的基础上改进而来的，是一种多层的有序链表。查找的平均时间复杂度为O(logN)
2.实现层级靠的是节点结构体中的zskiplistLevel结构体类型的level数组
3.调表查询过程：
（1）比较权重，小的话访问该层下一个节点
（2）比较SDS类型数据大小，小的话访问该层下一个节点
（3）以上两种都不满足的情况下，跳到当前节点的下一层
4.跳表节点层数设置
头结点直接创建最大层数（64），其他节点生成小于0.25的随机数就一直创建层，一旦随机数超过0.25就确定该节点层数
5.为什么用跳表不用平衡树
（1）内存占用方面更灵活
（2）范围查找更容易
（3）算法实现更容易

参考：图解Redis介绍