面试官：为何Redis使用跳表而非红黑树实现SortedSet？

独坐君王位

明白跳表（Skip List）是正在看闭于Redis的书的工夫，Redis中的有序汇合利用了跳表数据构造。接着便查了一些专客，去进修一下跳表。后背会利用Java代码去俭朴完成跳表。
甚么是跳表

跳表由William Pugh创造，他正在论文《Skip lists: a probabilistic alternative to balanced trees》中具体引见了跳表的数据构造战插进删除等操纵，论文是那么引见跳表的：

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个结面。
若每第2^i 个结面皆有一个指背间距为 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 为什么没有挑选白乌树去完成呢？

跳表的意义终究正在于那边？

单链表即使存储的数占有序，若搜刮某数据，也只能从头至尾遍历，搜刮服从很低，平均工夫庞大度是O(n)。
寻求极致的法式员便开端念了，那那该怎样进步链表构造的搜刮服从呢？
若以下图，对链表成立一级“索引”，每两个结面提与一个结面到上一级，把抽出去的那级叫做索引或索引层。图中的down表示down指针，指背下一级结面。

好比要搜刮16：

先遍历索引层，当遍历到索引层的13时，发明下一个结面是17，分析目标结面位于那俩结面中心
然后经由过程down指针，降落到本初链表层，担当遍历
此时只需再遍历2个结面，便可找到16！

本来单链表构造需遍历10个结面，如今只需遍历7个结面便可。可睹，减一层索引，所需遍历的结面个数便裁减了，搜刮服从提拔。

若再减层索引，搜刮服从是否是更下？因而每两个结面再抽出一个结面到第两级索引。如今搜刮16，只需遍历6个结面了！

那里数据量没有年夜，能够您也出觉得到搜刮服从ROI下吗。
那数据量便变年夜一面，现有一64结面链表，给它成立五级的索引。

本来出有索引时，单链表搜刮62需遍历62个结面！
如今呢？只需遍历11个！以是您如今能领会到了，当链表少度n很年夜时，成立索引后，搜刮机能明显提拔。
这类有多级索引的，能够进步查询服从的链表便是近来水遍面试圈的跳表。
做为松散的法式员，我们又开端猎奇了
跳表的搜刮工夫庞大度

我们皆明白单链表搜刮工夫庞大度O(n)，那云云快的跳表呢？
若链表有n个结面，会有几级索引呢？假定每两个结面抽出一个结面做为下级索引，则：

第一级索引结面个数是n/2
第两级n/4
第三级n/8
…
第k级便是n/(2^k)

假定索引有h级，第一流索引有2个结面，可得：

n/(2h) = 2

复造代码

以是：

h = log2n-1

复造代码

若包罗本初链表那一层，全部跳表的下度便是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

复造代码

以是空间庞大度是O(n)。那个量仍是挺年夜的，可否再细微低落索引占用的内乱存空间呢？
若每三五个结面才抽与一个到下级索引呢？

第一级索引需求估计n/3个结面
第两级索引需求估计n/9个结面
每往上一级，索引结面个数皆除以3

假定第一流索引结面个数为1，总索引结面数：

n/3+n/9+n/27+…+9+3+1=n/2

复造代码

虽然空间庞大度仍是O(n)，但比上里的每两个结面抽一个结面的索引构建办法，要裁减了一半的索引结面存储空间。
我们年夜可没必要过火在乎索引占用的分外空间，实践开辟中，本初链表中存储的有多是很年夜的工具，而索引结面只需存储枢纽值战几个指针，无需存储工具，以是当工具比索引结面年夜许多时，那索引占用的分外空间可疏忽。
插进战删除的工夫庞大度

插进

正在跳表中插进一个数据，只需O(logn)工夫庞大度。
单链表中，一旦定位好要插进的地位，插进的工夫庞大度是O(1)。但那里为了包管本初链表中数据的有序性，要先找到插进地位，以是那个过程当中的查找操纵比力耗时。
纯真的单链表，需遍历每一个结面以找到插进的地位。但跳表搜刮某结面的的工夫庞大度是O(logn)，以是搜刮某数据应插进的地位的工夫庞大度也是O(logn)。

删除

假如那个结面正在索引中也有呈现，除要删除本初链表的结面，借要删除索引中的。
由于单链表删除操纵需拿到要删除结面的先驱结面，然后经由过程指针完成删除。以是查找要删除结面时，必然要获得先驱结面。如果单背链表，便出那个成绩了。
跳表索哄动态更新

当不断往跳表插进数据时，若没有更新索引，便可能呈现某2个索引结面之间数据十分多。极度状况下，跳表借会退化成单链表。

做为一种静态数据构造，我们需求某种本领去保护索引取本初链表巨细之间的平衡，也便是道，假如链表中结面多了，索引结面便响应天增长一些，避免庞大度退化，和查找、插进、删除操纵机能降落。
像白乌树、AVL树如许的平衡两叉树经由过程阁下旋连结阁下子树的巨细平衡，而跳表是经由过程随机函数保护前里提到的“平衡性”。
往跳表插进数据时，能够挑选同时将那个数据插进到部分索引层中。

那怎样挑选参加哪些索引层呢？

经由过程一个随机函数决议将那个结面插进到哪几级索引中，好比随机函数天生了值K，那便把那个结面增加到第一级到第K级那K级索引中。

为什么Redis要用跳表去完成有序汇合，而没有是白乌树？

Redis中的有序汇合撑持的核心操纵次要撑持：

插进一个数据
删除一个数据
查找一个数据
迭代输出有序序列
以上操纵，白乌树也能完成，工夫庞大度跟跳表一样。
根据区间查找数据
白乌树的服从低于跳表。跳表能够做到O(logn)定位区间的出发点，然后正在本初链表挨次今后遍历便可。

除机能，另有别的缘故原由：

代码完成比白乌树好懂、好写多了，由于俭朴便代表可读性好，不容易堕落
跳表更灵敏，可经由过程改动索引构建战略，有用平衡施行服从战内乱存耗损

由于白乌树比跳表降生更早，许多编程言语中的Map范例（好比JDK 的 HashMap）皆是经由过程白乌树完成的。营业开辟时，间接从JDK拿去用，但跳表出有一个现成的完成，只能本人完成。
跳表的代码完成（Java 版）

数据构造界说

表中的元素利用结面去表示，结面的层数正在它被插进时随机计较决议（取表中已有结面数量无闭）。
一个i层的结面有i个前背指针（java中利用结面工具数组forward去表示），索引为从1到i。用MaxLevel去记载跳表的最年夜层数。
跳表的层数为当前局部结面中的最年夜层数（假如list为空，则层数为1）。
列表头header具有从1到MaxLevel的前背指针：

public class SkipList<T> {
// 最下层数
private final int MAX_LEVEL;
// 当前层数
private int listLevel;
// 表头
private SkipListNode<T> listHead;
// 表尾
private SkipListNode<T> NIL;
// 天生randomLevel用到的几率值
private final double P;
// 论文里给出的最好几率值
private static final double OPTIMAL_P = 0.25;
public SkipList() {
// 0.25, 15
this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
}
public SkipList(double probability, int maxLevel) {
P = probability;
MAX_LEVEL = maxLevel;
listLevel = 1;
listHead = new SkipListNode<T>(Integer.MIN_VALUE, null, maxLevel);
NIL = new SkipListNode<T>(Integer.MAX_VALUE, null, maxLevel);
for (int i = listHead.forward.length - 1; i >= 0; i--) {
listHead.forward[i] = NIL;
}
}
// 内乱部类
class SkipListNode<T> {
int key;
T value;
SkipListNode[] forward;
public SkipListNode(int key, T value, int level) {
this.key = key;
this.value = value;
this.forward = new SkipListNode[level];
}
}
}

复造代码

搜刮算法

按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。
[code]public class SkipList { // 最下层数 private final int MAX_LEVEL; // 当前层数 private int listLevel; // 表头 private SkipListNode listHead; // 表尾 private SkipListNode NIL; // 天生randomLevel用到的几率值 private final double P; // 论文里给出的最好几率值 private static final double OPTIMAL_P = 0.25; public SkipList() { // 0.25, 15 this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1); } public SkipList(double probability, int maxLevel) { P = probability; MAX_LEVEL = maxLevel; listLevel = 1; listHead = new SkipListNode(Integer.MIN_VALUE, null, maxLevel); NIL = new SkipListNode(Integer.MAX_VALUE, null, maxLevel); for (int i = listHead.forward.length - 1; i >= 0; i--) { listHead.forward = NIL; } } // 内乱部类 class SkipListNode { int key; T value; SkipListNode[] forward; public SkipListNode(int key, T value, int level) { this.key = key; this.value = value; this.forward = new SkipListNode[level]; } } public T search(int searchKey) { SkipListNode curNode = listHead; for (int i = listLevel; i > 0; i--) { while (curNode.forward.key </span searchKeyspan class="token punctuation")/span span class="token punctuation"{/span curNode span class="token operator"=/span curNodespan class="token punctuation"./spanforwardspan class="token punctuation"[/spanispan class="token punctuation"]/spanspan class="token punctuation";/span span class="token punctuation"}/span span class="token punctuation"}/span span class="token keyword"if/span span class="token punctuation"(/spancurNodespan class="token punctuation"./spankey span class="token operator"==/span searchKeyspan class="token punctuation")/span span class="token punctuation"{/span span class="token keyword"return/span curNodespan class="token punctuation"./spanvaluespan class="token punctuation";/span span class="token punctuation"}/span span class="token keyword"else/span span class="token punctuation"{/span span class="token keyword"return/span span class="token keyword"null/spanspan class="token punctuation";/span span class="token punctuation"}/span span class="token punctuation"}/span span class="token keyword"public/span span class="token keyword"void/span span class="token function"insert/spanspan class="token punctuation"(/spanspan class="token keyword"int/span searchKeyspan class="token punctuation",/span span class="token class-name"T/span newValuespan class="token punctuation")/span span class="token punctuation"{/span span class="token class-name"SkipListNode/spanspan class="token generics"span class="token punctuation"/spanspan class="token class-name"T/spanspan class="token punctuation"/span/spanspan class="token punctuation"[/spanspan class="token punctuation"]/span update span class="token operator"=/span span class="token keyword"new/span span class="token class-name"SkipListNode/spanspan class="token punctuation"[/spanMAX_LEVELspan class="token punctuation"]/spanspan class="token punctuation";/span span class="token class-name"SkipListNode/spanspan class="token generics"span class="token punctuation"/spanspan class="token class-name"T/spanspan class="token punctuation"/span/span curNode span class="token operator"=/span listHeadspan class="token punctuation";/span span class="token keyword"for/span span class="token punctuation"(/spanspan class="token keyword"int/span i span class="token operator"=/span listLevel span class="token operator"-/span span class="token number"1/spanspan class="token punctuation";/span i span class="token operator">= 0; i--) { while (curNode.forward.key <span class="token operator">

面试官：为何Redis使用跳表而非红黑树实现SortedSet？

浏览过的版块