[Redis] 数据结构zset压缩列表实现和跳表实现讲解-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Redis] 数据结构zset压缩列表实现和跳表实现讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

😚一个不甘平凡的普通人，致力于为Golang社区和算法学习做出贡献，期待您的关注和认可，陪您一起学习打卡！！！😘😘😘
🤗专栏：算法学习
🤗专栏：Go实战
💬个人主页：个人主页

跳表问题
[Redis] 数据结构zset压缩列表实现和跳表实现讲解

1. redis数据结构

redis 有五种数据结构：string，hash，list，set，zset

2. zset底层数据结构：

压缩列表 或者跳表实现
压缩列表的实现底层数据结构：底层是一个数组，相对于数组多的是一个列表长度，尾部偏移量，列表元素个数和列表结束表标识，可以更好的找到列表的首部和尾部，对于中间的其他元素来说仍然需要进行遍历，所以时间复杂度是o(n)
[Redis] 数据结构zset压缩列表实现和跳表实现讲解

3. 什么时候采用压缩列表？

有序集合保存的元素数量小于128个有序集合保存的所有元素长度小于64字节

4. 跳表是什么？

跳表是在压缩列表的基础上增加了多级索引，通过多级索引的位置进行跳转，实现了快速查找元素跳表skiplist的寻址逻辑可以简单地概括为：从最高层开始寻址，当前节点的next指针如果指向null的话就下降一层，next指针指向的下一个元素值如果小于查找值，就继续走，如果大于的话就调用backward后退指针找前一个元素再比较，直到找到对应的位置。

举例：普通链表需要逐个遍历找到目标值27
[Redis] 数据结构zset压缩列表实现和跳表实现讲解

跳表建立一级索引，每隔一个值建立一个索引，可以找到目标元素
[Redis] 数据结构zset压缩列表实现和跳表实现讲解

或者在一级索引的基础上，建立二级索引来加快查找速度
[Redis] 数据结构zset压缩列表实现和跳表实现讲解
时间复杂度是o(logn)

5.在最前面我们提到redis最终并没有采用树这样的结构，其中一个原因就跟指针个数有关：

（不清楚树的数据结构也没关系，只需要知道树的指针固定有两个，左子树指针和右子树指针）跳表节点的平均指针数是1.3个，而树的指针数固定为2个，指针又占用一定内存，显然跳表比树是用到更少的内存，redis是基于内存的操作，瓶颈最有可能就是内存大小和网络带宽，所以跳表比起树更节约内存一点。
[Redis] 数据结构zset压缩列表实现和跳表实现讲解