Skip to content

Commit 4e39fdf

Browse files
author
jiahaixin
committed
mock
1 parent 40d49bf commit 4e39fdf

File tree

12 files changed

+904
-204
lines changed

12 files changed

+904
-204
lines changed

docs/.DS_Store

0 Bytes
Binary file not shown.

docs/_images/.DS_Store

0 Bytes
Binary file not shown.

docs/_images/redis/zset.svg

Lines changed: 1 addition & 0 deletions
Loading

docs/data-management/.DS_Store

0 Bytes
Binary file not shown.

docs/data-structure-algorithms/Skip-List.md

Lines changed: 18 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,11 @@
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

@@ -49,7 +48,7 @@
4948

5049
像这样,我们每隔一个节点取一个数据作为索引节点(或者增加一个指针),比如我们要找 31 直接在索引链表就找到了(遍历 3 次),如果找 16 的话,在遍历到 31的时候,发现大于目标节点,就跳到下一层,接着遍历~ (蓝线表示搜索路径)
5150

52-
> 恩,如果你数了下遍历次数,没错,加不加索引都是 4 次遍历才能找到 16,这是因为数据量太少
51+
> 恩,如果你数了下遍历次数,没错,加不加索引都是 4 次遍历才能找到 16,这是因为数据量太少
5352
>
5453
> 数据量多的话,我们也可以多建几层索引,如下 4 层索引,效果就比较明显了
5554
@@ -113,7 +112,7 @@
113112

114113
我们上边建立索引层都是下层节点个数的 1/2,最高层索引的节点数就是 2 个,但是我们随意插入或者删除一个原有链表的节点,这个比例就肯定会被破坏。
115114

116-
作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中结点多了,索引结点就相应地增加一些,避免复杂度退化。
115+
作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中节点多了,索引节点就相应地增加一些,避免复杂度退化。
117116

118117
如果重建索引的话,效率就不能保证了。
119118

@@ -131,15 +130,15 @@
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
145144
class 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

docs/design-pattern/.DS_Store

0 Bytes
Binary file not shown.

docs/framework/.DS_Store

0 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)