晋中市网站建设_网站建设公司_Oracle_seo优化

B-树的插入与删除操作需严格维护其结构平衡性。在插入时，首先将关键字插入到合适的叶节点中，若该节点关键字数量超过上限 $ m-1 $，则进行“分裂”：取中间关键字上移至父节点，原节点以中间关键字为界拆分为两个子节点。若分裂传递至根节点且导致根满，则根分裂并生成新的根，树高加一。删除操作时，若关键字位于非叶节点，则用其中序后继替代并转为对叶节点的删除；若删除后节点关键字个数小于最小要求 $ \lceil m/2 \rceil - 1 $，则通过左兄弟或右兄弟“借”关键字，若兄弟也无法借用，则与兄弟及父节点中的分隔关键字合并，可能导致合并后的节点继续向上合并，甚至树高减一。

哈希表是一种基于映射关系的存储结构，其核心是哈希函数 $ H(key) $，它将任意关键字转换为地址空间内的索引值，从而实现快速存取。理想情况下查找时间复杂度为 $ O(1) $。但由于哈希函数输出空间有限，不同关键字可能映射到同一地址，产生冲突。常见的冲突解决方法包括链地址法（拉链法）和开放定址法（如线性探测、平方探测）。为减少冲突，应设计分布均匀的哈希函数，并保持较低的装载因子。
当B-树中某节点的关键字个数超过 $ m-1 $（即最大允许关键字数）时，需对该节点进行分裂操作，以维持B-树的结构特性。具体步骤如下：

1. 确定分裂位置：
   将该节点中的 $ m $ 个关键字按升序排列（插入后已有序），选取中间关键字（第 $ \lceil m/2 \rceil $ 个关键字，即索引为 $ \left\lfloor \frac{m}{2} \right\rfloor $ 的关键字）作为上移关键字。

2. 拆分左右两部分：

   • 中间关键字左侧的 $ \lceil m/2 \rceil - 1 $ 个关键字保留在原节点中；
   • 右侧的 $ \lfloor m/2 \rfloor $ 个关键字构成一个新节点；
   • 若该节点是非叶节点（有子树），则其 $ m+1 $ 棵子树也需一并分割：前 $ \lceil m/2 \rceil $ 棵子树归属原节点，后 $ \lfloor m/2 \rfloor + 1 $ 棵子树归属新节点。

3. 中间关键字上移至父节点：
   将选出的中间关键字插入到父节点中的合适位置，并将新节点的指针作为右子树连接到父节点中。若父节点因此也超过了 $ m-1 $ 个关键字，则递归执行分裂，直至根节点。

4. 若根节点分裂：
   当根节点发生分裂时，创建一个新的根节点，将上移的关键字作为新的根，原根分裂为两个子节点。此时树的高度增加一层。

⚠️ 注意：分裂操作保证了每个节点的关键字个数始终满足 $ \lceil m/2 \rceil - 1 \leq n \leq m-1 $，从而保持B-树的平衡性。

# 示例伪代码表示分裂过程（以m=5为例）defsplit_node(node):mid=len(node.keys)//2# m=5时，mid=2，第3个关键字上移separator=node.keys[mid]left_keys=node.keys[:mid]# 前半部分保留right_keys=node.keys[mid+1:]# 后半部分新建节点left_children=node.children[:mid+1]ifnotnode.is_leaf()elseNoneright_children=node.children[mid+1:]ifnotnode.is_leaf()elseNonenew_right_node=BTreeNode(keys=right_keys,children=right_children)# 更新当前节点node.keys=left_keys node.children=left_childrenreturnseparator,new_right_node