B树系列文章(3)--删除、更新操作(摘自老杨)

4.B树上的删除元组操作

假设B树的组织形式如图7。

删除索引键值为9的记录，执行流程：

1）以索引键值=9查询B树，定位要删除的元组，该元组位于叶子节点L1。

2）删除索引键值=9的入口项，10、16对应的记录向前移动一个位置。参照图8。

一般的文档上都会描述下溢节点，也就是说入口项占有率<50%（一般的设为50%），就会与兄弟节点进行合并，从而使所有节点的最小占有率≥50%。这样做的好处是显而易见的，维持B树在合理的深度。但是这样可能频繁的合并、分裂操作。

所以，大多数实际的B树不对下溢节点进行合并操作。

5.B树的更新操作

B树的更新操作，分为两种：

1）直接对数据进行更新；

2）分解为删除加插入操作。