B+树及插入和删除操作详解

本节介绍一种应文件系统所需而生的一种 B-树的变型树——B+树。前面介绍了B-树，B+树其实同B-树有许多相同之处，本节将用B-树同B+树通过对比两者的差异来介绍B+树。 什么是B+树？ 一颗 m 阶的 B+树和 m 阶的 B-树的差异在于： 有 n 棵子树的结点中含有 n 个关键字； 在上一节中，在 B-树中的每个结点关键字个数 n 的取值范围为⌈m/2⌉ -1≤n≤m-1，而在 B+树中每个结点中关键字个数 n 的取值范围为：⌈m/2⌉≤n≤m。 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 所有的非终端结点（非叶子结点）可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。 例如，图 1 中所示...阅读全文