请选择 进入手机版 | 继续访问电脑版

[Redis] 为何Redis利用 跳表而非红黑树实现SortedSet

[复制链接]
查看157 | 回复20 | 2021-9-14 01:30:31 | 显示全部楼层 |阅读模式
目次

知道跳表(Skip List)是在看关于Redis的书的时间 ,Redis中的有序集合利用 了跳表数据布局 。接着就查了一些博客,来学习一下跳表。后面会利用 Java代码来简单实现跳表。

什么是跳表

跳表由William Pugh发明,他在论文《Skip lists: a probabilistic alternative to balanced trees》中具体 先容 了跳表的数据布局 和插入删除等操作,论文是这么先容 跳表的:

  1. Skip lists are a data structure that can be used in place of balanced trees.Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
复制代码

也就是说,跳表可以用来更换 红黑树,利用 概率平衡 技术,使得插入、删除操作更简单、更快。先来看论文里的一张图:

这里写图片形貌

观察上图

  • a:已排好序的链表,查找一个结点最多必要 比较N个结点。
  • b:每隔2个结点增长 一个指针,指向该结点间距为2的后续结点,那么查找一个结点最多必要 比较ceil(N/2)+1个结点。
  • c,每隔4个结点增长 一个指针,指向该结点间距为4的后续结点,那么查找一个结点最多必要 比较ceil(N/4)+1个结点。
  • 若每第
    1. 2^i
    复制代码
    个结点都有一个指向间距为
    1. 2^i
    复制代码
    的后续结点的指针,如许 不断增长 指针,比较次数会降为log(N)。如许 的话,搜索 会很快,但插入和删除会很困难。

一个拥有k个指针的结点称为一个k层结点(level k node)。按照上面的逻辑,50%的结点为1层,25%的结点为2层,12.5%的结点为3层…假如 每个结点的层数随机选取,但仍服从如许 的分布呢(上图e,对比上图d)?

使一个k层结点的第i个指针指向第i层的下一个结点,而不是它后面的第2^(i-1)个结点,那么结点的插入和删除只必要 原地修改操作;一个结点的层数,是在它被插入的时间 随机选取的,并且永不改变。由于 如许 的数据布局 是基于链表的,并且额外的指针会跳过中心 结点,以是 作者称之为跳表(Skip Lists)。

二分查找底层依靠 数组随机访问的特性,以是 只能用数组实现。若数据存储在链表,就没法用二分搜索 了?

实在 只需稍微 改造下链表,就能支持类似 “二分”的搜索 算法,即跳表(Skip list),支持快速的新增、删除、搜索 操作。

Redis中的有序集合(Sorted Set)就是用跳表实现的。我们知道红黑树也能实现快速的插入、删除和查找操作。那Redis 为何不选择红黑树来实现呢?

为何Redis利用
跳表而非红黑树实现SortedSet

跳表的意义毕竟 在于何处?

单链表即使存储的数据有序,若搜索 某数据,也只能从头到尾遍历,搜索 服从 很低,匀称 时间复杂度是O(n)。

寻求 极致的程序员就开始想了,那这该怎样 进步 链表布局 的搜索 服从 呢?
若如下图,对链表建立一级“索引”,每两个结点提取一个结点到上一级,把抽出来的那级叫作索引或索引层。图中的down表示down指针,指向下一级结点。

为何Redis利用
跳表而非红黑树实现SortedSet

比如要搜索 16:

先遍历索引层,当遍历到索引层的13时,发现下一个结点是17,阐明 目标 结点位于这俩结点中心

然后通过down指针,降落 到原始链表层,继续遍历
此时只需再遍历2个结点,即可找到16!

原先单链表布局 需遍历10个结点,如今 只需遍历7个结点即可。可见,加一层索引,所需遍历的结点个数就减少了,搜索 服从 提升 。

为何Redis利用
跳表而非红黑树实现SortedSet

若再加层索引,搜索 服从 是不是更高?于是每两个结点再抽出一个结点到第二级索引。如今 搜索 16,只需遍历6个结点了!

为何Redis利用
跳表而非红黑树实现SortedSet

这里数据量不大,大概 你也没感觉到搜索 服从 ROI高吗。

那数据量就变大一点,现有一64结点链表,给它建立五级的索引。

为何Redis利用
跳表而非红黑树实现SortedSet

原来没有索引时,单链表搜索 62需遍历62个结点!
如今 呢?只需遍历11个!以是 你如今 能领会 到了,当链表长度n很大时,建立索引后,搜索 性能明显 提升 。

这种有多级索引的,可以进步 查询服从 的链表就是迩来 火遍口试 圈的跳表。
作为严谨的程序员,我们又开始好奇了

跳表的搜索 时间复杂度

我们都知道单链表搜索 时间复杂度O(n),那云云 快的跳表呢?

若链表有n个结点,会有多少级索引呢?假设每两个结点抽出一个结点作为上级索引,则:

  • 第一级索引结点个数是n/2
  • 第二级n/4第
  • 三级n/8
  • 第k级就是
    1. n/(2^k)
    复制代码

假设索引有h级,最高级索引有2个结点,可得:n/(2h) = 2[/code]

以是 :h = log2n-1[/code]

若包含原始链表这一层,整个跳表的高度就是log2 n。我们在跳表中查询某个数据的时间 ,假如 每一层都要遍历m个结点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)。

那这个m的值是多少呢?按照前面这种索引布局 ,我们每一级索引都最多只必要 遍历3个结点,也就是说m=3,为什么是3呢?我来表明 一下。

假设我们要查找的数据是x,在第k级索引中,我们遍历到y结点之后,发现x大于y,小于后面的结点z,以是 我们通过y的down指针,从第k级索引降落 到第k-1级索引。在第k-1级索引中,y和z之间只有3个结点(包含y和z),以是 ,我们在K-1级索引中最多只必要 遍历3个结点,依次类推,每一级索引都最多只必要 遍历3个结点。

通过上面的分析,我们得到m=3,以是 在跳表中查询恣意 数据的时间复杂度就是O(logn)。这个查找的时间复杂度跟二分查找是一样的。换句话说,我们实在 是基于单链表实现了二分查找,是不是很神奇?不过,天下没有免费的午餐,这种查询服从 的提升 ,条件 是建立了很多级索引,也就是我们在第6节讲过的空间换时间的计划 思绪 。

跳表是不是很费内存?

由于跳表要存储多级索引,势必比单链表斲丧 更多存储空间。那到底是多少呢?
若原始链表大小为n:

  • 第一级索引大约有n/2个结点
  • 第二级索引大约有n/4个结点
  • 末了 一级2个结点

多级结点数的总和就是:

n/2+n/4+n/8…+8+4+2=n-2[/code]

以是 空间复杂度是O(n)。这个量还是挺大的,可否 再稍微 降低索引占用的内存空间呢?
若每三五个结点才抽取一个到上级索引呢?

为何Redis利用
跳表而非红黑树实现SortedSet

  • 第一级索引必要 大约n/3个结点
  • 第二级索引必要 大约n/9个结点
  • 每往上一级,索引结点个数都除以3

假设最高级索引结点个数为1,总索引结点数:n/3+n/9+n/27+…+9+3+1=n/2[/code]

只管 空间复杂度还是O(n),但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半的索引结点存储空间。

我们大可不必过分在意索引占用的额外空间,实际 开发 中,原始链表中存储的有大概 是很大的对象,而索引结点只需存储关键值和几个指针,无需存储对象,以是 当对象比索引结点大很多时,那索引占用的额外空间可忽略。

插入和删除的时间复杂度

插入

在跳表中插入一个数据,只需O(logn)时间复杂度。
单链表中,一旦定位好要插入的位置,插入的时间复杂度是O(1)。但这里为了保证原始链表中数据的有序性,要先找到插入位置,以是 这个过程中的查找操作比较耗时。

单纯的单链表,需遍历每个结点以找到插入的位置。但跳表搜索 某结点的的时间复杂度是O(logn),以是 搜索 某数据应插入的位置的时间复杂度也是O(logn)。

为何Redis利用
跳表而非红黑树实现SortedSet

删除

假如 这个结点在索引中也有出现,除了要删除原始链表的结点,还要删除索引中的。
由于 单链表删除操作需拿到要删除结点的前驱结点,然后通过指针完成删除。以是 查找要删除结点时,肯定 要获取前驱结点。如果 双向链表,就没这个题目 了。

跳表索引动态更新

当不停往跳表插入数据时,若不更新索引,就大概 出现某2个索引结点之间数据非常多。极端环境 下,跳表还会退化成单链表。

为何Redis利用
跳表而非红黑树实现SortedSet

作为一种动态数据布局 ,我们必要 某种本领 来维护索引与原始链表大小之间的平衡 ,也就是说,假如 链表中结点多了,索引结点就相应地增长 一些,避免复杂度退化,以及查找、插入、删除操作性能降落 。

像红黑树、AVL树如许 的平衡 二叉树通过左右旋保持左右子树的大小平衡 ,而跳表是通过随机函数维护前面提到的“平衡 性”。

往跳表插入数据时,可以选择同时将这个数据插入到部分索引层中。

  1. 那如何选择加入哪些索引层呢?
复制代码

通过一个随机函数决定将这个结点插入到哪几级索引中,比如随机函数天生 了值K,那就把这个结点添加到第一级到第K级这K级索引中。

为何Redis利用
跳表而非红黑树实现SortedSet

  1. 为何Redis要用跳表来实现有序集合,而不是红黑树?
复制代码

Redis中的有序集合支持的核心操作重要 支持:

  • 插入一个数据
  • 删除一个数据
  • 查找一个数据
  • 迭代输出有序序列:以上操作,红黑树也能完成,时间复杂度跟跳表一样。
  • 按照区间查找数据:红黑树的服从 低于跳表。跳表可以做到
    1. O(logn)
    复制代码
    定位区间的出发点 ,然后在原始链表次序 以后 遍历即可。

除了性能,还有别的 缘故起因 :

  • 代码实现比红黑树好懂、好写多了,由于 简单就代表可读性好,不易出错
  • 跳表更机动 ,可通过改变索引构建策略,有用 平衡 实行 服从 和内存斲丧

由于 红黑树比跳表诞生更早,很多编程语言中的Map范例 (比如JDK 的 HashMap)都是通过红黑树实现的。业务开发 时,直接从JDK拿来用,但跳表没有一个现成的实现,只能本身 实现。

跳表的代码实现(Java 版)

数据布局 定义

表中的元素利用 结点来表示,结点的层数在它被插入时随机计算决定(与表中已有结点数目 无关)。

一个i层的结点有i个前向指针(java中利用 结点对象数组forward来表示),索引为从1到i。用MaxLevel来记录跳表的最大层数。

跳表的层数为当前全部 结点中的最大层数(假如 list为空,则层数为1)。

列表头header拥有从1到MaxLevel的前向指针:

  1. public class SkipList<T> {
  2. // 最高层数
  3. private final int MAX_LEVEL;
  4. // 当前层数
  5. private int listLevel;
  6. // 表头
  7. private SkipListNode<T> listHead;
  8. // 表尾
  9. private SkipListNode<T> NIL;
  10. // 生成randomLevel用到的概率值
  11. private final double P;
  12. // 论文里给出的最佳概率值
  13. private static final double OPTIMAL_P = 0.25;
  14. public SkipList() {
  15. // 0.25, 15
  16. this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
  17. }
  18. public SkipList(double probability, int maxLevel) {
  19. P = probability;
  20. MAX_LEVEL = maxLevel;
  21. listLevel = 1;
  22. listHead = new SkipListNode<T>(Integer.MIN_VALUE, null, maxLevel);
  23. NIL = new SkipListNode<T>(Integer.MAX_VALUE, null, maxLevel);
  24. for (int i = listHead.forward.length - 1; i >= 0; i--) {
  25. listHead.forward[i] = NIL;
  26. }
  27. }
  28. // 内部类
  29. class SkipListNode<T> {
  30. int key;
  31. T value;
  32. SkipListNode[] forward;
  33. public SkipListNode(int key, T value, int level) {
  34. this.key = key;
  35. this.value = value;
  36. this.forward = new SkipListNode[level];
  37. }
  38. }
  39. }
复制代码

搜索 算法

按key搜索 ,找到返回该key对应的value,未找到则返回null。

通过遍历forward数组来需找特定的searchKey。假设skip list的key按照从小到大的次序 分列 ,那么从跳表的当前最高层listLevel开始探求 searchKey。在某一层找到一个非小于searchKey的结点后,跳到下一层继续找,直到最底层为止。那么根据末了 搜索 制止 位置的下一个结点,就可以判定 searchKey在不在跳表中。

在跳表中找8的过程:

这里写图片形貌
 

插入和删除算法

都是通过查找与毗连 (search and splice):

这里写图片形貌

维护一个update数组,在搜索 竣事 之后,update保存的是待插入/删除结点在第i层的左侧结点。

插入

若key不存在,则插入该key与对应的value;若key存在,则更新value。

假如 待插入的结点的层数高于跳表的当前层数listLevel,则更新listLevel。

选择待插入结点的层数randomLevel:

randomLevel只依靠 于跳表的最高层数和概率值p。

另一种实现方法为,假如 天生 的randomLevel大于当前跳表的层数listLevel,那么将randomLevel设置为listLevel+1,如许 方便以后的查找,在工程上是可以担当 的,但同时也粉碎 了算法的随机性。

删除

删除特定的key与对应的value。假如 待删除的结点为跳表中层数最高的结点,那么删除之后,要更新listLevel。

  1. public class SkipList<T> {
  2. // 最高层数
  3. private final int MAX_LEVEL;
  4. // 当前层数
  5. private int listLevel;
  6. // 表头
  7. private SkipListNode<T> listHead;
  8. // 表尾
  9. private SkipListNode<T> NIL;
  10. // 生成randomLevel用到的概率值
  11. private final double P;
  12. // 论文里给出的最佳概率值
  13. private static final double OPTIMAL_P = 0.25;
  14. public SkipList() {
  15. // 0.25, 15
  16. this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
  17. }
  18. public SkipList(double probability, int maxLevel) {
  19. P = probability;
  20. MAX_LEVEL = maxLevel;
  21. listLevel = 1;
  22. listHead = new SkipListNode<T>(Integer.MIN_VALUE, null, maxLevel);
  23. NIL = new SkipListNode<T>(Integer.MAX_VALUE, null, maxLevel);
  24. for (int i = listHead.forward.length - 1; i >= 0; i--) {
  25. listHead.forward[i] = NIL;
  26. }
  27. }
  28. // 内部类
  29. class SkipListNode<T> {
  30. int key;
  31. T value;
  32. SkipListNode[] forward;
  33. public SkipListNode(int key, T value, int level) {
  34. this.key = key;
  35. this.value = value;
  36. this.forward = new SkipListNode[level];
  37. }
  38. }
  39. public T search(int searchKey) {
  40. SkipListNode<T> curNode = listHead;
  41. for (int i = listLevel; i > 0; i--) {
  42. while (curNode.forward[i].key < searchKey) {
  43. curNode = curNode.forward[i];
  44. }
  45. }
  46. if (curNode.key == searchKey) {
  47. return curNode.value;
  48. } else {
  49. return null;
  50. }
  51. }
  52. public void insert(int searchKey, T newValue) {
  53. SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
  54. SkipListNode<T> curNode = listHead;
  55. for (int i = listLevel - 1; i >= 0; i--) {
  56. while (curNode.forward[i].key < searchKey) {
  57. curNode = curNode.forward[i];
  58. }
  59. // curNode.key < searchKey <= curNode.forward[i].key
  60. update[i] = curNode;
  61. }
  62. curNode = curNode.forward[0];
  63. if (curNode.key == searchKey) {
  64. curNode.value = newValue;
  65. } else {
  66. int lvl = randomLevel();
  67. if (listLevel < lvl) {
  68. for (int i = listLevel; i < lvl; i++) {
  69. update[i] = listHead;
  70. }
  71. listLevel = lvl;
  72. }
  73. SkipListNode<T> newNode = new SkipListNode<T>(searchKey, newValue, lvl);
  74. for (int i = 0; i < lvl; i++) {
  75. newNode.forward[i] = update[i].forward[i];
  76. update[i].forward[i] = newNode;
  77. }
  78. }
  79. }
  80. public void delete(int searchKey) {
  81. SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
  82. SkipListNode<T> curNode = listHead;
  83. for (int i = listLevel - 1; i >= 0; i--) {
  84. while (curNode.forward[i].key < searchKey) {
  85. curNode = curNode.forward[i];
  86. }
  87. // curNode.key < searchKey <= curNode.forward[i].key
  88. update[i] = curNode;
  89. }
  90. curNode = curNode.forward[0];
  91. if (curNode.key == searchKey) {
  92. for (int i = 0; i < listLevel; i++) {
  93. if (update[i].forward[i] != curNode) {
  94. break;
  95. }
  96. update[i].forward[i] = curNode.forward[i];
  97. }
  98. while (listLevel > 0 && listHead.forward[listLevel - 1] == NIL) {
  99. listLevel--;
  100. }
  101. }
  102. }
  103. private int randomLevel() {
  104. int lvl = 1;
  105. while (lvl < MAX_LEVEL && Math.random() < P) {
  106. lvl++;
  107. }
  108. return lvl;
  109. }
  110. public void print() {
  111. for (int i = listLevel - 1; i >= 0; i--) {
  112. SkipListNode<T> curNode = listHead.forward[i];
  113. while (curNode != NIL) {
  114. System.out.print(curNode.key + "->");
  115. curNode = curNode.forward[i];
  116. }
  117. System.out.println("NIL");
  118. }
  119. }
  120. public static void main(String[] args) {
  121. SkipList<Integer> sl = new SkipList<Integer>();
  122. sl.insert(20, 20);
  123. sl.insert(5, 5);
  124. sl.insert(10, 10);
  125. sl.insert(1, 1);
  126. sl.insert(100, 100);
  127. sl.insert(80, 80);
  128. sl.insert(60, 60);
  129. sl.insert(30, 30);
  130. sl.print();
  131. System.out.println("---");
  132. sl.delete(20);
  133. sl.delete(100);
  134. sl.print();
  135. }
  136. }
复制代码

到此这篇关于为何Redis利用 跳表而非红黑树实现SortedSet的文章就先容 到这了,更多相干 Redis跳表实现SortedSet内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 123457782 | 2021-9-14 03:32:17 | 显示全部楼层
admin楼主的帖子实在是写得太好了。文笔流畅,修辞得体!
回复

使用道具 举报

avatar 秋天一且 | 2021-9-18 08:15:12 | 显示全部楼层
帖子很有深度!
回复

使用道具 举报

avatar 风男人1984 | 2021-9-20 18:12:13 | 显示全部楼层
太邪乎了吧?
回复

使用道具 举报

avatar 名人堂熊猫虞kk | 2021-10-4 10:02:23 | 显示全部楼层
有钱、有房、有车,人人都想!
回复

使用道具 举报

avatar 123457647 | 2021-10-6 23:54:38 | 显示全部楼层
不是惊喜,是惊吓!
回复

使用道具 举报

avatar 信森好帝 | 2021-10-7 15:19:10 | 显示全部楼层
无图无真相!
回复

使用道具 举报

avatar 李松泰李c | 2021-10-8 06:20:53 | 显示全部楼层
我回帖admin楼主给加积分吗?
回复

使用道具 举报

avatar 蠕行者 | 2021-10-9 02:18:12 | 显示全部楼层
看帖不回帖的人就是耍流氓,我回复了!
回复

使用道具 举报

avatar leefengme | 2021-10-10 06:30:13 | 显示全部楼层
我就搞不明白了,看帖回帖能死人么,居然只有我这么认真的在回帖!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则