钓鱼网站网址大全网站建设合同详细

B树的插入

原树：

插入key后，若导致原节点关键字数超过上限，则从中间位置（$\lceil \frac{m}{2}\rceil$）将关键字分成两部分，左部分包含的关键字放在原节点中，右部分包含的关键字放到新节点中，中间位置（$\lceil \frac{m}{2}\rceil$）的节点插入原节点的父节点




若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根节点为止，进而导致B树高度+1

B树的删除

若被删除关键字在终端节点，则直接删除该关键字；若在非终端节点，则用直接前驱或直接后继来替代被删除的关键字
（直接前驱：当前关键字左侧指针所指子树中最右下的元素；直接后继：当前关键字右侧指针所指子树中最左下的元素）

若被删除关键字所在节点删除后的关键字个数低于下限，则需要与其右（或左）兄弟借，需要调整该节点的兄弟节点与双亲节点。比如下图当右兄弟很宽裕时，用当前节点的后继、后继的后继来填补空缺

下图示例为当左兄弟很宽裕时，用当前节点的前驱、前驱的前驱来填补空缺

当兄弟不够借时，将关键字删除后与左（或右）兄弟节点及双亲节点中的关键字进行合并。






如上，在合并过程中，双亲节点中的关键字个数会-1，若其双亲节点是根节点且关键字个数减少到0，则直接删除根节点，合并后的新节点成为根。若双亲节点不是根节点，且关键字个数减少到$\lceil \frac{m}{2}\rceil -2$，则又要与它自己的兄弟节点进行调整和合并操作，并重复上述步骤，直至符合B树要求