二、B+树

1、B+树的概念
    B+树是B树的一种变形树，它与B树的差异在于：
    有k个子结点的结点必然有k个关键码；
    非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。

2、B+树的查找
    跟B树的查找类似，但是也有不同。由于跟记录有关的信息存放在叶结点中，查找时若在上层已找到待查的关键码，并不停止，而是继续沿指针向下一直查到叶结点层的关键码。此外，B+树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。上面两种方式结合起来，使得B+树非常适合范围检索。

3、B+树的插入
    B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。

4、B+树的删除
    B+树中的关键码在叶结点层删除后，其在上层的复本可以保留，作为一个"分解关键码"存在，如果因为删除而造成结点中关键码数小于 ，其处理过程与B树的处理一样。

不同于B树只适合随机检索，B+树同时支持随机检索和顺序检索，在实际中应用比较多。