B树还是B+树，别再傻傻分不清了

B-Tree

B-Tree（B树）是一棵多路搜索平衡查找树，相对于二叉树，B树的每个节点有多个子节点，即多叉（路）。Oracle和MongoDB使用的索引技术就是基于B树的数据结构。

一棵m阶的B-Tree有如下特征（其中ceil(x)是一个取最大值的函数）：

1. 每个节点最多有m个子节点；
2. 每个非叶子节点（根节点除外）至少有ceil(m/2)个子节点；
3. 如果根节点不是叶子节点，那么根节点至少有2个子节点；
4. 对于非叶子节点，最多存储m-1个关键字；
5. 每个节点的关键字是遵循左小右大的原则依次排序的；
6. 每个节点既存放索引也存放数据；
7. 所有叶子节点都处在同一层。

B树查找

假设现在有一个初始状态为3阶的B树，我们以查找13为例：

• 第一次磁盘IO：13比30小，选择左子树；
• 第二次磁盘IO：13比15小，选择左子树；
• 第三次磁盘IO：定位到13，查出对应的数据，查询结束。

B+Tree（B+树）

相对于B树，B+树有四点不同：

1. B+树中非叶子节点不存放数据，存的是索引，它的叶子节点才存放数据，而B树中所有节点都存放数据；
2. B+树相邻的叶子节点之间通过链表指针连接起来，而B树没有；
3. 查找过程中，B树在找到具体的数据以后就结束，而B+树则需要通过索引找到叶子节点中数据才结束；
4. B树任何一个关键字只出现在一个节点中，而B+树可以出现多次。

因此，相对于B树，B+树有以下优点：

• 非叶子节点不存放数据，单一节点存储更多的元素，磁盘IO次数更少；
• 查询都要找到叶子节点，查询性能稳定；
• 所有叶子节点形成有序链表，便于范围查询，查询效率更高。

一个B+树能存放多少数据

在MySQL中InnoDB的默认页大小为16KB，这个值可以修改；

查询命令如下：

SHOW VARIABLES LIKE 'innodb_page_size';

InnoDB中的聚簇索引B+树的一个节点被设计为一页，一页大小在InnoDB中默认为16KB，假设主键索引类型为bigint（8Byte）,指针在InnoDB中为6Byte，共14字节。因为在非叶子节点中的Key值就会对应一个指针，即N个Key+N个指针，那么16KB能存放16*1024/14=1170个索引指针。

假设一条数据大小为1KB，那么叶子节点可以存储16条数据，对于2阶的B+树则会有1170个叶子节点，那么最多可以存放18,720（1170*16）条数据。而对于3阶的B+树，最多可以存放21,902,400（1170*1170*16）条数据。

由此可见3阶B+树就能满足千万级的数据存储需求，因此，16KB页面大小还是很合理的。