zset底层数据结构

叁歲伎倆 2023-10-12 20:25 5阅读 0赞

### zset底层数据结构 ###

*  常见的面试题
 *  Redis的数据类型
 *  简单说一下zset底层数据结构
 *   *  压缩列表的底层数据结构
 *  采用压缩列表的场景
 *   *  跳表的定义
     *  跳表是如何查找某个元素的
 *  跳表的时间复杂度
 *   *  为什么需要跳表
 *  为什么用跳表而不用红黑树或者二叉树

# 常见的面试题 #

1.  redis几种基本数据结构
2.  zset底层数据结构？简单说说跳表底层的数据结构？
3.  什么时候采用压缩列表、什么时候采用跳表呢？
4.  跳表的时间复杂度
5.  简单描述一下跳表如何查找某个元素呢？
6.  zset为什么用跳表而不用二叉树或者红黑树呢

# Redis的数据类型 #

![在这里插入图片描述][dc64ebf81e144652abef352fae7c79cc.png]

# 简单说一下zset底层数据结构 #

zset底层数据结构对应**压缩列表**和**跳表**。

## 压缩列表的底层数据结构 ##

![在这里插入图片描述][7ff84f1e4f7c4c3cb7e619682764358f.png]  
压缩列表其实是比较好理解的，它本质上是一个数组。只不过是他增加了列表的长度、尾部的偏移量、列表元素个数、以及列表的结尾的标志。这样的话，就有利于快速的查找列表的首、尾的节点。

但是对于其他寻找正常的元素，比如元素1、元素2等等，效率仍没有很高效，只能一个个遍历。

# 采用压缩列表的场景 #

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

不符合则采用跳表。

## 跳表的定义 ##

跳表在链表的基础上增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。

![在这里插入图片描述][6d07ef0d206e497a8959f56761b740de.png]  
比如针对一张普通的链表，我想要查找元素27该如何查找呢？  
只能从链表的头部一个个往后遍历，这个过程中我们需要遍历6次，才能找到元素27。

## 跳表是如何查找某个元素的 ##

建立多级索引，比如如果我们建立一级索引，对应的是下面这张图，每隔一个元素建立一个索引，就建立了四个索引。  
![在这里插入图片描述][cc97ce47d10643b9a5636fa7e566a7be.png]  
利用一次索引我们需要遍历5个节点就可以找到27。每个遍历的节点如下：  
![在这里插入图片描述][69237a88f1aa4d1aa7c3045b37ff97a2.png]  
如果我们觉得慢的话，可以建立二级索引：  
你就在一级索引的基础上，再每间隔一个元素建立一个索引的节点。

我们每次遍历的节点如下：  
![在这里插入图片描述][2c1da6a9269b43fd81d20edc8a647282.png]  
针对下面这张图，我们利用跳表快速的找到70。整个查找过程就是在多级索引之间跳来跳去，最后定位到了这个元素。所以又称为“跳表”。  
![在这里插入图片描述][77c35b4ad98b41558f1526779529fe4f.png]

# 跳表的时间复杂度 #

当数据量特别大的时候，跳表的查找时间复杂度就是O(logn)。因为他本身利用的思想就有点类似于二分法。

## 为什么需要跳表 ##

因为普通链表查找一个元素需要的时间复杂度是O(n)。而跳表查找一个时间复杂度是O（logn）。查找的速度会更快。

删除插入等时间复杂度也是O(logn)。

# 为什么用跳表而不用红黑树或者二叉树 #

![在这里插入图片描述][c0da3d542e9e4593aca5791c28b5798d.png]  
像二叉树和红黑树，他本身查找一个元素时间复杂度不也是O(logn)吗？

为啥不采用树形结构，其中有两个原因：

1.  因为zset有一个很核心的操作，叫做范围查找，也就是说我们要查找某个区间范围内的元素。  
    ![在这里插入图片描述][28c65f970c6544248871c6ce4b5a4ba3.png]  
    跳表可以做到O(logn)时间复杂度内的快速查找。比如说你可以找到区间的起点，然后依次往后遍历就可以了。但是红黑树范围查找的效率没有跳表高。
2.  跳表的实现比红黑树或者平衡二叉树要简单，易懂，更容易实现。可以有效地控制跳表的索引层级来控制内存的消耗。

**参考资料**：[面试官：讲讲 Zset 底层数据原理？为什么不用树而用跳表|Redis 面试][Zset _Redis]

[dc64ebf81e144652abef352fae7c79cc.png]: https://img-blog.csdnimg.cn/dc64ebf81e144652abef352fae7c79cc.png
[7ff84f1e4f7c4c3cb7e619682764358f.png]: https://img-blog.csdnimg.cn/7ff84f1e4f7c4c3cb7e619682764358f.png
[6d07ef0d206e497a8959f56761b740de.png]: https://img-blog.csdnimg.cn/6d07ef0d206e497a8959f56761b740de.png
[cc97ce47d10643b9a5636fa7e566a7be.png]: https://img-blog.csdnimg.cn/cc97ce47d10643b9a5636fa7e566a7be.png
[69237a88f1aa4d1aa7c3045b37ff97a2.png]: https://img-blog.csdnimg.cn/69237a88f1aa4d1aa7c3045b37ff97a2.png
[2c1da6a9269b43fd81d20edc8a647282.png]: https://img-blog.csdnimg.cn/2c1da6a9269b43fd81d20edc8a647282.png
[77c35b4ad98b41558f1526779529fe4f.png]: https://img-blog.csdnimg.cn/77c35b4ad98b41558f1526779529fe4f.png
[c0da3d542e9e4593aca5791c28b5798d.png]: https://img-blog.csdnimg.cn/c0da3d542e9e4593aca5791c28b5798d.png
[28c65f970c6544248871c6ce4b5a4ba3.png]: https://img-blog.csdnimg.cn/28c65f970c6544248871c6ce4b5a4ba3.png
[Zset _Redis]: https://www.bilibili.com/video/BV1kh411x7Jc/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb