redis设计与实现之跳跃表

小灰灰 2024-02-19 17:33 39阅读 0赞

### 1. 跳跃表简介 ###

1.  跳跃表（skiplist）是一个有序结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
2.  跳跃表的平均查询时间复杂度为O(logN)，最坏O(N)
3.  为什么选择跳跃表？
4.  大部分情况下性能与平衡树媲美
5.  实现比平衡树更为简单

### 2. 跳跃表的实现 ###

1.  Redis的跳跃表有两个结构定义
2.  节点结构为zskiplistNode
3.  跳跃表信息zskiplist：图5-1最左边  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70]
4.  zskiplist结构属性
5.  header：指向跳跃表表头节点
6.  tail：指向跳跃表表尾节点
7.  level：指跳跃表当前层数最大那个节点的层数（表头层数不计算在内）
8.  length：记录跳跃表的长度，跳跃表当前节点数量（表头节点不计算在内）
9.  zskiplistNode结构属性
10. 层（Level）：节点中用L1、L2、L3等表示，每层都带有两个属性：前进指针与跨度。前进指针用于访问表尾方向的其他节点；跨度记录了前进指针指向节点与当前节点距离
11. 后退（backward）指针：节点中用BW表示，指向当前节点的前一个节点
12. 分值（score）：各个节点中的1.0、2.0、3.0是节点的分值，在跳跃表中，节点按各自保存的分支从小到大排序
13. 成员对象（object）：各个节点中的o1、o2、o3是节点所保存的对象

### 3. 跳跃表节点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70 1]

#### 3.1 层 ####

1.  跳跃表节点的level数组可以包含多个元素，一般来说层数越多访问其他节点的速度越快。
2.  每次创建一个新跳跃表节点的时候，程序根据幂次定律（power law，越大的数出现的频率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”

#### 3.2 前进指针 ####

每个层都有一个指向表尾方向下一个节点的前进指针。图5-3用虚线表示出了程序从表头向表尾方向，遍历跳跃表中所有节点的路径：  
  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70 2]

1.  迭代程序首先访问跳跃表中的第一个节点（表头），然后从第四层的前进指针移动到第一个节点
2.  在第二个节点时，程序沿着第二层的前进指针移动到第三个节点
3.  在第三个节点时，程序沿着第二层的前进指针移动到第四个节点
4.  当程序继续沿着第二层的前进指针移动时，它碰到一个null，程序知道这时已经达到了跳跃表表尾，结束本次遍历

问题：为什么从所有跨度为1的前进指针中选择层数最高的指针进行遍历？  
答

1.  因为层数最高跳跃的步进越大且过滤掉的数据越大，类似于二叉树，先过滤掉一半数据，层数最高如果只有两步，且刚好是中间位置，则就是二叉树的第一步二分，可以滤掉更多的数据。
2.  并且可以判断，如果前进是超过了当前目标值，则说明目标值就在当前与下个跳跃节点之间，那么可以用同样的方式判断递减一层的数据，直至找到最低层，从最底层开始查找目标值，这样保证了遍历的链表元素是最少的，小于log(N)复杂度

#### 3.3 跨度 ####

#### 3.4 后退指针 ####

#### 3.5 分值和成员 ####

### 4. 跳跃表插入 ###

原图地址：https://en.wikipedia.org/wiki/File:Skip\_list\_add\_element-en.gif  
![在这里插入图片描述][20200429101159240.gif]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c72931245ac84f31962224937deed3dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/220a699b737e4b2fbf9cda1a0c9014f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1OTc4MTk_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/3017229d10f543ceafca6b4dca5ea809.png
[20200429101159240.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/360833188178452fad8f0ac89974f399.png