字节面试：谈谈索引为什么能提高查询性能？

怼烎@ 2022-12-26 00:59 34阅读 0赞

--------------------

## 前言 ##

昨天，有个女孩子问我提高数据库查询性能有什么立竿见影的好方法？

这简直是一道送分题，我自豪且略带鄙夷的说，当然是加「索引」了。

她又不紧不慢的问，索引为什么就能提高查询性能。

这还用问，索引就像一本书的目录，用目录查当然很快。

她失望地摇了摇头，你说的只是一个类比，可**为什么通过目录就能提高查询速度呢**。

唉，对啊，通过书目可以快速查询，这只是一个现象，真正原因到底是什么呢。

那女孩看着诧异且表情僵硬的我，满意而又意味深长的笑笑：原来你这个男程序员也不会，看来我还得靠自己研究了。

哎，熬夜又要憔悴了我这该死的美貌。

来自同行的羞辱，是可忍孰不可忍？！

于是，我踏上了数据库索引学习的不归路，原来数据库索引使用了一种叫 B+ 树的古老数据结构，当然也有 Hash 等类型，暂且不说，可 B+ 树 这是个什么妖魔鬼怪呢？

下面就来浅尝辄止的扒一扒树的前世今生。

--------------------

## 正文 ##

### 二叉树 ###

由 n（ n > 0）个有限节点组成一个具有层次关系的集合，看起来就像一个倒挂的树，因此称这样的数据结构为树。

一个节点的子节点个数叫做度，通俗的讲就是树叉的个数。树中最大的度叫做树的度，也叫做阶。一个 2 阶树最多有 2 个子节点即最多有 2 叉，因此这样的树称为**二叉树**，二叉树是树家族中最简单的树。

![format_png][]

两个叉的树就是二叉树，可这除了用来按一定结构存放数据外，跟查询性能好像也没关系，不会又是一个没用的噱头吧。

--------------------

### 二分查找 ###

听说二叉树的原始威力来源于一种叫做二分查找的算法。

相传在鹦鹉的原始社会，存在着森严的等级制度，每只鸟必须按高矮顺序分出等级和尊卑。

那么问题来了，如下图，怎样才能找出**最高**、**最矮**、**中等高**的那些鹦鹉呢、以及**指定高度**的那只呢?

![format_png 1][]

##### 第一种方法: 扫描法 #####

一个一个依次测量，完毕后所有的问题都迎刃而解。

这种一个一个依次全部测量的方法叫做扫描，他的缺点很明显，最高和最矮，需要全部测量完毕才能知晓。

而对于指定高度，最好的情况是第一次就找到；最坏的情况是最后一次才找到，时间复杂度为 n，也就是说从 13 个鹦鹉中找到指定身高的那只，最坏的情况是查 13 次。

##### 第二种方法：二分法 #####

13 个鹦鹉全部听令，按从矮到高列队，向左看齐，报数。

![format_png 2][]

报数字 1 的就是最矮的，报数字 13 的就是最高的，报数字 7 的就是中等身高的那只。

最好和最坏的情况都是一次找到。而查询性能一下子提高 13 倍，我的个乖乖，无论多个只鹦鹉，时间复杂度都是 1，好可怕。

> **问题**：我不服，你这是偷换概念，有本事对比一个查找指定高度鹦鹉的性能。

因为鹦鹉们已经按高矮排好了队，所以指定高度的鹦鹉，要么是站中间那个只，要么就是在它的左边或右边的那群里。

如果是中间那个，一次就找到，如果不是只需要从中间左边或右边那一半中找，再在这一半中找中间那只，对比身高。

以此类推，每次都把查询的范围减半，时间复杂度`log2(n)`。

那么 log2(13) 就是 4，最坏的情况也才 4 次，时间复杂度确实不是 1 了，但好像也不糟，简化如下：

![format_png 3][]

> **问题**：如果按高矮排队，仍然需要一个一个比较，跟扫描有什么区别，那还不如直接扫描呢？

事实确实如此,单纯的一次查询，先排序，再二分查找，不见得比扫描快，甚至还不如。

但是，在数据的世界，大部分数据一生会被查询无数次，如果只在数据降生的时候排一次序，往后余生，是不是就可以直接用二分查找，这似乎就是传说的读多写少，以及对应的复用。

**优点**：

*  查找快

**缺点**:

*  必须有序，需要提前排序
 *  每次查找都需要不断计算中间位置

--------------------

### 二分查找树 ###

如果一组数据不会或不常变更，那么他们的位置也基本不变。可是每次查询都需要重新计算中间位置是一种浪费，而浪费可耻。

我们能不能把所有中间节点组织起来，每次使用时，直接取中间节点?

请看下图，找到所有单次二分查找的中间节点，把他们连起来，并用手提起最中间的那个节点，就是一棵二分查找树。

![format_png 4][]

**优点**：二分查找树就是通过数据结构的方式实现了二分查找算法，通过存储中间节点的数据，弥补了二分查找每次都要计算中间位置的缺点。

--------------------

### 平衡二叉树: ###

如果二分查找树不断进行修改，比如删除某些节点，经过一段时间后，最早那个中间节点的数据（根），很可能就不在中间了。

中间位置就像一个天平的支点，如果他不在中间了，那么整个天平就会失衡，失衡的世界就会坍塌成不伦不类的瘸树，甚至是降维成一个链表或者数组。

二分查找算法的关键在于有序和中间节点，而二分查找树的关键是中间节点的维护，如果维护的节点已经不在中间了，那么它就失去了意义。

所以必须保证「二分查找树」是一个正确的树，一个根节点在中心的树，一个左右子树层级（高度）基本相等（高度相差不超过1）的树，一个平衡的树。

平衡二叉树中最常见的就是红黑树：

![format_png 5][]

红黑树规定了一系列节点颜色规则，以及对应的左旋和右旋操作来保证颜色规则，从而达到树的平衡性。

看到这花里胡哨的颜色以及复杂的规则，让人第一眼就望而却步，但所有的这些，也不过是为了保证二叉树的平衡性，由于维持平衡的操作太过麻烦，无法用一句话简单概括，只好用一堆人鬼难分的规则和步骤来实现，只要按着这些步骤就一定能实现二叉树的平衡。

*平衡二叉树 = 二分查找树 + 平衡（左右高度相差不超过 1 ）*

平衡二叉树并未提高二分查找树的性能，它只是保正树不会被二向箔（多次增删改）打击降维成链表或不对称的残缺树，永远维持平衡。

另外，不仅仅是二叉树，其他种类的树，也是需要有序和平衡，才能发挥最大的威力。

--------------------

### 多叉树之 B-tree ###

两个叉的树就能折半查询，理论可以提高一倍性能，那么多个叉是不是能提高更多倍性能？

如下图的 3 阶（叉）树（所有数据仅用于演示，非真实分布）

![format_png 6][]

每个节点维护两个数据，并指向最多 3 个子节点。如图 3 个子节点的数据分别为：小于 17， 17 ~ 35 ，大于 35。

假设，从上图中查找 10 这个数，步骤如下：

1.  找到根节点，对比 10 与 17 和 35 的大小，发现 10 < 17 在左子节点，也就是第 2 层节点；
2.  从根节点的指针，找到左子节点，对比 10 与 8 和 12 的大小，发现 8 < 10 < 12，数据在当前节点的中间子节点，也就是第 3 层节点；
3.  通过上步节点的指针，找到中间子节点（第 3 层节点），对比 10 与 9 和 10 的大小，发现 9 < 10 == 10，因此找到当前节点的第二数即为结果。

加上忽略的 12 个数据，从 26 个数据中查找一个数字 10，仅仅用了 log3(26)≈ 3 次，而如果用平衡二叉树,则需要 log2(26)≈ 5 次，事实证明，多叉树确实可以再次提高查找性能。

多叉树是在二分查找树的基础上，增加单个节点的数据存储数量，同时增加了树的子节点数，一次计算可以把查找范围缩小更多。

**优点**：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小。

**复杂节点**:  
至此，我们列举的数据都是孤零零的单个数字。试想，你手里已经有一个数据 10，为什么还要费力吧唧的再从一堆数据中找到这个 10，自己找自己？这不是有病吗？

单个数字只能活在演示中，现实的世界要复杂的多，我们来看一个接近真实场景的案例。

现有一个以年龄为索引的 3 阶树，存储了一批用户信息，如下图：

![format_png 7][]

数字为用户的年龄，其它为与树排序查找无关的业务数据，像这种索引数据与树排序查找无关的业务一起维护在节点的平衡多叉（阶）树称为 B- 树（ B 树）。

**缺点**：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。

--------------------

### 磁盘I/O ###

计算机的功能主要为：计算、存储和网络。而用于计算的数据以及计算后的结果很大一部分都需要存储起来，以备后续再次使用。向磁盘中存储和读取的过程叫磁盘 I/O。磁盘的读取方式和速度会严重影响到整个业务的计算性能。

下面我们简单了解一下磁盘是如何工作的。

磁盘大概长这个样子：

![format_png 8][]

磁盘主要由磁盘盘片、传动手臂、读写磁头和马达组成。

为了存储容量,主轴像穿糖葫芦一样把多个磁盘片组成一个阵列。通过马达驱动主轴转动以及传动手臂移动，使读写磁头在磁盘片上读写数据。大概如下：

![format_png 9][]

磁盘片由很多半径不等的同心圆组成，这些圆被称为磁道，数据就是写在这些磁道上。

![format_png 10][]

每个磁道又划分成块称为扇区。

![format_png 11][]

如果磁盘是一记事本，那么一张磁盘片就是本子的一页纸，而主轴就是本子的装订线；磁道就是纸页的行，而扇区可以看作是很宽的列。

![format_png 12][]

如果在磁盘中存储一首诗,想象中大概这个样子。

![format_png 13][]

磁盘的读 I/O 操作,需要找到数据所在的磁盘片，以及对应的磁道和扇区。这些操作类似于从一本书中找到数据所在的页，行，列。

因为每个磁盘片都对应一个磁头，所以性能的关键就在于找行和列，即寻道和磁盘旋转。寻道即通过磁头找到数据所在的磁道，相当于换行到数据所在行。由于磁头只能水平移动，即只能换行寻道，无法在指定磁道上移动，因此需要磁盘高速旋转移动到指定扇区，类似写春联时，笔不动，纸动。

![format_png 14][]

综上所述，磁盘的读写是通过机械运动来定位数据所在位置，而 cpu 是通过电信号进行数字运算。粗略的认为，机械查询数据，与光速处理数据的性能完全不是在一个量级，总之一句话就是**磁盘处理太慢太慢了**。

虽然磁盘处理数据太慢了，但是它是目前相对廉价且稳定的存储设备，所以又不能舍弃不用，但大致可以通过以下方法进行优化。

*  尽量减少 I/O 次数，比如可以使用缓存；
 *  每次 I/O 尽量获取更多的数据；
 *  每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数；

--------------------

### 多叉树之 B+tree ###

做为数据库的索引，无论用什么样的数据结构维护，这些数据最终都会存储到磁盘中。

鉴于磁盘 I/O 的性能问题，以及每次 I/O 获取数据量上限所限，提高索引本身 I/O 的方法最好是，减少 I/O 次数和每次获取有用的数据。

B-tree 已经大大改进了树家族的性能，它把多个数据集中存储在一个节点中，本身就可能减少了 I/O 次数或者寻道次数。

但是仍然有一个致命的缺陷，那就是它的索引数据与业务绑定在一块，而业务数据的大小很有可能远远超过了索引数据，这会大大减小一次 I/O 有用数据的获取，间接的增加 I/O 次数去获取有用的索引数据。

因为业务数据才是我们查询最终的目的，但是它又是在「二分」查找中途过程无用的数据，因此，如果只把业务数据存储在最终查询到的那个节点是不是就可以了？

理想很丰满，现实很骨瘦如柴，谁知道哪个节点就是最终要查询的节点呢？

B+tree 横空出世，**B+ 树就是为了拆分索引数据与业务数据的平衡多叉树**。

![format_png 15][]

B+ 树中，非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据。这样即保证了叶子节点的简约干净，数据量大大减小，又保证了最终能查到对应的业务数。既提高了单次 I/O 数据的有效性，又减少了 I/O 次数，还实现了业务。

但是，在数据中索引与数据是分离的，不像示例那样的？

如图：我们只需要把真实的业务数据，换成数据所在地址就可以了，此时，业务数据所在的地址在 B+ 树中充当业务数据。

![format_png 16][]

--------------------

### 总结 ###

*  数据存储在磁盘（ SSD 跟 CPU 性能也不在一个量级），而磁盘处理数据很慢；
 *  提高磁盘性能主要通过减少 I/O 次数，以及单次 I/O 有效数据量；
 *  索引通过多阶（一个节点保存多个数据，指向多个子节点）使树的结构更矮胖，从而减少 I/O 次数；
 *  索引通过 B+ 树，把业务数据与索引数据分离，来提高单次 I/O 有效数据量，从而减少 I/O 次数；
 *  索引通过树数据的有序和「二分查找」（多阶树可以假设为多分查找），大大缩小查询范围；
 *  索引针对的是单个字段或部分字段，数据量本身比一条记录的数据量要少的多，这样即使通过扫描的方式查询索引也比扫描数据库表本身快的多；

--------------------

### 知识扩展 ###

树的结构最大的优点就是查询性能高，因此所有需要提高查询性能的都可以考虑树。

而现实中也确实有这样的例子，比如：

*  HashMap 中的数据冲突时，链表转化成红黑树；
 *  数据库索引使用的 B+ 树；
 *  搜索引擎倒排索引使用的字典树；

以上只是浅尝辄止、点到为止的描述了数据库使用 B+ 树索引为什么能提高查询性能原因及简单过程。

并没有深入各种数据结构的细节，也未提及其它索引类型和索引的具体存储格式，目的仅仅是，为了让大家对索引有一个感性的认识。

[format_png]: /images/20221120/93a7d363f5804d8780420750105767b2.png
[format_png 1]: /images/20221120/c1d215adcd04432fa1e275d0eb52b518.png
[format_png 2]: /images/20221120/ba261d51f8e8404b85f660c413bd6998.png
[format_png 3]: /images/20221120/a51c844548d34b04928e7994541fdc78.png
[format_png 4]: /images/20221120/e68bb3a3be54423e80378def368b5493.png
[format_png 5]: /images/20221120/86061255c8ad4935bf833b7b17f9158b.png
[format_png 6]: /images/20221120/382afe390d18434e83cfc8de9bfdb37c.png
[format_png 7]: /images/20221120/61d88a30a5d84d5280d87ddc4d793990.png
[format_png 8]: /images/20221120/0c582b7c67874c418d92ed265f8dac98.png
[format_png 9]: /images/20221120/0435bfd702584bb8b5b4783a914066e9.png
[format_png 10]: /images/20221120/2caab4aec2114e91a0d116d4bd595768.png
[format_png 11]: /images/20221120/b75079a1f9d24e2fb18306b406803a8d.png
[format_png 12]: /images/20221120/b2675017232d491ebfcf3bb54729546b.png
[format_png 13]: /images/20221120/0e99ea7ebeef48278fce7cab2b3b2178.png
[format_png 14]: /images/20221120/f4958fcb7ae34119ad13870723ade555.png
[format_png 15]: /images/20221120/73a453d669794394bd45e9fc537abc3a.png
[format_png 16]: /images/20221120/e208cf7983ab497699b3f084a01c2de2.png