MySQL 数据库要用B+树存储索引？
# 背景
在面试中，mysql的索引结构应该是高频考点了。
面试官：你了解mysql的索引吗？
我：索引是一种协助快速查询数据的一种数据结构。
面试官：那你知道mysql中存储索引用的什么数据结构吗？
我：一般使用B+数吧。
面试官：B+树的查询时间大概是多少？
我：和树的高度有关，log(n)
面试官：mysql的索引结构为什么选用B+树，而不是选择二叉排序树、平衡二叉树、红黑树以及Hash呢？
我：……
mysql的索引结构为什么选用B+树？ 这个问题之前在总结 mysql索引 的时候已经总结过了，但是感觉还是没有总结到位，考虑的方面还不够全面，所以这篇文章再来细细地捋一下。
数据结构选型以如下图的user表进行分析：
# Hash 表
哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，通过这个地址进行数据查询的数据结构。
如果需要检索id=7的数据，sql如下：
select *
from user
where id = 7;
2
3
哈希算法快速检索数据的计算过程：首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的额数据的物理地址，通过该独立地址可以找到对应 user_name='g'这个数据。
但是hash算法可能出现碰撞问题，即hash函数可能计算相同的key值，不同的key映射到了同一个结果。解决碰撞问题的常见方法是链地址法 ：碰撞数据使用链表连接，计算hash值后，判断该值如果有碰撞，遍历到链表，直到找到真正的key所对应的数据为止。
从算法时间复杂度分析来看，哈希算法时间复杂度为 O(1)，检索速度非常快。比如查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法。
select * from user where id >3;
即hash算法针对范围查找效率太低，需要把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。
Hash索引仅仅适合等值查询，如果是范围查询和排序的话，它的性能就会大大下降。
而往往我们的业务都是复杂的查询，我们数据库大部分瓶颈也是在查询上，所以Hash索引在大部分场景下是不适合的。
总结：hash表可以快速检索单条数据，但是范围查询和排序的效率太低，而且可能需要Hash碰撞，极端情况下效率低。所以不适合作为MySQL的索引数据结构。
# 二叉查找树（BST）
为了解决hash表范围查找效率低的问题，我们考虑二叉查找树。
二叉查找树支持快速查找数据，时间复杂度为O(logn)。如下图所示，只需计算三次即可找到id=7的数据。
二叉查找数按序排列（从左到右升序），如果想找到id>5的数据，只需要找到节点6及其右子树的数据即可，范围查找比较容易实现。
普通二叉树的致命缺点：极端情况下会退化为线性链表，时间复杂度为O(n)，性能急剧下降，如下图：
数据库表的主键id一般为自增，上述的线性结构查找问题必然出现，而且频率还很高。
总结：二叉查找数查询效率高，而且可以解决hash表范围查询效率低的问题，但是会频繁出现不平衡退化问题导致查询效率低的问题，所以不适合作为MySQL索引的数据结构。
# 红黑树
二叉查找树不平衡，可以通过树节点的自动旋转和调整来解决，从而保证二叉树的查找性能。最常见的思路是平衡二叉树和红黑树。
红黑树可以自动调整树的结构，当二叉树不平衡时，红黑树自动左右旋转和节点变色，保持基本平衡，时间复杂度为O(logn)，查询效率不会降低。如下图，红黑树查找id=7的节点只需要查找4次：
但是红黑树也有缺点，即“右倾”现象（参看下图），虽然没有二叉树退化那么夸张，但数据库主键基本都是自增，面对成千上百万的数据，这查询效率可想而知。
总结：红黑树查询效率与二叉查找树相似，极端退化情况比平衡二叉树好，但是也没能达到预期，所以不适合MySQL索引的数据结构。
# 平衡二叉树（AVL）
既然二叉树不平衡，为了解决其极端情况下退化为线性链表的问题，我们考虑使用平衡二叉树。
AVL 树顺序插入 1~7 个节点，查找 id=7 所要比较节点的次数为 3。
AVL 树插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。
从树的形态看来，AVL 树不存在红黑树的“右倾”问题。大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。
AVL 树的优点：
- 查询效率高O(logn)，不存在极端情况。
- 可以进行范围查找和排序。
但是为什么不选取AVL树作为MySQL索引的数据结构？
主要是磁盘IO因素的影响。如果使用AVL树，每一个树节点，只存储一个数据。如果查询id=7的数据，需要比对三次树节点，即进行三次磁盘IO操作，如果数据量大了，那磁盘IO的次数会很高，消耗大量的时间。
所以，设计数据库索引的时候，还需要考虑怎么尽可能减少磁盘的IO次数。
注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。
磁盘读取1B和1KB的数据消耗的时间基本是一样的，所以可以在一个节点存储更多的数据，即一次磁盘IO读取更多数据，即可解决问题。所以就考虑到了B树。
# B树
B树是一种平衡多路搜索树，它的每个节点可以拥有多于两个孩子节点。M路的B树最多能拥有M个孩子节点。
平衡二叉树没能充分利用磁盘预读功能，而B树是为了充分利用磁盘预读功能来而创建的一种数据结构，也就是说B树就是为了作为索引才被发明出来的的。
为啥要设计成多路呢？
是为了进一步降低树的高度。路数越多，树的高度越低。
如果设计成无限多路可以吗？
设计成无限多路，树会退化成有序数组。mysql默认一个节点也就是一次IO读取数据的大小刚好是16K，一次IO是为了加载一个节点，读取一页数据，这样可以读更多的数据。如果是有序数组，这样反而不好，因为数据量太大一次不能够将数据加载到内存。
你知道B树一般用在哪里吗？
B树做文件系统的索引比较多。
为什么文件系统的索引喜欢用B树而不用红黑树或者有序数组呢?
文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。
如果一棵树都无法一次性加载进内存，你该怎么查找呢?
这时候B树的多路存储威力就出来了，可以每次加载B树的一个节点，然后一步步往下找。
如果在内存中,红黑树比B树效率更高，但是涉及到磁盘操作，B树就更优了。
磁盘IO与预读
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。
mysql每一次IO读取的数据我们称之为一页(page)。
如果每个节点限制最多存储两个key（即二叉树），一个节点如果超过两个key会自动分裂。
比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。
如果是一个存储了 16 个数据的 B 树，同样每个节点最多存储 2 个 key，查询 id=16 这个数据需要查询比较 4 个节点，也就是经过 4 次磁盘 IO。看起来查询性能与 AVL 树一样。
如果限制每个节点可以存储6个key。
一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。
一个存储了 16 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。相对于 AVL 树而言磁盘 IO 次数降低为一半。
B 树作数据库索引优点：
- 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
- 尽可能少的磁盘 IO，加快了检索速度；
- 可以支持范围查找。
缺点：
如果是多条的话，B树需要做局部的中序遍历，可能要跨层访问。
# B+树
比B树更适合作为索引的结构是B+树。MySQL中也是使用B+树作为索引。它是B树的变种，因此是基于B树来改进的。为什么B+树会比B树更加优秀呢？
- B树：有序数组+平衡多叉树；
- B+树：有序数组链表+平衡多叉树；
B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。
B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
——梁斌《走进搜索引擎》
比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。
只查询一条记录，B树性能会好于B+树，因为B树的高度总体要比B+树矮。但是更多的业务需要的却是范围查询。
数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。
B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
在数据库中基于范围的查询是非常频繁的，因此MySQL最终选择的索引结构是B+树而不是B树。
B+树的查找过程：
如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。
真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。
# B*树
B*Tree是B+树的变体，在B+Tree的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B* 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
# 为什么MySQL的索引要使用B+树而不是B树?
两个角度：范围查询和树的高度（IO查询次数）。
- B+树在B树基础上进行变种，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点，非常便于范围查询。
- 如果是多条的话，B树需要做局部的中序遍历，可能要跨层访问。
- 而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。
- B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少。指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低。
# 为什么MySQL的索引要使用B+树而不是Hash索引?
如果只选一个数据，那确实是hash更快。但是数据库中经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了。
而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。
# 总结
- Hash索引可以快速进行等值查询，时间复杂度为O(1)，但是并不适合范围查询和排序，而且可能需要Hash碰撞，极端情况下效率低。
- 二叉查找树可以进行范围查询，时间复杂度为O(log(n))效率也可以，但是极端情况下会退化为线性链表，最坏时间复杂度为O(n)，而且通常是基于主键插入数据，退化概率很高，性能低。
- 平衡树中，红黑树极端情况也会有右倾退化的问题（类似于链）；平衡二叉树绝对均衡，查询效率很高，但插入时需要频繁调整，性能低。最重要的原因是：平衡二叉树树比较高，需要多次IO查询。
- B树每个节点可以存储更多的数据，而且是多路，可以大大降低树的高度，减少了IO查询。但是范围查询时比较复杂，效率略低。
- B+树在B树基础上进行变种，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点，非常便于范围查询。
- B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；