You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

119 lines
15 KiB
Markdown

2 years ago
# 02 | 非线性结构检索:数据频繁变化的情况下,如何高效检索?
你好,我是陈东。
当我们在电脑中查找文件的时候,我们一般习惯先打开相应的磁盘,再打开文件夹以及子文件夹,最后找到我们需要的文件。这其实就是一个检索路径。如果把所有的文件展开,这个查找路径其实是一个树状结构,也就是一个非线性结构,而不是一个所有文件平铺排列的线性结构。
![](https://static001.geekbang.org/resource/image/18/46/1859310bd112d5479eac9c097db8b946.jpeg)
树状结构:文件组织例子
我们都知道,有层次的文件组织肯定比散乱平铺的文件更容易找到。这样熟悉的一个场景,是不是会给你一个启发:对于零散的数据,非线性的树状结构是否可以帮我们提高检索效率呢?
另一方面,我们也知道,在数据频繁更新的场景中,连续存储的有序数组并不是最合适的存储方案。因为数组为了保持有序必须不停地重建和排序,系统检索性能就会急剧下降。但是,非连续存储的有序链表倒是具有高效插入新数据的能力。因此,我们能否结合上面的例子,使用非线性的树状结构来改造有序链表,让链表也具有二分查找的能力呢?今天,我们就来讨论一下这个问题。
## 树结构是如何进行二分查找的?
上一讲我们讲了因为链表并不具备“随机访问”的特点所以二分查找无法生效。当链表想要访问中间的元素时我们必须从链表头开始沿着指针一步一步遍历需要遍历一半的节点才能到达中间节点时间代价是O(n/2)。而有序数组由于可以“随机访问”因此只需要O(1)的时间代价就可以访问到中间节点了。
那如果我们能在链表中以O(1)的时间代价快速访问到中间节点,是不是就可以和有序数组一样使用二分查找了?你先想想看该怎么做,然后我们一起来试着改造一下。
![](https://static001.geekbang.org/resource/image/2c/ca/2c61d26ed919411dd9be1a94cefb30ca.jpg)
直接记录和访问中间节点
既然我们希望能以O(1)的时间代价访问中间节点那将这个节点直接记录下来是不是就可以了因此如果我们把中间节点M拎出来单独记录那我们的第一步操作就是直接访问这个中间节点然后判断这个节点和要查找的元素是否相等。如果相等则返回查询结果。如果节点元素大于要查找的元素那我们就到左边的部分继续查找反之则在右边部分继续查找。
对于左边或者右边的部分我们可以将它们视为两个独立的子链表依然沿用这个逻辑。如果想用O(1)的时间代价就能访问这两个子链表的中间节点我们就应该把左边的中间节点L和右边的中间节点R单独拎出来记录。
并且由于我们是在访问完了M节点以后才决定接下来该去访问左边的L还是右边的R。因此我们需要将L和MR和M连接起来。我们可以让M带有两个指针一个左指针指向L一个右指针指向R。这样在访问M以后一旦发现M不是我们要查找的节点那么我们接下来就可以通过指针快速访问到L或者R了。
![](https://static001.geekbang.org/resource/image/d2/f4/d274bfacd98b00d82746cfeb838ec1f4.jpeg)
将M节点改为带两个指针指向L节点和R节点
对于其余的节点,我们也可以进行同样的处理。下面这个结构,你是不是很熟悉?没错,这就是我们常见的二叉树。你可以再观察一下,这个二叉树和普通的二叉树有什么不一样?
![](https://static001.geekbang.org/resource/image/bf/bb/bf8df69285c21e28b493bd2f7a0c1abb.jpeg)
二叉检索树结构
没错这个二叉树是有序的。它的左子树的所有节点的值都小于根节点同时右子树所有节点的值都大于等于根节点。这样的有序结构使得它能使用二分查找算法快速地过滤掉一半的数据。具备了这样特点的二叉树就是二叉检索树Binary Search Tree或者叫二叉排序树Binary Sorted Tree
讲到这里,不知道你有没有发现,**尽管有序数组和二叉检索树,在数据结构形态上看起来差异很大,但是在提高检索效率上,它们的核心原理都是一致的。**那么,它们是如何提高检索效率的呢?核心原理又一致在哪里呢?接下来,我们就从两个主要方面来看。
* 将数据有序化,并且根据数据存储的特点进行不同的组织。对于连续存储空间的数组而言,由于它具有“随机访问”的特性,因此直接存储即可;对于非连续存储空间的有序链表而言,由于它不具备“随机访问”的特性,因此,需要将它改造为可以快速访问到中间节点的树状结构。
* 在进行检索的时候它们都是通过二分查找的思想从中间节点开始查起。如果不命中会快速缩小一半的查询空间。这样不停迭代的查询方式让检索的时间代价能达到O(log n)这个级别。
说到这里你可能会问二叉检索树的检索时间代价一定是O(log n)吗?其实不一定。
## 二叉检索树的检索空间平衡方案
我们先来看一个例子。假设一个二叉树的每一个节点的左指针都是空的右子树的值都大于根节点。那么它满足二叉检索树的特性是一颗二叉检索树。但是如果我们把左边的空指针忽略你会发现它其实就是一个单链表单链表的检索效率如何呢其实是O(n)而不是O(log n)。
![](https://static001.geekbang.org/resource/image/a9/eb/a9f61debcc5a5502f810b1c84ca682eb.jpeg)
退化成链表的二叉检索树
为什么会出现这样的情况呢?
**最根本的原因是,这样的结构造成了检索空间不平衡。在当前节点不满足查询条件的时候,它无法把“一半的数据”过滤掉,而是只能过滤掉当前检索的这个节点。因此无法达到“快速减小查询范围”的目的。**
因此,为了提升检索效率,我们应该尽可能地保证二叉检索树的平衡性,让左右子树尽可能差距不要太大。这样无论我们是继续往左边还是右边检索,都可以过滤掉一半左右的数据。
也正是为了解决这个问题有更多的数据结构被发明了出来。比如AVL树平衡二叉树和红黑树其实它们本质上都是二叉检索树但它们都在保证左右子树差距不要太大上做了特殊的处理保证了检索效率让二叉检索树可以被广泛地使用。比如我们常见的C++中的Set和Map等数据结构底层就是用红黑树实现的。
这里我就不再详细介绍AVL树和红黑树的具体实现了。为了保证检索效率我们其实只需要在数据的组织上考虑检索空间的平衡划分就好了这一点都是一样的。
## 跳表是如何进行二分查找的?
除了二叉检索树,有序链表还有其他快速访问中间节点的改造方案吗?我们知道,链表之所以访问中间节点的效率低,就是因为每个节点只存储了下一个节点的指针,要沿着这个指针遍历每个后续节点才能到达中间节点。那如果我们在节点上增加一个指针,指向更远的节点,比如说跳过后一个节点,直接指向后面第二个节点,那么沿着这个指针遍历,是不是遍历速度就翻倍了呢?
同理如果我们能增加更多的指针提供不同步长的遍历能力比如一次跳过4个节点甚至一半的节点那我们是不是就可以更快速地访问到中间节点了呢
这当然是可以实现的。我们可以为链表的某些节点增加更多的指针。这些指针都指向不同距离的后续节点。这样一来,链表就具备了更高效的检索能力。这样的数据结构就是**跳表**Skip List
一个理想的跳表就是从链表头开始用多个不同的步长每隔2^n个节点做一次直接链接n取值为012……。跳表中的每个节点都拥有多个不同步长的指针我们可以在每个节点里用一个数组next来记录这些指针。next数组的大小就是这个节点的层数next\[0\]就是第0层的步长为1的指针next\[1\]就是第1层的步长为2的指针next\[2\]就是第2层的步长为4的指针依此类推。你会发现不同步长的指针在链表中的分布是非常均匀的这使得整个链表具有非常平衡的检索结构。
![](https://static001.geekbang.org/resource/image/bb/77/bbae24216d975a014b6112dbce45ae77.jpg)
理想的跳表
举个例子当我们要检索k=a6时从第一个节点a1开始用最大步长的指针开始遍历直接就可以访问到中间节点a5。但是如果沿着这个最大步长指针继续访问下去下一个节点是大于k的a9这说明k在a5和a9之间。那么我们就在a5和a9之间用小一个级别的步长继续查询。这时候a5的下一个元素是a7a7依然大于k的值因此我们会继续在a5和a7之间用再小一个级别的步长查找这样就找到a6了。这个过程其实就是二分查找。时间代价是O(log n)。
## 跳表的检索空间平衡方案
不知道你有没有注意到我在前面强调了一个词那就是“理想的跳表”。为什么要叫它“理想”的跳表呢难道在实际情况下跳表不是这样实现的吗的确不是。当我们要在跳表中插入元素时节点之间的间隔距离就被改变了。如果要保证理想链表的每隔2^n个节点做一次链接的特性我们就需要重新修改许多节点的后续指针这会带来很大的开销。
所以,在实际情况下,我们会在检索性能和修改指针代价之间做一个权衡。为了保证检索性能,我们不需要保证跳表是一个“理想”的平衡状态,只需要保证它在大概率上是平衡的就可以了。因此,当新节点插入时,我们不去修改已有的全部指针,而是仅针对新加入的节点为它建立相应的各级别的跳表指针。具体的操作过程,我们一起来看看。
首先我们需要确认新加入的节点需要具有几层的指针。我们通过随机函数来生成层数比如说我们可以写一个函数RandomLevel(),以(1/2)^n的概率决定是否生成第n层。这样通过简单的随机生成指针层数的方式我们就可以保证指针的分布在大概率上是平衡的。
在确认了新节点的层数n以后接下来我们需要将新节点和前后的节点连接起来也就是为每一层的指针建立前后连接关系。其实每一层的指针链接你都可以看作是一个独立的单链表的修改因此我们只需要用单链表插入节点的方式完成指针连接即可。
这么说,可能你理解起来不是很直观,接下来,我通过一个具体的例子进一步给你解释一下。
我们要在一个最高有3层指针的跳表中插入一个新元素k这个跳表的结构如下图所示。
![](https://static001.geekbang.org/resource/image/dd/42/dd4a8d2cfc40d4825dc5951ddcce2442.jpg)
假设我们通过跳表的检索已经确认了k应该插入到a6和a7两个节点之间。那接下来我们要先为新节点随机生成一个层数。假设生成的层数为2那我们就要修改第0层和第1层的指针关系。对于第0层的链表k需要插入到a6和a7之间我们只需要修改a6和a7的第0层指针对于第1层的链表k需要插入到a5和a7之间我们只需要修改a5和a7的第1层指针。这样我们就完成了将k插入到跳表中的动作。
通过这样一种方式我们可以大大减少修改指针的代价。当然由于新加入节点的层数是随机生成的因此在节点数目较少的情况下如果指针分布的不合理检索性能依然可能不高。但是当节点数较多的时候指针会趋向均匀分布查找空间会比较平衡检索性能会趋向于理想跳表的检索效率接近O(log n)。
因此相比于复杂的平衡二叉检索树如红黑树跳表用一种更简单的方式实现了检索空间的平衡。并且由于跳表保持了链表顺序遍历的能力在需要遍历功能的场景中跳表会比红黑树用起来更方便。这也就是为什么在Redis这样的系统中我们经常会利用跳表来代替红黑树作为底层的数据结构。
## 重点回顾
好了,关于非线性结构的检索技术,我们就先讲到这里。我们一起回顾一下今天的重点内容。
首先,对于数据频繁变化的应用场景,有序数组并不是最适合的解决方案。我们一般要考虑采用非连续存储的数据结构来灵活调整。同时,为了提高检索效率,我们还要采取合理的组织方式,让这些非连续存储的数据结构能够使用二分查找算法。
数据组织的方式有两种一种是二叉检索树。一个平衡的二叉检索树使用二分查找的检索效率是O(log n)但如果我们不做额外的平衡控制的话二叉检索树的检索性能最差会退化到O(n)也就和单链表一样了。所以AVL树和红黑树这样平衡性更强的二叉检索树在实际工作中应用更多。
除了树结构以外另一种数据组织方式是跳表。跳表也具备二分查找的能力理想跳表的检索效率是O(log n)。为了保证跳表的检索空间平衡跳表为每个节点随机生成层级这样的实现方式比AVL树和红黑树更简单。
无论是二叉检索树还是跳表它们都是通过将数据进行合理组织然后尽可能地平衡划分检索空间使得我们能采用二分查找的思路快速地缩减查找范围达到O(log n)的检索效率。
除此之外,我们还能发现,当我们从实际问题出发,去思考每个数据结构的特点以及解决方案时,我们就会更好地理解一些高级数据结构和算法的来龙去脉,从而达到更深入地理解和吸收知识的目的。并且,这种思考方式,会在不知不觉中提升你的设计能力以及解决问题的能力。
## 课堂讨论
今天的内容比较多,你可以结合我留的课堂讨论题,加深理解。
二叉检索树和跳表都能做到O(log n)的查询时间代价还拥有灵活的调整能力并且调整代价也是O(log n)包括了寻找插入位置的时间代价。而有序数组的查询时间代价也是O(log n)调整代价是O(n),那这是不是意味着二叉检索树或者跳表可以用来替代有序数组呢?有序数组自己的优势又是什么呢?
欢迎在留言区畅所欲言,说出你的思考过程和最终答案。如果有收获,也欢迎把这篇文章分享给你的朋友。