大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说zset底层的数据结构为什么使用调表而不是红黑树[亲测有效],希望您对编程的造诣更进一步.
zset底层的数据结构为什么使用调表而不是红黑树
前言
Redis中使用到的数据结构以及各个数据对象的底层数据结构在上一篇文章已经写得非常详细，这里不再赘述。
https://www.cnblogs.com/ruigedada/p/16248689.html
zset的底层数据结构是压缩列表和跳表，当满足以下条件时，Redis将使用压缩列表存储
-
有序集合保存的元素个数要小于 128 个；
-
有序集合保存的所有元素成员的长度都必须小于 64 字节。
我们都知道，调表的查找时间复杂度为O(logn)，但是红黑树和AVL树的查找效率也是O(logn)呀，为什么zset的底层是调表而不是红黑树或者AVL树呢？
一、跳表、红黑树和AVL树的区别
| 跳表 | 红黑树 | AVL树 | |
|---|---|---|---|
| 查询时间复制度 | O(logn) | O(logn) | O(logn) |
| 插入/删除效率 | 最高 | 低 | 最低 |
| 范围查询效率 | 高 | 低 | 低 |
| 实现难易 | 易 | 难 | 难 |
-
1、虽然跳表，红黑树和AVL树的查找时间复杂度都是O(logn)，但相比于跳表，红黑树和AVL树的插入/删除效率更低。为什么呢？
-
跳表在插入或者删除时，我们只需要考虑相邻两个结点就可以了，其插入删除的过程和链表的过程实际上是差不多的，只是需要考虑索引的问题。
-
红黑树和AVL树都是自平衡树，所以在插入和删除时会涉及到结点的旋转问题，因此其效率不如跳表，而AVL树是一个严格的平衡树，追求的是绝对的平衡，因此其效率比红黑树还不如，这也是HashMap不使用AVL树的原因之一。
-
-
2、对于范围查找来说，跳表只需要查找最小的那个值，然后往后遍历就可以了。
-
3、因为不需要旋转操作，因此跳表的实现更简单
原文地址：https://www.cnblogs.com/ruigedada/archive/2022/05/14/16270084.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/5267.html
