1.B树简介

在B树上进行查找时，由于B树是作为索引文件而驻留在磁盘上的，因此查找B树上的一个节点实际对应一次对硬盘的访问。为减少访问磁盘的次数，需尽可能降低树的高度，即增加阶数。

B树主要用于大型文件的索引，因大型文件中的记录是无序的，因此，建立的索引是稠密索引，即文件中的每个记录对应一个索引项。有如下两个操作：

（1）添加记录时，将记录加在文件末尾，把索引项添加到B树中。

（2）删除文件记录时，无需真正删除该记录，只需删除B树中的索引项即可。

这种组织形式下，记录的插入和删除比较方便，但要根据关键字的次序访问所有的文件记录，效率是很低的。因为每个记录的访问都必须在B树中先找到它的存储地址。因此，如果文件有N个记录，对应的B树必须被访问N次。而且因为是稠密索引，每个记录一个索引项，导致B树占用的空间比较大。

2.B+树简介

B+树也是B树的一种。

如果一个文件既能支持每个记录的随机访问，也能支持对整个文件按序访问，这样的文件称为索引顺序文件。

B+树是既能实现快速的随机访问，又能实现快速顺序访问的索引结构。

M阶的B+树的性质：

（1）根或者是叶子，或者有2～M个儿子。

（2）除根之外所有节点都有不少于[M/2]且不多于M个儿子。

（3）有k个儿子的节点保存了k-1个键来引导查找，键i代表了子树i+1中键的最小值。

（4）叶节点的儿子指针指向存储记录的数据块的地址。对于索引B+树，它们是叶节点。但对于数据块来说，它们又是数据块的父节点。数据块才是真正的叶节点。而B树中，叶节点的儿子指针都是空指针。

（5）每个数据块至少有[L/2]个记录，至多有L个记录。

2.1.B+树的操作

主要有以下三种操作。

2.1.1.B+树的查找

和二叉查找树类似，在B+树上查找某一条记录也是从根节点开始，根据节点中的键值决定查找哪一棵子树。一层一层往下找，直到找到该记录存放的数据块。在数据块中查找被查记录，找到了则表示查找成功，没有找到则表示该记录不存在。

2.1.2.B+树的插入

插入也与二叉查找树类似。

当插入的数据块已满的时候，现在这个数据块有L+1个元素，可以把它分裂成两个数据块。索引节点也需要做相应的修改，必要时也需要对索引节点进行分裂。

2.1.3.B+树的删除

删除时，首先找到存储被删除的节点，然后在节点中删除它。如果删除后当前数据块不符合规定，则需要对数据块进行调整：如果邻居节点的记录数不是最少，则借一个过来；如果邻居节点的记录数也是最少，则把两个节点合并成一个节点。

3.使用场景

主要用于文件系统以及数据库做索引。

数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题,正是为了解决这个问题,B+树应用而生.B+树只需要去遍历叶子节点就可以实现整棵树的遍历.而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。