数据频繁变化的情况下，如何高效检索？( 二 ) _高效检索

O(log n) 这个级别。说到这里，你可能会问，二叉检索树的检索时间代价一定是 O(log n) 吗？其实不一定。
二、二叉检索树的检索空间平衡方案我们先来看一个例子。假设，一个二叉树的每一个节点的左指针都是空的，右子树的值都大于根节点。那么它满足二叉检索树的特性，是一颗二叉检索树。但是，如果我们把左边的空指针忽略，你会发现它其实就是一个单链表！单链表的检索效率如何呢？其实是 O(n)，而不是 O(log n) 。

文章插图
退化成链表的二叉检索树
为什么会出现这样的情况呢？
最根本的原因是，这样的结构造成了检索空间不平衡。在当前节点不满足查询条件的时候，它无法把“一半的数据”过滤掉，而是只能过滤掉当前检索的这个节点。因此无法达到“快速减小查询范围”的目的。
因此，为了提升检索效率，我们应该尽可能地保证二叉检索树的平衡性，让左右子树尽可能差距不要太大。这样无论我们是继续往左边还是右边检索，都可以过滤掉一半左右的数据。
也正是为了解决这个问题，有更多的数据结构被发明了出来。比如：AVL 树（平衡二叉树）和红黑树，其实它们本质上都是二叉检索树，但它们都在保证左右子树差距不要太大上做了特殊的处理，保证了检索效率，让二叉检索树可以被广泛地使用。比如，我们常见的C++ 中的 Set 和 Map 等数据结构，底层就是用红黑树实现的。
这里，我就不再详细介绍 AVL 树和红黑树的具体实现了。为了保证检索效率，我们其实只需要在数据的组织上考虑检索空间的平衡划分就好了，这一点都是一样的。
三、跳表是如何进行二分查找的？除了二叉检索树，有序链表还有其他快速访问中间节点的改造方案吗？我们知道，链表之所以访问中间节点的效率低，就是因为每个节点只存储了下一个节点的指针，要沿着这个指针遍历每个后续节点才能到达中间节点。那如果我们在节点上增加一个指针，指向更远的节点，比如说跳过后一个节点，直接指向后面第二个节点，那么沿着这个指针遍历，是不是遍历速度就翻倍了呢？
同理，如果我们能增加更多的指针，提供不同步长的遍历能力，比如一次跳过 4 个节点，甚至一半的节点，那我们是不是就可以更快速地访问到中间节点了呢？
这当然是可以实现的。我们可以为链表的某些节点增加更多的指针。这些指针都指向不同距离的后续节点。这样一来，链表就具备了更高效的检索能力。这样的数据结构就是跳表（Skip List）。
一个理想的跳表，就是从链表头开始，用多个不同的步长，每隔 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) 。
四、跳表的检索空间平衡方案不知道你有没有注意到，我在前面强调了一个词，那就是“理想的跳表” 。为什么要叫它“理想”的跳表呢？难道在实际情况下，跳表不是这样实现的吗？的确不是。当我们要在跳表中插入元素时，节点之间的间隔距离就被改变了。如果要保证理想链表的每隔 2^n 个节点做一次链接的特性，我们就需要重新修改许多节点的后续指针，这会带来很大的开销。
所以，在实际情况下，我们会在检索性能和修改指针代价之间做一个权衡。为了保证检索性能，我们不需要保证跳表是一个“理想”的平衡状态，只需要保证它在大概率上是平衡的就可以了。因此，当新节点插入时，我们不去修改已有的全部指针，而是仅针对新加入的节点为它建立相应的各级别的跳表指针。具体的操作过程，我们一起来看看。