B+树

B+树是B树的变形树，更适合与文件索引系统

1 B+树和B树的区别

一棵m阶的B+树和m阶的B树的差异在于： 1. 有n棵子树的结点中含有n个关键字；（B树是含有n-1个关键字） 2. 所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接： 3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

2 B+树的查找、插入和删除

B+数的查询、插入、删除，最终都要到叶子结点

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。 1. 查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。B+树查找的分析类似于B树。B+树不仅能够有效地查找单个关键字，而且更适合查找某个范围内的所有关键字。例如，在B+树上找出范围在[a,b]之间的所有关键字值。处理方法如下：通过一次查找找出关键字a,不管它是否存在，都可以到达可能出现a的叶子结点，然后在叶子结点中查找关键字值等于a或大于的那些关键字，对于所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。如果在当前结点中没有发现大于b的关键字，就可以使用当前叶子结点的最后一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于b的关键字，才停止查找。 2. 插入：仅在叶子结点上进行插入，当结点中的关键字个数大于m时要分裂成两个结点，平分关键字，并且，它们的双亲结点中应同时包含这两个结点中的最大关键字。 3. 删除：B+树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于[m/2]时，其和兄弟结点的合并过程亦和B树类似。