博客主页：看看是李XX还是李歘歘 

每天分享一些包括但不限于计算机基础、算法等相关的知识点

点关注不迷路，总有一些知识点是你想要的

️今天的内容是      MySQL的索引结构为什么是B+树？    ️

先来看一下树的演化：

1. 树：非线性结构，每个节点有唯一的一个父结点和多个子结点（子树），为一对多的关系。
2. 二叉树：每个结点最多有两颗子树，并且子树有左右之分，不能颠倒。
3. 满二叉树：每一层的结点个数都达到了当层能达到的最大结点数。

4. 完全二叉树：除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点，而这些连续结点右边的结点全部不存在。

5. 二叉查找树(BST)是一种特殊的二叉树，又称为二叉排序树、二叉搜索树。二叉査找树的递归定义如下：

   ①要么二叉査找树是一棵空树。

   ②要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。

6. 平衡二叉树(AVL树)，是一种特殊的二叉排序树，其左右子树都平衡二叉树，且左右子树高度之差不大超过1。

7. B树属于多叉树，又名平衡多路查找树，查找路径有多个，一个树节点中包含多条数据，并包含多个指针域。B-树就是B树（别讲什么B减树，‘-’是分隔符）。

8. B+树，也是一种平衡多路查找树，是在B树的基础上发展而来的。

正文

数据库的索引及其数据是存储在磁盘中的，从磁盘中读取数据的速度会比内存中读取慢很多，所以，我们应当尽量减少从磁盘中读取数据的次数。 另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。 如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。

为什么不使用二叉查找树？

二叉查找树可能出现“一条龙”的景象，把二叉树特殊化为一个链表，相当于全表扫描，查找元素发挥不了二叉排序树的优势，只能按照链表的形式查找，高度太高了，查找效率不稳定。

为什么不使用平衡二叉树？

平衡二叉树解决了二叉树高度太高，查找效率不稳定的问题。但是，平衡二叉树的每个节点只存储一个键值和数据，如果数据非常的多（大多数情况下数据是海量的），二叉树的结点将会非常多，高度也会及其高，查找效率降低。

为什么不使用B树？

B树相对于平衡二叉树，优势在于每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子结点，高度就会降低，B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题，在找数据时需要遍历整个B树，为解决这个问题引出了B+树，。

B+树

1. B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。 

2. 因为B+树索引的所有数据均存储在叶子节点，并用链表链接成一个线性表【在数据库设计中B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的】。而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。  

为什么MySQL选择B+树做索引

1、B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、B+树更便于遍历：由于B+树的数据都存储在叶子结点中，非叶子结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

4、B+树更适合基于范围的查询：B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

【数据库】B树、B+树、索引_皮皮要HAPPY的博客-程序员宅基地_数据库索引b树和b+树

MySQL中存储索引用到的数据结构是B+树，B+树的查询时间跟树的高度有关，是log(n)，如果用hash存储，那么查询时间是O(1)。既然hash比B+树更快，为什么mysql用B+树来存储索引呢？

1. 从内存角度上说，数据库中的索引一般时在磁盘上，数据量大的情况可能无法一次性装入内存，B+树的设计可以允许数据分批加载。
2. 从业务场景上说，如果只选择一个数据那确实是hash更快，但是数据库中经常会选中多条这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了，hash还需要解决冲突。

Hash索引和B+树区别是什么？你在设计索引是怎么抉择的？

• B+树可以进行范围查询，Hash索引不能。
• B+树支持联合索引的最左侧原则，Hash索引不支持。
• B+树支持order by排序，Hash索引不支持。
• Hash索引在等值查询上比B+树效率更高。
• B+树使用like进行模糊查询的时候，like后面（比如%开头）的话可以起到优化的作用，Hash索引根本无法进行模糊查询。

问题2：既然增加树的路数可以降低树的高度，那么无限增加树的路数是不是可以有最优的查找效率？

答：这样会形成一个有序数组，文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。有序数组没法一次性加载进内存，这时候B+树的多路存储威力就出来了，可以每次加载B+树的一个结点，然后一步步往下找。

在内存中，红黑树比B树更优，但是涉及到磁盘操作B树就更优了

TODO：差一个红黑树

参考：
再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她

https://segmentfault.com/a/1190000021488885

补充：

至于MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。