[top]
目标：redis有序集合的原理，为什么选择跳跃链表
二分查找
简单定义
在一个单调有序的集合中查找元素
- 每次将集合分为左右两部分
- 判断解在哪个部分中并调整集合上下界
- 重复直到找到目标元素
时间复杂度
O(logn)优于直接顺序查找O(n)
例子
查找值为22的记录过程：
- mid = (low+high) / 2
- mid<x: low = mid + 1
- mid>x: high = mid -1
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 13 | 15 | 18 | 22 | 28 | 34 | 56 | 65 | 70 | 80 |
| low=0 | min=4 | high=9 |
mid = 4 （mid = (low+high) / 2）
因为key 4 的值是28，28比22大，即 high = mid -1，新的high = 3
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 13 | 15 | 18 | 22 | 28 | 34 | 56 | 65 | 70 | 80 |
| low=0 | high=3 |
high=3 值是22 已经找到返回结果3
跳跃链表
定义
跳表由多条链表L0 ……LN以及下行指针构成
| 第三级索引 | -♾️ | +♾️ | |||||||
| 第二级索引 | -♾️ | 44 | +♾️ | ||||||
| 第一级索引 | -♾️ | 23 | 44 | 56 | +♾️ | ||||
| 原始链表 | -♾️ | 12 | 23 | 31 | 44 | 56 | 64 | 78 | +♾️ |
每条链表包含元素检索值单调递增，包含两个特殊节点 -∞(起始节点)和+∞(终止节点)
L0包含所有元素，对任意的i>0，Li+1是Li的子集，且Li+1中的每一个节点，有一个下行指针，指向Li中与之有相同索引值的节点
在跳跃表中查找一个元素x
- 从最上层的链(Ln)的开头开始
- 假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较
- x = y 输出查询成功
- x > y 从p向右移动到q的位置
- x < y 从p向下移动一格
- 如果当前位置在最底层的链中(L0),且还要往下移动的话,则输出查询失败
例子
假设要寻找78这个值
| 第三级索引 | -♾️ | +♾️ | |||||||
| ↓ | |||||||||
| 第二级索引 | -♾️ | 44 | +♾️ | ||||||
| ↓ | |||||||||
| 第一级索引 | -♾️ | 23 | 44 | 56 | +♾️ | ||||
| ↓ | |||||||||
| 原始链表 | -♾️ | 12 | 23 | 31 | 44 | 56 | 64 | 78 | +♾️ |
Comments NOTHING