查找——B+ 树

想要了解更多的动态查找，可以看一看前面的文章

B+树

是应文件系统的需要而构造的一种 B-树的变形树。

与 B-差异

一棵 m 阶的 B+树和 m 阶的 B-树的差异在于:

(1)有 n 棵子树的结点中含有 n 个关键字。

(2)所有的叶子结点中包含全部关键字字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序连接。

(3)所有的非终端结点可以看成是索引部分，结点中含有其子树中最大(或最小)关键字。

B+树查找有两种方式:

• 一种是从 sqt 开始按关键字从小到大顺序查找；

• 另一种是从根结点 Root 开始，进行随机查找。在 B+树上进行随机查找、插入、删除的过程与 B-树类似。只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。在 B+树上插入仅在叶子结点上进行，当结点中的关键字个数大于 m 时要分裂成两个结点，它们所含关键字个数都为【m+1 /2】。并且，它们的双亲结点中应同时包含这两个结点中最大关键字。在 B+树上删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于【m/2】时，其和兄弟结点的合并过程和 B-树类似。

B+树相比于其他方法不是很常用，了解即可。