面试SQL学习之索引篇（二）

上次讲到了索引的作用， 今天我们来看下，索引的数据结构究竟是怎样的？

1. 为什么索引要存放到硬盘上？
2. B树和B+树的结构是怎样的？为什么我们常用B+树作为索引的数据结构？

为什么索引要存放到硬盘上？

数据库服务器有两种存储介质，分别为硬盘和内存。

• 内存属于临时存储，容量有限，而且当发生意外时（比如断电或者发生故障重启）会造成数据丢失；

• 硬盘相当于永久存储介质，这也是为什么我们需要把数据保存到硬盘上。这就是我们所说的 持久化 ！

虽然内存的读取速度很快，但我们还是需要将索引存放到硬盘上。当我们在硬盘上进行查询时，也就产生了硬盘的I/O操作。相比于内存的存取来说，硬盘的I/O存取消耗的时间要高很多。我们通过索引来查找某行数据的时候，需要计算产生的磁盘I/O次数，当磁盘I/O次数越多，所消耗的时间也就越大。

如果我们能让索引的数据结构尽量减少硬盘的I/O操作，所消耗的时间也就越小。

B树

这里就不过多阐述二叉树或者是平衡二叉树为什么不可以做索引的数据结构了（大家可以去查查相关的查询参数）。这里只说一句：如果用二叉树作为索引的实现结构，会让树变得很高，增加硬盘的I/O次数，影响数据查询的时间。 所以我们的做法就是：因此一个节点就不能只有2个子节点，而应该允许有M个子节点(M>2)。

B树的出现就是为了解决这个问题，B树的英文是Balance Tree，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用B树来实现。

在数据库里面，B树的结构如下图所示：

B树作为平衡的多路搜索树，它的每一个节点最多可以包括M个子节点，M称为B树的阶。

同时你能看到，每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x个关键字，那么指针数就是x+1。对于一个100阶的B树来说，如果有3层的话最多可以存储约100万的索引数据。对于大量的索引数据来说，采用B树的结构是非常适合的，因为树的高度要远小于二叉树的高度。

然后我们来看下如何用B树进行查找。假设我们想要查找的关键字是9，有以下几步：

1. 我们与根节点的关键字(17，35）进行比较，9小于17那么得到指针P1；
2. 按照指针P1找到磁盘块2，关键字为（8，12），因为9在8和12之间，所以我们得到指针P2；
3. 按照指针P2找到磁盘块6，关键字为（9，10），然后我们找到了关键字9。

在B树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行I/O操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素，B树相比于平衡二叉树来说磁盘I/O操作要少，在数据查询中比平衡二叉树效率要高。

B+树

B+树基于B树做出了改进，主流的DBMS都支持B+树的索引方式，比如MySQL。他们两个有这么几个差别：

1. 有 k 个孩子的节点就有k个关键字。也就是孩子数量=关键字数
2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

再回到 B树：

1. 孩子数量=关键字数+1。【对比1】
2. 非叶子节点既保存索引，也保存数据记录。【对比3】

Include：

它的键一定会出现在叶子节点上，同时也有可能在非叶子节点中重复出现。而 B 树中同一键值不会出现多次。

举个例子看看上面的描述：一棵B+树，阶数为3，根节点中的关键字1、18、35分别是子节点（1，8，14），（18，24，31）和（35，41，53）中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中，因此在叶子节点中包括了所有的关键字信息，并且每一个叶子节点都有一个指向下一个节点的指针，这样就形成了一个链表。

比如，我们想要查找关键字16：

1. 与根节点的关键字(1，18，35)进行比较，16在1和18之间，得到指针P1（指向磁盘块2）
2. 找到磁盘块2，关键字为（1，8，14），因为16大于14，所以得到指针P3（指向磁盘块7）
3. 找到磁盘块7，关键字为（14，16，17），然后我们找到了关键字16，然后找到关键字16所对应的数据。

整个过程一共进行了3次I/O操作，这么看起来B+树和B树的查询过程差不多，但是B+树和B树有个根本的差异在于，B+树的中间节点并不直接存储数据。这样的好处是什么呢？

• 查询效率更稳定

B+树每次只有访问到叶子节点才能找到对应的数据，而在B树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。

• 查询效率更高

通常B+树比B树更矮胖（阶数更大，深度更低），查询所需要的磁盘I/O也会更少。同样的磁盘页大小，B+树可以存储更多的节点关键字。

不仅是对单个关键字的查询上，在查询范围上，B+树的效率也比B树高。这是因为所有关键字都出现在B+树的叶子节点中，并通过有序链表进行了链接。而在B树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。

非聚集索引

我们返回来再看看这个问题，上节说到非聚集索引会有 回表 操作，那么这个操作具体是什么样子？

聚集索引的叶子节点存放了整行数据，而 InnoDB 存储引擎非聚集索引的叶子节点并不会放整行数据，而存放的是键值和主键 ID。

当通过辅助索引来寻找数据时：

1. InnoDB 存储引擎会遍历辅助索引树查找到对应记录的主键
2. 通过主键索引来找到对应的行数据

比如一颗高度为 3 的辅助索引树中查找数据，那需要对这颗辅助索引树遍历 3 次找到指定主键，如果聚集索引树的高度也为 3，那么还需要对聚集索引树进行 3 次查找，最终找到一个完整的行数据所在的页，因此获取数据一共需要6次逻辑 IO 访问。

假设下面就是某个表的某个非聚集索引 idx_a 结构：

上图中两点关键点需要注意：

• 根据 a 字段的值创建了 B+ 树结构
• 每个叶子节点保存的是 a 字段自己的键值和主键 ID

对于该表，比如有下面这条查询语句：

select * from test where a=3;

它先通过 a 字段上的索引树，得到主键 id 为 3，再到 id 的聚集索引树上找到对应的行数据。

而下面这条 SQL:

select * from test where id=3;

查询到的结果是一样的，而执行过程则只需要搜索 id 的聚集索引树。我们能看出辅助索引的查询比主键查询多扫描一颗索引树，所以，我们应该尽量使用主键做为条件进行查询。