一、为什么要B树
一般来说，索引本身也很大一般不存在内存中，而是以索引文件的形式存储在磁盘上。
1. 主存存取原理
目前计算机使用的主存基本都是随机读写存储器（RAM），其抽象结构如下：
主存的存取过程如下：
1）读：当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。
2）写：写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。
2. 磁盘存取原理
磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。
3. 局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理。程序运行期间所需要的数据通常比较集中。
局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的，在B树中可以检查多个子结点，由于在一棵树中检查任意一个结点都需要一次磁盘访问，所以B树避免了大量的磁盘访问。
二、B-树
1. 简介
1) 一个 m 阶的B-树满足以下条件：
2) 每个结点至多拥有m棵子树；
3) 根结点至少拥有两颗子树（存在子树的情况下）；
4) 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
5) 所有的叶结点都在同一层上；所有叶节点具有相同的深度，也就是说 B-Tree 是平衡的；
6) 有 k 棵子树的分支结点则存在 k-1 个关键码（子树在关键码之间生成），关键码按照递增次序进行排列；
7) 关键字数量需要满足ceil(m/2)-1 <= n <= m-1；（ceil向下取整）
2. 插入
假定对高度为h的m阶B-树进行操作。
新结点一般插在第h层，通过搜索找到对应的结点进行插入，那么根据即将插入的结点的数量又分为下面几种情况。
1）如果该结点的关键字个数没有到达m-1个，那么直接插入即可；
2）如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。
3. 删除
同样的，我们需要先通过搜索找到相应的值，存在则进行删除，需要考虑删除以后的情况，
1）如果该结点拥有关键字数量仍然满足B树性质，则不做任何处理；
2）如果该结点在删除关键字以后不满足B树的性质（关键字没有到达ceil(m/2)-1的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况。
（1）如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
（2）如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为ceil(m/2)-1，借的一方的关键字数量为ceil(m/2)-2的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；
3）其余情况参照BST中的删除。
三、B+树
B-树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫。而B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可。
1. 简介
以一个m阶树为例：
1) 根结点只有一个，分支数量范围为[2，m]；
2) 分支结点，每个结点包含分支数范围为[ceil(m/2), m]；
3) 分支结点的关键字数量等于其子分支的数量减一，关键字的数量范围为[ceil(m/2)-1, m-1]，关键字顺序递增；
4) 所有叶子结点都在同一层。
2. 操作
其操作和B树的操作是类似的，不过需要注意的是，在增加值的时候，如果存在满员的情况，将选择结点中的值作为新的索引，还有在删除值的时候，索引中的关键字并不会删除，也不会存在父亲结点的关键字下沉的情况，因为那只是索引。
四、总结
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点。
所以通常B-树用于文件索引，而B+树则常用于数据库索引。
1. 关键字的数量不同
B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用（由于是索引，所以有多少索引就有多少的子节点数据），但是B-树虽然也有m个子结点，但是其只拥有m-1个关键字。
2. 存储的位置不同
B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据；但是B-树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
3. 分支结点的构造不同
B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
4. 查询不同
B-树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。