非线性结构检索——数据频繁变化的情况下高效检索
总览
树结构是如何进行二分查找的？
链表的结构特点意味着它无法提供“随机访问“，那么如果我们要以O(1)的时间代价快速访问到中间节点，就可以和有序数组一样使用二分查找了。
如果我们把中间节点单独拎出来记录，那么第一步操作就是直接访问这个中间节点，然后决定去左还是去右。
这样，一个binary search tree就出现了。尽管有序数组和二叉检索树，在数据结构形态上看起来差异很大，但是在提高检索效率上，它们的核心原理都是一致的：
- 将数据有序化，并且根据数据存储特点进行不同的组织。对于连续存储空间的数组，可以直接存储因为它可以随机访问。对于非连续存储空间的有序链表，不具备随机访问的特性，需要改造此成可以快速访问到中间节点的树状结构。
- 进行检索时，都是通过二分的思想从中间节点开始查起，如果不命中，查询空间缩小一半，然后进行不断的迭代。
那么二叉检索数的检索时间一定是O(log n)吗？
二叉检索树的检索空间平衡方案
二叉树有可能退化成线性的链表，为了解决这个问题，有更多的数据结构被发明了出来。比如：AVL 树（平衡二叉树）和红黑树，其实它们本质上都是二叉检索树，但它们都在保证左右子树差距不要太大上做了特殊的处理，保证了检索效率，让二叉检索树可以被广泛地使用。比如，我们常见的 C++ 中的 Set 和 Map 等数据结构，底层就是用红黑树实现的。
我们只需要在数据的组织上考虑检索空间的平衡划分。
跳表示如何进行二分查找的
链表之所以访问中间节点的效率低，是因为每个节点都只存储了下一个节点的指针，要沿着这个指针遍历每个后续节点才能达到中间节点。那如果我们在节点上增加一个指针，指向更远的节点。如果为链表的某些节点增加更多的指针，这些指针都指向不同距离的后续节点。这种数据结构是就跳表。
一个理想的跳表，就是从链表头开始，用多个不同的步长，每隔 2^n 个节点做一次直接链接（n 取值为 0，1，2……）。跳表中的每个节点都拥有多个不同步长的指针，我们可以在每个节点里，用一个数组 next 来记录这些指针。next 数组的大小就是这个节点的层数，next[0]就是第 0 层的步长为 1 的指针，next[1]就是第 1 层的步长为 2 的指针，next[2]就是第 2 层的步长为 4 的指针，依此类推。你会发现，不同步长的指针，在链表中的分布是非常均匀的，这使得整个链表具有非常平衡的检索结构。
举个例子，当我们要检索 k=a6时，从第一个节点 a1开始，用最大步长的指针开始遍历，直接就可以访问到中间节点 a5。但是，如果沿着这个最大步长指针继续访问下去，下一个节点是大于 k 的 a9，这说明 k 在 a5和 a9之间。那么，我们就在 a5和 a9之间，用小一个级别的步长继续查询。这时候，a5的下一个元素是 a7，a7依然大于 k 的值，因此，我们会继续在 a5和 a7之间，用再小一个级别的步长查找，这样就找到 a6了。这个过程其实就是二分查找。时间代价是 O(log n)。
跳表到底有多块
如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)。
假如一共有 m 级索引，第 m 级的结点数为两个，通过上边我们找到的规律，那么得出 n/(2^m)=2，从而求得 m=log(n)-1。如果加上原始链表，那么整个跳表的高度就是 log(n)。我们在查询跳表的时候，如果每一层都需要遍历 k 个结点，那么最终的时间复杂度就为 O(k*log(n))。
在每一层最多遍历3个节点，所以k=3，时间复杂度还是O(log n)
跳表的检索空间平衡方案
这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们就需要额外再用接近 n 个结点的存储空间。
我们前面都是每两个结点抽出一个结点到上级索引，如果我们每三个结点或五个结点，抽出一个结点到上级索引，是不是就不用那么多索引结点了呢？
第一级索引需要大约 n/3 个结点，第二级需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。
通过等比数列求和，总的索引结点大小就是 n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是 O(n)，但比上面的每两个结点抽一个结点的索引构建方法，要减少一半的索引结点存储空间。
动态的插入和删除
对于跳表来说，查找某个结点的时间复杂度是 O(logn)，所以这里查找某个数应该插入的位置，方法也是类似的，时间复杂度也是 O(logn)。
如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后再通过指针完成删除。所以，在查找要删除的结点时，一点要获取前驱结点。当然，如果我们用双向链表，就不需要考虑这个问题了。
跳表索引动态更新
当我们不停的往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡。也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
红黑树、AVL 树这样的平衡二叉树它们是通过左右旋转的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护平衡性的。我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 k，那我们就将这个结点添加到第一级到第 k 级这个 k 级索引中。
首先，我们需要确认新加入的节点需要具有几层的指针。我们通过随机函数来生成层数，比如说，我们可以写一个函数 RandomLevel()，以 (1/2)^n 的概率决定是否生成第 n 层。这样，通过简单的随机生成指针层数的方式，我们就可以保证指针的分布，在大概率上是平衡的。
randomLevel()
level := 1
// random()返回一个[0...1)的随机数
while random() < p and level < MaxLevel do
level := level + 1
return level
根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析如下：
- 节点层数至少为1。而大于1的节点层数，满足一个概率分布。
- 节点层数恰好等于1的概率为1-p。
- 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
- 节点层数大于等于3的概率为p2，而节点层数恰好等于3的概率为p2(1-p)。
- 节点层数大于等于4的概率为p3，而节点层数恰好等于4的概率为p3(1-p)。
- ……
现在很容易计算出：
- 当p=1/2时，每个节点所包含的平均指针数目为2；
- 当p=1/4时，每个节点所包含的平均指针数目为1.33。这也是Redis里的skiplist实现在空间上的开销。
具体跳表的时间复杂度计算：
Skip Lists: A Probabilistic Alternative to Balanced Trees –William Pugh
在确认了新节点的层数 n 以后，接下来，我们需要将新节点和前后的节点连接起来，也就是为每一层的指针建立前后连接关系。其实每一层的指针链接，你都可以看作是一个独立的单链表的修改，因此我们只需要用单链表插入节点的方式完成指针连接即可。
- 确认k应该插入到a6和a7两个节点之间。
- 生成随机层数，如果随机出的层数为2，那需要修改第0层和第1层的指针关系。
- 对于第0层，k插入a6和a7之间，只需要修改a6和a7的第0层指针。
- 对于第1层，k插入a5和a7之间，只需要修改a5和a7的第1层指针。
Redis里的跳表
为什么Redis要用跳表而不是红黑树？其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表一样。但是按照区间来查找这个操作，红黑树的效率没有跳表高。对于按照区间查找这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点。
- skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。范围查找有利
- 在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
- 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。插入删除简单
- 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。内存占用比红黑树少
- 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。红黑树单个key更快
- 从算法实现难度上来比较，skiplist比平衡树要简单得多。
序数组的优点：
- 有序数据占用的内存空间小于调表
- 有序数组的读取操作能保持在很稳定的时间复杂度，而调表并不能
- 因为数组存储空间是连续的，可以利用内存的局部性原理加快查询