面试题
- Redis 的跳跃列表了解吗？这个数据结构有什么缺点
- Redis 项目里面怎么用？Redis 的数据结构都了解哪些？布隆过滤器怎么用？
- Redis 的多路 IO 复用如何理解，为什么单线程还可以抗那么高的 QPS
- Redis 的 zset 底层实现，压缩列表和跳表，这样设计的优缺点
- Redis 的跳表说一下，解决了哪些问题，时间复杂度和空间复杂度如何
- Redis 的 zset 用的什么数据结构
Redis 数据类型的底层数据结构
- SDS 动态字符串
- 双向链表
- 压缩列表 ziplist
- 哈希表 hashtable
- 跳表 skiplist
- 整数集合 intset
- 快速列表 quicklist
- 紧凑列表 listpack
skiplist 跳表面试题⭐️
为什么引出跳表
单链表
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高 O(N)
痛点
数组和链表各有优缺点，链表遍历的时候，时间复杂度最差会出现 O(N) ，我们优化下一下，尝试（升维）空间换时间，给链表加个索引，称为“索引升级”，两两取首即可。
-
优化1
-
优化2
画了一个包含 64 个节点的链表，按照前面讲的这种思路，建立了五级索引
概述
-
跳表是可以实现二分查找的有序链表
skiplist 是一种以空间换取时间的结构。由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表。但是，由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多。
-
跳表 = 链表 + 多机索引
跳表时间/空间复杂度介绍
-
跳表的时间复杂度
跳表查询的时间复杂度分析，如果链表里有N个结点，会有多少级索引呢？O(logN)按照我们前面讲的，两两取首。每两个结点会抽出一个节点作为上一级索引的节点，一次估算：
第一级索引的结点个数大约就是 n/2，
第二级索引的结点个数大约就是 n/4，
第三级索引的结点个数大约就是 n/8，依次类推......
也就是说，第k级索引的结点个数是第 k-1级索引的结点个数的 1/2，那第k级索引结点的个数就是 n/(2^k)
假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到
n / (2^h) = 2，从而求得h=log2n - 1，如果包含原始链表这一层，整个跳表的高度就是log2nn/2^k → n/2^k = 2 → h = log2n - 1 → O(logn) -
跳表的空间复杂度
跳表查询的空间复杂度分析O(N)比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？
第一步：首先原始链表长度为 n；
第二步：两两取首，每层索引的节点数：n/2，n/4，n/8 ... 8，4，2 每上升一级就减少一半，直到剩下 2 个节点，以此类推；如果我们把每层索引的节点数写出来，就是一个等比数列。
这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n) 。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。
第三步：思考三三取首，每层索引的结点数：n/3, n/9, n/27 ... , 9, 3, 1 以此类推；
第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。为了方便计算，我们假设最高一级的索引结点个数是 1。我们把每级索引的结点个数都写下来，也是一个等比数列
通过等比数列求和公式，总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是 O(n) ，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。所以空间复杂度是 O(n);
优缺点
-
优点
跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的
-
缺点
维护成本相对较高，在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是
O(1)，但是新增或者删除时需要把所有索引都更新一遍，为了保证原始链表中数据的有序性，我们需要先找到要动作的位置，这个查找操作就会比较耗时最后在新增和删除的过程中的更新，时间复杂度也是O(log n)。