这一章其实也是一个老生常谈的面试题了，我们直接说答案，InnoDB的索引底层数据结构是B+树，那么为什么InnoDB的索引要采用B+树呢？我们先一步步来！！！

一、二叉树

我们都知道二叉树是一个最常用最基本的数据结构，但它有一个致命缺点，就是非常容易形成链表，比如一共7个数，我从1开始insert，一直到7，就会形成如下的数据结构：

那么这就形成了一个链表，如果数据量很多很多，链表会非常长，查询效率可想而知！！！

二、红黑树

那么为了解决二叉树的缺点，我们引入了红黑树，红黑树与二叉树最大的区别就是，红黑树可以自动平衡，我们还是7个数，从1开始insert，一直到7，形成的数据结构如下：

从图可以看出，红黑树会自动帮我们进行树的平衡，但不要高兴太早，红黑树也有个大的缺点，就是当你的数据量过大，比如几百万上千万数据，那么树的层数会非常多，树会变得很高，如果你查询最低的叶子节点，那效率会非常低。

类似于有50层的高楼，我要查找第一层的数据，那我只能从50层往下一点点找，效率很低。

三、B-Tree

B树就是一个大的节点里面有很多小的K-V节点，放着我们的索引数据，不管是根节点还是叶子节点都有我们的data数据。

四、B+树

4.1 理解B+树

首先看看B+树有哪些特点：

1. B+树是一棵平衡树，每个叶子节点到根节点的路径长度相同，查找效率较高；
2. B+树的所有关键都在叶子节点上，因此范围查询时只需要遍历一遍叶子节点即可；
3. B+树的叶子节点都按照关键字大小顺序存放，因此可以快速地支持按照关键字大小进行排序；
4. B+树的非叶子节点不存储实际数据，因此可以存储更多的索引数据；
5. B+树的非叶子节点使用指针连接子节点，因此可以快速地支持范围查询和倒序查询；
6. B+树的叶子节点之间通过双向链表链接，方便进行范围查询。

那么，使用B+树实现索引，就有以下几个优点：

1. 支持范围查询，B+树在进行范围查找时，只需要从根节点一直遍历到叶子节点，因为数据都存储在叶子节点上，而且叶子节点之间有指针连接，可以很方便地进行范围查找；
   
2. 支持排序，B+树的叶子节点按照关键字顺序存储，可以快速支持排序操作，提高排序效率；
   
3. 存储更多的索引数据，因为它的非叶子节点只存储索引关键字，不存储实际数据，因此可以存储更多的索引数据；
   
4. 在节点分裂和合并时，IO操作少。B+树的叶子节点的大小是固定的，而且节点的大小一般都会设置为一页的大小，这就使得节点分裂和合并时，IO操作很少，只需读取和写入一页；
   
5. 有利于磁盘预读。由于B+树的节点大小是固定的，因此可以很好地利用磁盘预读特性，一次性读取多个节点到内存中，这样可以减少IO操作次数，提高查询效率；
   
6. 有利于缓存。B+树的非叶子节点只存储指向子节点的指针，而不存储数据，这样可以使得缓存能够容纳更多的索引数据，从而提高缓存的命中率，加快查询速度。
   

4.2 B+树解决红黑树层数高的问题

mysql中非叶子节点大约是16K大小，我们假如主键用bigint，大小为8字节，中间为下一个磁盘节点的文件地址，一般为6字节，那么16K大小能放多少个索引元素，16K/8b+6b为1170，那么就能放下1170个索引元素。

16是什么呢？我们data数据就算放一整行数据，一般最大也不超过1KB，一行数据撑死1KB，所以我们能放16个。

那么1170*1170*16=21902400，B+树三层节点能放下2000多万元素，我要找某个数据，只需要三次磁盘IO即可找到，效率多高。

而且根节点还是常驻内存的，这更快了！！！

4.3 B树与B+树的区别？

其实二者最大的区别就是B+树非叶子节点不存储数据。

我们都知道影响查询效率的主要就是树的高度，那我们刚才说了，B+树三层可以存储2000多万元素，那B树因为非叶子节点也存储数据，所以导致非叶子节点也只能存16个，如果数据是1KB的话。

五、MyISAM索引文件和数据文件是分离的（非聚集）

我们可以看mysql的安装目录，有个data/数据库名，如果是MyISAM存储引擎，则会有个MYI文件和MYD文件，MYI就是存储索引的文件，MYD就是存储数据的文件。

假如我要找col1=30的数据，该怎么个流程呢？

可以看到我们先遍历非叶子节点，这里就去MYI文件里找，找到30，然后对应非叶子节点的地址是0xF3，再通过这个地址去MYD文件里找数据并返回。而这个就叫做非聚集索引。

六、InnoDB索引实现（聚集）

InnoDB存储引擎只有一个文件，就是IBD文件，它是索引和数据放在一起的。

看图得知，叶子节点30是索引，也就是col1字段，同时也包含col2和col3字段的值。这个就是我们非常有名的聚集索引。

聚集索引就是叶节点包含了完整的数据记录。

七、为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

如果有主键，B+树会直接使用主键去构建索引结构，因为主键的值都是不相等的，所以非常好构建。

那如果我们不创建主键，那Mysql会从第一个字段一直找，直到知道一个值都不相同的列去构建B+树，那如果压根没有值都不相等的列怎么办？那Mysql就会给你创建一个隐藏列，类似于rowid一样，来构建B+树。

虽然不建主键，Mysql也会帮我们创建一个隐藏列去解决，但我们要知道，数据库资源是非常宝贵的，这么简单的事就不要让Mysql去做了。

那为什么推荐使用整型做自增主键呢？B+树在构建的时候，是一个个比对按顺序来构建的，你觉得用UUID这种字符串去做比对合适吗？显然不合适，还是老实用整型吧。

八、B+树索引和Hash索引有什么区别？

B+ 树索引和哈希索引是常见的数据库索引结构，它们有以下几个主要区别：

B+ 树索引将索引列的值按照大小排序后存储，因此 B+ 树索引适合于范围查找和排序操作；而哈希索引是将索引列的值通过哈希函数计算后得到一个桶的编号，然后将桶内的记录保存在一个链表或者树结构中。因此，哈希索引适合于等值查询，但不适合范围查询和排序操作。

B+ 树索引在插入和删除数据时需要调整索引结构，这个过程可能会涉及到页分裂或页合并等操作，因此 B+ 树索引的维护成本比较高；而哈希索引在插入和删除数据时只需要计算哈希值并插入或删除链表中的记录，因此哈希索引的维护成本相对较低。

B+ 树索引在磁盘上是有序存储的，因此在进行区间查询时可以利用磁盘预读的优势提高查询效率；而哈希索引在磁盘上是无序存储的，因此在进行区间查询时可能会需要随机访问磁盘，导致查询效率降低。

B+ 树索引在节点中存储多个键值对，因此可以充分利用磁盘块的空间，提高空间利用率；而哈希索引由于需要存储哈希值和指针，因此空间利用率相对较低。

九、联合索引的底层存储结构长什么样？

我们这里符合一个最左前缀法则，比如上图我们拿name、age、position来做联合索引，那么就会先比较name值，比如HanMeimei和Jeff值不同，那就能比较出大小了，那也就不用再继续比较age和position了。

但如果name值相同，则比较age，如果age值也相同，则比较position。