关于数据结构:数据结构-跳表

有序的数组能够应用二分查找的办法疾速检索一个数据，然而链表没有方法应用二分查找。

对于一个单向链表来说，即便链表中存储的是有序的数据，但如果想要从中查找某个数据时，也只能从头到尾遍历链表，其工夫复杂度是 $O(n)$。

为了进步链表的查问效率，使其反对相似“二分查找”的办法，对链表进行多层次扩大，这样的数据结构就是跳表。跳表对标的是均衡树，是一种晋升链表插入、删除、搜寻效率的数据结构。

首先，跳表处理的是有序的链表，个别应用双向链表更加不便。

而后，每两个结点提取一个结点到上一级，提取的这一层被称作为 索引层。

这时候，当想要查找 19 这个数字，能够先从索引层开始查找；当达到 17 时，发现下一个结点存储 21 这个数字，则能够确定，想要查找的 19 必定是在 17 到 21 之间；这时候能够转到下一层（原始链表）中查找，疾速从 17 开始检索，很快就能够查找出 19 这个数字。

退出一层索引之后，查找一个结点须要遍历的结点个数缩小了，也就是查找效率进步了。实际上，个别会新增多层索引，领有多层索引的跳表，查找一个结点须要遍历的结点个数将再次缩小。

这种链表加多层索引的构造，就是跳表。

为了不便对跳表的效率做剖析，在这里设定一个常见的跳表类型。

假如每两个结点会抽出一个结点作为上一级索引的结点，那第一级的索引个数大概就是 $\frac{n}{2}$，第二级的索引个数大概就是 $\frac{n}{4}$，以此类推，第 k 个索引的结点个数是第 k-1 个索引的结点个数的 $\frac{1}{2}$，那么，第 k 个索引的结点个数就是 $\frac{n}{2^k}$。

假如索引总共有 h 级，最高级的索引有 2 个结点，应用公式 $\frac{n}{2^h} = 2$ 进行反推，能够计算得出 $h = \log_2 n – 1$，如果是蕴含原始链表那一级，跳表的高度就是 $\log_2 n$ 级。

如果想要从跳表中查问某个数据时，每层都会遍历 m 个结点，那么，在跳表中查问一个数据的工夫复杂度就是 $O(m \log n)$。

从下面图中可知，在每一级索引中最多只须要遍历 3 个结点，其实就能够看作是 m = 3。

理论就是，在最高级索引时最多遍历 3 个结点，当须要在下一级索引中持续检索时，算上前后两个当做范畴的结点也只有 3 个，因而，在每一级索引最多只须要遍历 3 个结点。

如果细究的话，m 的值与抽取索引值的距离有间接关系，然而只是计算工夫复杂度的话，能够将 m 值看作是一个常数。

因而，在跳表中做检索的工夫复杂度是 $O(\log n)$。

同样的，假如每两个结点会抽出一个结点作为上一级索引的结点，那第一级的索引个数大概就是 $\frac{n}{2}$，第二级的索引个数大概就是 $\frac{n}{4}$，顺次类推，最终索引占用的空间将是 $\frac{n}{2} + \frac{n}{4} + … + 4 + 2 = n – 2$。

所以，跳表的空间复杂度是 $O(n)$。

实际上，跳表是一种应用空间换工夫的数据结构，以减少索引的形式，进步检索数据的效率。因而，跳表会比一般链表消耗更多内存进行数据存储。

在上述剖析跳表的工夫复杂度和空间复杂度时，都是以每两个结点抽出一个结点作为上一级索引的结点。

实际上，也能够应用 3 个结点或 4 个结点甚至更多结点做距离。当然，以不同个数结点做距离时，检索效率和内存占用都会有些不一样。

假如以 3 个结点做距离，占用的空间会有所升高，在这个跳表上做检索操作时，检索的效率也会有一些升高。

因为在每一级索引检索的最多结点个数将从 2 个变成 3 个，跳表的高度是 $\log_3 n$ 级，最终占用的空间将是 $\frac{n}{3} + \frac{n}{9} + … + 3 + 1 = \frac{n}{2}$。

在实践上，以 3 个结点做距离的跳表与以 2 个结点做距离的跳表的工夫复杂度和空间复杂度都是一样的。然而，实际操作时，以 3 个结点做距离的跳表的空间占用会比以 2 个结点做距离的跳表更优一些。

实际上，在软件开发中，不用太在意索引占用的额定空间。尽管原始链表中存储的有可能是很大的对象，但索引结点能够只存储要害值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额定空间就能够疏忽了。

下面了解的跳表都是动态的，理论开发中，跳表在新增、删除结点时须要做动静解决，否则容易导致检索效率升高。

如上图所示，如果频繁插入结点，而没有对索引层做动静解决，很容易呈现不满足一开始设定的跳表规定。

删除链表的结点时也是同样情理，如果删除结点而没有更新索引层，索引层容易呈现已被删除的脏结点。

比拟容易了解的办法就是重建索引，当每次插入、删除结点的时候，把整个跳表的所有索引层删除重建。

然而这种办法会升高插入结点时的效率，已知跳表的空间复杂度是 $O(n)$，也能够推断出重建跳表索引层的工夫简单至多是 $O(n)$。

也就是说，应用重建索引的形式，跳表插入结点消耗工夫将会直线回升。

与重建索引相比，随机索引的效率会更高一些，像 Redis 实现 SortedSet 底层用的跳表就是应用随机索引的形式进行动静解决。

这里的做法是通过应用一个随机函数，来决定这个结点插入时，是否须要插入到索引层、以及插入到第几级索引。

一般来说，通过随机函数失去的数据都是比拟平均的，也示意最终失去的跳表索引层也是比拟平均，而且数据量越大，索引层越是平均。

先设定索引的生成规定：从原始链表中随机抉择 $\frac{1}{2}$ 个结点作为一级索引，从一级索引中随机抉择 $\frac{1}{4}$ 个结点作为二级索引，以此类推，始终到最顶层索引。这时候就须要依据这个规定实现所需的随机函数，并且是每次插入结点的时候，都通过随机函数判断这个结点须要插入到几级索引。

以下是 Redis 源码当中应用到的随机函数：

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

这个随机函数会随机生成 1 到索引最高层数之间的一个数字，该办法有 $\frac{1}{2}$ 的概率返回 1、有 $\frac{1}{4}$ 的概率返回 2、有 $\frac{1}{8}$ 的概率返回 3、以此类推。其中 1 示意不须要生成索引，2 示意须要生成一级索引，3 示意须要生成二级索引，以此类推。

为什么不是返回 1 时生成一级索引呢？这是因为，在生成比一级索引更高层级的索引时，都会向下生成索引，即如果随机函数返回 3，则会给这个结点同时生成二级索引和一级索引。这样，如果返回 1 时生成一级索引则会呈现生成一级索引的概率为 100%。

应用随机索引办法的跳表，插入结点的工夫复杂度与跳表索引的高度雷同，最终工夫复杂度降到 $O(\log n)$，而不是重建索引的 $O(n)$。

与均衡查找树相比，跳表领有以下劣势：

跳表的底层原始链表反对范畴查问
跳表绝对简略，更容易应用代码实现
跳表更加灵便，能够通过扭转索引构建策略，无效均衡执行效率和内存耗费

针对上述的第 1 点，反对范畴查问的 B+ 树更实用于磁盘，跳表次要用于内存中读取数据。

LSM-Tree 全称是 Log Structured-Merge Tree，其中文名是日志构造的合并树，是一种分层的、有序的、基于硬盘的数据结构。

LSM-Tree 的外围思路是，首先写入数据到内存中，不须要每次有数据更新时就必须将数据写入到磁盘中，内存达到阈值之后，再应用归并排序的形式将内存中的数据合并追加到磁盘队尾。

因为跳表恰好就是人造有序的，所以在 flush 的时候效率很高，通常基于 LSM-Tree 构造的数据库在内存局部都会抉择跳表这种数据结构。

HBase 的 MemStore 外部基于 LSM-Tree 实现，Google 开源的 LevelDB 以及 Facebook 基于 LevelDB 优化的 RocksDB 外部的 MemTable 都是基于 LSM-Tree 实现，它们都应用到了跳表这一构造。

关于数据结构:数据结构-跳表

简介

效率剖析

工夫复杂度

空间复杂度

结点距离

动静插入和删除

重建索引

随机索引

利用场景

跳表和均衡查找树

LSM-Tree