ToB企服应用市场:ToB评测及商务社交产业平台

标题: zset底层的数据结构为什么使用调表而不是红黑树 [打印本页]

作者: 天津储鑫盛钢材现货供应商 时间: 2022-6-23 18:11
标题: 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、因为不需要旋转操作，因此跳表的实现更简单

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)