【说明】博客内容选自课件内容

目录

1．B+树的结构特点

2．查找过程

3．插入操作

4．删除操作

---

1．B+树的结构特点

(1).  每个叶子结点中含有 n 个关键字和  n 个指向记录的指针；所有叶子结点彼此相链接构成一个有序链表，其头指针 sq 指 向含最小关键字的结点；

(2). 所有叶子结点都处在同一层次上，每个叶子结 点中关键字的个数均介于 ⌈m/2⌉和 m 之间。

(3). 每个非叶子结点可以看成索引表，其索引项为（ Ki , Ai ），其中关键字 Ki 为其相应指针 Ai 所指子树中关键字的最大值；

2．查找过程

 (1).  在 B+ 树上，既可进行顺序查找，也可进行缩小范围的按索引查找；

 (2).  在进行缩小范围的按索引查找时，不管成功与否，都必须查到叶子结点才能结束；

 (3). 若在结点内查找时，给定值≤Ki, 则应继续在 Ai 所指子树中查找；

3．插入操作

①B+树的插入仅在叶结点上进行。 每插入一 个(关键码-指针) 索引项后都要判断结点中的子树棵数是否超出范围。

②当插入后结点中的子树棵数大于 m 时, 需要将叶结点分裂为两个结点, 它们的关键码分别为 ⌈(m+1)/2⌉ 和 ⌊(m+1)/2⌋ 。

③它们的双亲结点中应同时包含这两个结点的最大关键码和结点地址。此后, 问题归于在非叶结点中的插入了。      

（这部分操作的理解关键在于实例演示，请参考课件）

4．删除操作

①B+树的删除仅在叶子结点上进行。当在叶子结点上删除一个(关键码-指针)索引项后, 结点中的子树棵数仍然不少于 ém/2ù，属于简单删除, 其上层索引可以不改变。

②如果删除的关键码是该结点的最大关键码, 但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用,所以上层的副本仍然可以保留。

③如果在叶结点中删除一个(关键码-指针)索引项后，该结点中的子树棵数 n 小于结点子树棵数的下限 ém/2ù，必须做结点的调整或合并工作。

实例1

实例2