1- # 跳表──没听过但很犀利的数据结构
1+ # 跳表
22
33![ ] ( https://tva1.sinaimg.cn/large/008i3skNly1grm8yuyywxj30zk0qomyg.jpg )
44
55> Redis 是怎么想的:用跳表来实现有序集合?
66>
7- > Redis 的 zset 是一个复合结构,一方面它需要一个 hash 结构来存储 value 和 score 的对应关系,另一方面需要提供按照 score 来排序的功能,还需要能够指定 score 的范围来获取 value 列表的功能
87
9- 干过服务端开发的应该都知道 Redis 的 ZSet 使用跳表实现的(当然还有压缩列表),我就不从 1990 年的那个美国大佬 William Pugh 发表的那篇论文开始了,直接开跳
8+ 干过服务端开发的应该都知道 Redis 的 ZSet 使用跳表实现的(当然还有压缩列表、哈希表 ),我就不从 1990 年的那个美国大佬 William Pugh 发表的那篇论文开始了,直接开跳
109
1110![ 马里奥] ( https://i03piccdn.sogoucdn.com/bbdcce2d04b2bd83 )
1211
4948
5049像这样,我们每隔一个节点取一个数据作为索引节点(或者增加一个指针),比如我们要找 31 直接在索引链表就找到了(遍历 3 次),如果找 16 的话,在遍历到 31的时候,发现大于目标节点,就跳到下一层,接着遍历~ (蓝线表示搜索路径)
5150
52- > 恩,如果你数了下遍历次数,没错,加不加索引都是 4 次遍历才能找到 16,这是因为数据量太少
51+ > 恩,如果你数了下遍历次数,没错,加不加索引都是 4 次遍历才能找到 16,这是因为数据量太少,
5352>
5453> 数据量多的话,我们也可以多建几层索引,如下 4 层索引,效果就比较明显了
5554
113112
114113我们上边建立索引层都是下层节点个数的 1/2,最高层索引的节点数就是 2 个,但是我们随意插入或者删除一个原有链表的节点,这个比例就肯定会被破坏。
115114
116- 作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中结点多了,索引结点就相应地增加一些 ,避免复杂度退化。
115+ 作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中节点多了,索引节点就相应地增加一些 ,避免复杂度退化。
117116
118117如果重建索引的话,效率就不能保证了。
119118
131130
132131
133132
134- 其实跳表的思想很容易理解,可是架不住实战
133+ 其实跳表的思想很容易理解,可是架不住实战,我们接着看实战
135134
136135### 跳表的实现
137136
138- 差不多了解了跳表,其实就是加了几层索引的链表,一共有 N 层,以 0 ~ N-1 层表示,设第 0 层是原链表,抽取其中部分元素,在第 1 层形成新的链表,上下层的相同元素之间连起来;再抽取第 1 层部分元素,构成第 2 层,以此类推。
137+ 差不多了解了跳表,其实就是加了几层索引的链表,一共有 N 层,以 0 ~ N 层表示,设第 0 层是原链表,抽取其中部分元素,在第 1 层形成新的链表,上下层的相同元素之间连起来;再抽取第 1 层部分元素,构成第 2 层,以此类推。
139138
140- 题目 :设计跳表(https://leetcode-cn.com/problems/design-skiplist/)
139+ Leetcode 的题目 :设计跳表(https://leetcode-cn.com/problems/design-skiplist/)
141140
142- 链表结构,先搞定 Node
141+ 既然是链表结构,先搞个 Node
143142
144143``` java
145144class Node {
@@ -161,7 +160,7 @@ class Node{
161160> - 如果一个节点有第 i 层(i>=1)指针(即节点已经在第 1 层到第 i 层链表中),那么它有第(i+1)层指针的概率为 p。
162161> - 节点最大的层数不允许超过一个最大值,记为 MaxLevel。
163162>
164- > 这个计算随机层数的伪码如下所示 :
163+ > 这个计算随机层数的代码如下所示 :
165164>
166165> ``` java
167166> int randomLevel()
@@ -172,7 +171,7 @@ class Node{
172171> return level;
173172> ```
174173>
175- > `randomLevel()` 的伪码中包含两个参数 ,一个是 p,一个是 MaxLevel 。在 Redis 的 skiplist 实现中,这两个参数的取值为:
174+ > `randomLevel()` 包含两个参数 ,一个是 p,一个是 MaxLevel 。在 Redis 的 skiplist 实现中,这两个参数的取值为:
176175>
177176> ```
178177> p = 1 / 4
@@ -293,11 +292,11 @@ public Node search(int target) {
293292
294293> Redis 中的有序集合是通过跳表来实现的,严格点讲,其实还用到了压缩列表、哈希表。
295294>
296- > Redis 提供了两种编码的选择,根据数量量的多少进行对应的转化 ([ 源码地址] ( https://github.com/redis/redis/blob/8f59f131e5c26680d21e825695ef24a4fd7b99b7/src/server.h ) )
295+ > Redis 提供了两种编码的选择,根据数据量的多少进行对应的转化 ([ 源码地址] ( https://github.com/redis/redis/blob/8f59f131e5c26680d21e825695ef24a4fd7b99b7/src/server.h ) )
297296>
298297> - 当数据较少时,ZSet 是由一个 ziplist 来实现的
299298>
300- > - 当数据多的时候,ZSet 是由一个dict + 一个 skiplist 来实现的。简单来讲,dict 用来查询数据到分数的对应关系,而 skiplist 用来根据分数查询数据(可能是范围查找)。
299+ > - 当数据多的时候,ZSet 是由一个 dict + 一个 skiplist 来实现的。简单来讲,dict 用来查询数据到分数的对应关系,而 skiplist 用来根据分数查询数据(可能是范围查找)。
301300>
302301> ![ ] ( https://cdn.jsdelivr.net/gh/Jstarfish/picBed/redis/Blank%20diagram%20-%20Page%203.svg )
303302>
@@ -317,15 +316,15 @@ public Node search(int target) {
317316| ZSCAN | 迭代有序集合中的元素(包括元素成员和元素分值) |
318317| ** ZREVRANGE** | 返回有序集 key 中,指定区间内的成员。其中成员的位置按 score 值递减(从大到小)来排列 |
319318
320- 主要操作就是增删查一个数据,迭代数据、按区间查数据
319+ 主要操作就是增删查一个数据,迭代数据、按区间查数据,看下原因
321320
322321- 哈希表是无序的,且只能查找单个 key,不适宜范围查找
323322- 插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高(跳表只需要定位区间的起点,然后遍历就行了)
324323- Redis 选跳表实现有序集合,还有其他各种原因,比如代码实现相对简单些,且更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
325324
326325
327326
328- ## 这又是为什么?
327+ ## 扯点别的 | 这又是为什么?
329328
330329> 有序集合的英文全称明明是** sorted sets** ,为啥叫 zset 呢?
331330>
@@ -348,6 +347,10 @@ public Node search(int target) {
348347
349348跳表是一种动态数据结构,支持快速地插入、删除、查找操作,时间复杂度都是 $O(logn)$。
350349
350+ Redis 的 zset 是一个复合结构,一方面它需要一个 hash 结构来存储 value 和 score 的对应关系,另一方面需要提供按照 score 来排序的功能,还需要能够指定 score 的范围来获取 value 列表的功能
351+
352+ Redis 中的有序集合是通过压缩列表、哈希表和跳表的组合来实现的,当数据较少时,ZSet 是由一个 ziplist 来实现的。当数据多的时候,ZSet 是由一个dict + 一个 skiplist 来实现的
353+
351354![ ] ( https://i02piccdn.sogoucdn.com/06eb28fd58fa8840 )
352355
353356
0 commit comments