11.4.2 B+树 一、B+树的结构特点 B+树是B树的一种变型树,其结构和B树的差异在于: (1) B+树的每个叶子结点中含有 n 个索引项(即 n 个关键码和 n 个指针);并且,所有叶子结点彼此相链接构成一个有序链表,该有序链表的头指针指向含最小关键码的结点; (2) B+树上每个非叶结点中的关键码 Ki 是其相应指针 Ai 所指子树的索引项,即该关键码为该子树中关键码的最大值; (3) 一棵m阶的B+树中每个结点至多含 m 个关键码(即至多有 m 棵子树),除根结点至少含2个关键码外,其余结点至少含m/2个关键码,所有叶子结点都处在同一层次上。 例如右图为一棵深度为3的4阶B+树。 二、B+树的操作 在B+树上,既可以进行从根结点开始的缩小范围的查找,也可以从最小关键码开始进行顺序查找;在进行缩小范围的查找时和B树稍有不同,不管查找成功与否,都必须查到叶子结点才能结束,在结点内进行查找时,若给定值≤Ki,则应继续在 Ai 所指子树中进行查找。在B+树上进行插入和删除索引项时,则类似于B树,必要时也需要进行结点的"分裂"或"合并"操作,分裂和合并的规则和B树相同。 |
4阶B+树示例 |