前言
从算法逻辑上讲二叉查找树的查找和插入操作效率都已经很高，但是在实际应用中由于我们不能将整个索引表加载到内存，只能逐一加载每个磁盘页，这里的磁盘页就对应着索引树的节点。因此我们要将原本“瘦高”的树结构变得“矮胖”，从而减少磁盘IO的次数。
B- 树
B-树是一种多路平衡查找树，是对2-3树的一个扩展。一个m阶的B树（m的大小取决于磁盘页的大小）具有如下几个特征：
- 根结点至少有两个子女。
- 每个中间节点都包含k-1个元素和k个孩子，其中 k ∈ [m/2, m]
- 每一个叶子节点都包含k-1个元素，其中 k ∈ [m/2, m]
- 所有的叶子结点都位于同一层。
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
查找
下图以一个3阶B-树为例，第一次磁盘IO并在内存中和9比较：
第二次磁盘IO并在内存中和2、6比较：
第三次磁盘IO并在内存中和3、5比较：
单从比较次数来说B树相比二叉查找树并不占优势，但由于节点中存储着多个元素，因此它的磁盘IO次数比二叉查找树少很多，而内存中的比较耗时几乎可以忽略，因此查找性能也就比二叉查找树更好。
插入
以插入元素4为例，自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间，而由于此B-树是3阶的，每个节点最多能有2个元素，因此该节点无法再增加，而其父节点也含有两个元素，根节点只有一个元素。
于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
删除
以删除元素11为例，先自顶向下查找元素11的节点位置。
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子（左旋操作）。
B+ 树
B+树是B-树的一个变体，有着比B-树更高的查询性能。一个m阶的B+树（m的大小取决于磁盘页的大小）具有如下几个特征：
- 有k个子树的中间节点包含有k个元素（B-树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
注意，根节点的最大元素（上图中是15）等同于整个B+树的最大元素；由于父节点的元素都出现在子节点，因此所有叶子节点包含了全量元素信息，并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。
查找
在B-树中，无论中间节点还是叶子节点都带有卫星数据（索引元素所指向的数据记录），而Ｂ+树中间节点没有卫星数据，只有索引，这就意味着同样大小的磁盘页可以容纳更多节点元素，在相同的数据量下，B+树更加“矮胖”，IO操作更少。
下图以查找元素3为例，第一次磁盘IO：
第二次磁盘IO：
第三次磁盘IO：
B+树除了比B树更加“矮胖”这一点不同外，由于B+树的查询必须最终查找到叶子节点，而B-树中无论匹配元素处于中间节点还是叶子节点只要找到匹配元素即可，所以B+树的查找性能是稳定的，而B-树的查找性能不稳定（最好情况是只查根节点，最坏情况是查到叶子节点）。
范围查找
由于B+树的叶子节点构成了一条有序链表，因此B+树的范围查找比B-树简单得多，下面以查询范围为3到11的元素为例。
自顶向下，查找到范围的下限3：
通过链表指针，遍历到元素6、8：
通过链表指针，遍历到元素9、11，遍历结束：
总结
为了减少磁盘IO的次数，必须降低树的深度，将“瘦高”的树变得“矮胖，使得磁盘页可以容纳更多节点元素，因此出现了B-树。B+树是B-树的变体，相比B-树有以下优势：
- 单一节点存储更多的元素，使得查询的IO次数更少。
- 所有查询都要查找到叶子节点，查询性能稳定。
- 所有叶子节点形成有序链表，便于范围查询。
除了B-树和B+树，平时还会听到有B*树的概念，同样B*树是B+树的一个变体，相比B+树的不同之处如下：
- 将结点的最低利用率从1/2提高到2/3。
- 在B+树基础上，为非叶子结点也增加链表指针：B+树当一个结点满时，会分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；
B*树当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，而如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。