一、B树

B树又叫B-Tree、B-树，这里的 B 是 Balance（平衡）的缩写，所以它又叫平衡多路查找树。

• 它跟普通的平衡二叉树的不同是，B树的每个节点可以存储多个数据，而且每个节点不止有两个子节点，最多可以有上千个子节点。
• 中每个节点都存放着索引和数据，数据遍布整个树结构，搜索可能在非叶子节点结束，最好的情况是O(1)。
• 一般一棵 B 树的高度在 3 层左右，3 层就可满足 百万级别的数据量。
  

二、B+树

B+树是B树的一种变种，它与B树的区别是：

• 叶子节点保存了完整的索引和数据，而非叶子节点只保存索引值，因此它的查询时间固定为 log(n)。
• 叶子节点中有指向下一个叶子节点的指针，叶子节点类似于一个单链表。
• 正因为叶子节点保存了完整的数据以及有指针作为连接，B+树可以增加了区间访问性，提高了范围查询，而B树的范围查询相对较差。
• B+树更适合外部存储。因为它的非叶子节点不存储数据，只保存索引。
  

三、细化

3.1 B树特点

1、所有键值分布在整颗树中（索引值和具体data都在每个节点里）。
2、任何一个关键字出现且只出现在一个结点中。
3、搜索有可能在非叶子结点结束（好情况O(1)就能找到数据）
4、在关键字全集内做一次查找，能逼近二分查找；

3.2 B+树特点

1、所有关键字存储在叶子节点出现，内部节点（非叶子节点并不存储真正的 data）
2、为所有叶子结点增加了一个链指针

3.3 两者区别

1、B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据
2、B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
3、B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确