数据库索引为什么使用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*树额分解次数变得更少；

事实上，在MySQL数据库中，诸多存储引擎使用的是B+树，即便其名字看上去是BTREE。

4.1 innodb的索引机制

先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的

首先创建一张表：zodiac，并插入一些数据

对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主索引中的叶子页（leaf page）包含了数据记录，但非叶子节点只包含了主键，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起，因此这种索引被称为聚簇索引，或聚集索引。

这种索引方式，可以提高数据访问的速度，因为索引和数据是保存在同一棵B树之中，从聚簇索引中获取数据通常比在非聚簇索引中要来得快。

所以可以说，innodb的数据文件是依靠主键组织起来的，这也就是为什么innodb引擎下创建的表，必须指定主键的原因，如果没有显式指定主键，innodb引擎仍然会对该表隐式地定义一个主键作为聚簇索引。

同样innodb的辅助索引，如下图所示，假设这些字符是按照生肖的顺序排列的（其实我也不知道具体怎么实现，不要在意这些细节，就是举个例子），其叶子节点中也包含了记录的主键，因此innodb引擎在查询辅助索引的时候会查询两次，首先通过辅助索引得到主键值，然后再查询主索引，略微有点啰嗦

为什么说B+树比B 树更适合实际应用中 *** 作系统的文件索引和数据库索引？ B+树的磁盘读写代价更低

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

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。 B+树的查询效率更加稳定

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

---