B+树

在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的阶数是m，则除了根之外的每个节点都包含最少「m/2」 个元素最多 「m-1」个元素，对于任意的结点有最多 m 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大链接。

查找

查找以典型的方式进行，类似于[二叉查找树]。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是来确定这个位置。

插入

节点要处于违规状态，它必须包含在可接受范围之外数目的元素。

1. 首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
2. 如果没有节点处于违规状态则处理结束。
3. 如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则创建一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不小于最大数的一半。

删除

1. 首先，查找要删除的值。接着从包含它的节点中删除这个值。
2. 如果没有节点处于违规状态则处理结束。
3. 如果节点处于违规状态则有两种可能情况：
   1. 它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
   2. 它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

注解

假定 L 是节点允许拥有子节点的最小数目，而 U 是最大数目。则每个节点总是有在 L 和 U 之间（包含它们在内）个子节点，除了一个例外：根节点有从2到U（包含它们在内）个子节点。换句话说，根节点豁免于低边界限制，而拥有它自己的低边界2。这允许树持有小数目的元素。根有一个子节点没有意义，因为附着在这个子节点上的子树可以简单的附着在根节点上。允许根节点没有子节点也是不需要的，因为没有元素的树典型的表示为没有根节点。
wiki