数据库索引为什么使用B+树？

B tree： 二叉树（Binary tree），每个节点只能存储一个数。

B-tree： B树（B-Tree，并不是B“减”树，横杠为连接符，容易被误导）

B树属于多叉树又名平衡多路查找树。每个节点可以多个数（由磁盘大小决定）。

B+tree 和 B*tree 都是 B-tree的变种

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O *** 作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。

不了解磁盘相关知识的可以查看 硬盘基本知识（磁头、磁道、扇区、柱面）

下面通过示意图来看一下，B-tree、B+tree、B*tree

从图中可以看出，B-tree 利用了磁盘块的特性进行构建的树。每个磁盘块一个节点，每个节点包含了很关键字。把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

B-tree巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（每页为4K），这样每个节点只需要一次I/O就可以完全载入。

B-tree 的数据可以存在任何节点中。

B+tree 是 B-tree 的变种，数据只能存储在叶子节点。

B+tree 是 B-tree 的变种，B+tree 数据只存储在叶子节点中。这样在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定

B*tree 每个磁盘块中又添加了对下一个磁盘块的引用。这样可以在当前磁盘块满时，不用扩容直接存储到下一个临近磁盘块中。当两个邻近的磁盘块都满时，这两个磁盘块各分出1/3的数据重新分配一个磁盘块，这样这三个磁盘块的数据都为2/3。

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

B+树是一种树数据结构，常见于数据库与档案系统之中。B+树能够使资料保持有序，并拥有均匀的对数处理时间的插入和删除动作。B树的元素通常会自底向上插入，有别于多数自顶向下插入的二叉树。

B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡 *** 作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树(常简称为2-3 树)中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。

B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有在叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音(Boeing)，因为他曾经工作于波音科学研究实验室。

节点结构

在 B+ 树中的节点通常被表示为一组有序的元素和子指针。除了根之外的每个节点都包含最少 L 个元素最多 U 个元素，对于任意的 L 和 U 有最多 U+1 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。

每个内部节点的元素充当分开它的子树的分离值。例如，如果内部节点有三个子节点(或子树)则它必须有两个分离值或元素 a1 和 a2。在最左子树中所有的值都小于 a1，在中间子树中所有的值都在 a1 和 a2 之间，而在最右子树中所有的值都大于 a2。

算法

查找

查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用二分查找来确定这个位置。

插入

节点要处于违规状态，它必须包含在可接受范围之外数目的元素。

首先，查找要插入其中的节点的位置。接着把值插入这个节点中。

如果没有节点处于违规状态则处理结束。

如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则建立一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不大于最大数的一半。

删除

首先，查找要删除的值。接着从包含它的节点中删除这个值。

如果没有节点处于违规状态则处理结束。

如果节点处于违规状态则有两种可能情况:

它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。

它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

注解

假定 L 是节点允许拥有子节点的最小数目，而 U 是最大数目。则每个节点总是有在 L 和 U 之间(包含它们在内)个子节点，除了一个例外: 根节点有从2到U(包含它们在内)个子节点。换句话说，根节点豁免于低边界限制，而拥有它自己的低边界2。这允许树持有小数目的元素。根有一个子节点没有意义，因为附着在这个子节点上的子树可以简单的附着在根节点上。允许根节点没有子节点也是不需要的，因为没有元素的树典型的表示为没有根节点。

先从数据结构的角度来答。题主应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。那么Mysql如何衡量查询效率呢？磁盘IO次数，B-树（B类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用B+树就能很好的完成这个目的，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时啊！），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。另一个优点是什么，B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。至于MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。总体来说，Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

---