zset底层数据结构
zset底层数据结构
- 常见的面试题
- Redis的数据类型
- 简单说一下zset底层数据结构
- 压缩列表的底层数据结构
- 采用压缩列表的场景
- 跳表的定义
- 跳表是如何查找某个元素的
- 跳表的时间复杂度
- 为什么需要跳表
- 为什么用跳表而不用红黑树或者二叉树
常见的面试题
- redis几种基本数据结构
- zset底层数据结构？简单说说跳表底层的数据结构？
- 什么时候采用压缩列表、什么时候采用跳表呢？
- 跳表的时间复杂度
- 简单描述一下跳表如何查找某个元素呢？
- zset为什么用跳表而不用二叉树或者红黑树呢
Redis的数据类型
简单说一下zset底层数据结构
zset底层数据结构对应压缩列表和跳表。
压缩列表的底层数据结构
压缩列表其实是比较好理解的，它本质上是一个数组。只不过是他增加了列表的长度、尾部的偏移量、列表元素个数、以及列表的结尾的标志。这样的话，就有利于快速的查找列表的首、尾的节点。
但是对于其他寻找正常的元素，比如元素1、元素2等等，效率仍没有很高效，只能一个个遍历。
采用压缩列表的场景
- 有序集合保存的元素数量小于128个。
- 有序集合保存的所有元素的长度小于64字节。
不符合则采用跳表。
跳表的定义
跳表在链表的基础上增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。
比如针对一张普通的链表，我想要查找元素27该如何查找呢？
只能从链表的头部一个个往后遍历，这个过程中我们需要遍历6次，才能找到元素27。
跳表是如何查找某个元素的
建立多级索引，比如如果我们建立一级索引，对应的是下面这张图，每隔一个元素建立一个索引，就建立了四个索引。
利用一次索引我们需要遍历5个节点就可以找到27。每个遍历的节点如下：
如果我们觉得慢的话，可以建立二级索引：
你就在一级索引的基础上，再每间隔一个元素建立一个索引的节点。
我们每次遍历的节点如下：
针对下面这张图，我们利用跳表快速的找到70。整个查找过程就是在多级索引之间跳来跳去，最后定位到了这个元素。所以又称为“跳表”。
跳表的时间复杂度
当数据量特别大的时候，跳表的查找时间复杂度就是O(logn)。因为他本身利用的思想就有点类似于二分法。
为什么需要跳表
因为普通链表查找一个元素需要的时间复杂度是O(n)。而跳表查找一个时间复杂度是O（logn）。查找的速度会更快。
删除插入等时间复杂度也是O(logn)。
为什么用跳表而不用红黑树或者二叉树
像二叉树和红黑树，他本身查找一个元素时间复杂度不也是O(logn)吗？
为啥不采用树形结构，其中有两个原因：
- 因为zset有一个很核心的操作，叫做范围查找，也就是说我们要查找某个区间范围内的元素。
跳表可以做到O(logn)时间复杂度内的快速查找。比如说你可以找到区间的起点，然后依次往后遍历就可以了。但是红黑树范围查找的效率没有跳表高。 - 跳表的实现比红黑树或者平衡二叉树要简单，易懂，更容易实现。可以有效地控制跳表的索引层级来控制内存的消耗。
参考资料：面试官：讲讲 Zset 底层数据原理？为什么不用树而用跳表|Redis 面试
女爷i
爱被打了一巴掌
骑猪看日落
怼烎@
我就是我
还没有评论，来说两句吧...