B_树（B-Tree）是一种自平衡的多路搜索树，广泛用于数据库和文件系统中以高效管理大量数据

B_树（B-Tree）是一种自平衡的多路搜索树，广泛用于数据库和文件系统中以高效管理大量数据。以下是关于 m 阶 B_树的完整定义与相关特性：

1. m 阶 B_树的定义

一个 m 阶 B_树满足以下性质：

• 每个节点最多有 m 个子树；
• 根节点（若非叶子）至少有 2 个子树；
• 所有非根且非叶节点至少有 ⌈m/2⌉ 个子树；
• 每个非叶节点的结构为：(n, A₀, K₁, A₁, K₂, A₂, …, Kₙ, Aₙ)，其中：
  • n 是该节点中关键字的个数；
  • K₁ < K₂ < … < Kₙ 是关键字；
  • A₀ 是指向关键字小于 K₁ 的子树的指针；
  • Aᵢ 是指向关键字介于 Kᵢ 和 Kᵢ₊₁ 之间的子树的指针（i = 1 到 n−1）；
  • Aₙ 是指向关键字大于 Kₙ 的子树的指针；
• 关键字个数 n 满足：⌈m/2⌉ − 1 ≤ n ≤ m − 1；
• 所有叶节点位于同一层，表示查找失败的位置（外部节点），不存储实际数据。

示例：对于 4 阶 B_树，每个节点最多有 4 棵子树，最少（非根）有 ⌈4/2⌉ = 2 棵子树；关键字个数范围是 1 到 3。

2. 查找过程

B_树的查找从根节点开始，按如下步骤进行：

1. 在当前节点的关键字序列中使用二分查找目标值；
2. 若找到，则查找成功；
3. 若未找到，则根据关键字区间确定下一子树指针；
4. 递归或迭代进入对应子树继续查找；
5. 直到在某节点中找到目标，或到达空指针（即叶节点层）时失败退出。

由于 B_树是平衡树，所有叶节点在同一层，因此最坏情况下的查找路径长度为 O(logₘ N)，其中 N 是关键字总数，具有良好的时间性能。

3. 应用场景

B_树主要用于磁盘等外部存储系统的索引结构，原因包括：

• 多路分支减少树的高度，降低 I/O 次数；
• 平衡性保证操作效率稳定；
• 支持高效的插入、删除和查找操作；
• 常见变体如 B+ 树在数据库（如 MySQL 的 InnoDB 引擎）中广泛应用。

# 简化的 B_树节点类示例（Python）classBTreeNode:def__init__(self,m,is_leaf=False):self.max_children=m self.min_keys=(m+1)//2-1# ⌈m/2⌉ - 1self.is_leaf=is_leaf self.keys=[]# 存储关键字self.children=[]# 存储子节点指针defis_full(self):returnlen(self.keys)>=self.max_children-1

实现 B_树的插入操作需要遵循其结构特性，确保在插入新关键字后仍保持平衡。当节点的关键字数超过上限（m−1）时，必须进行节点分裂以维持 B_树的性质。

---

✅ B_树插入操作的基本步骤（m 阶）

1. 从根节点开始查找插入位置

   • 若树为空，则创建新的根节点，插入关键字；
   • 否则，递归向下查找应插入的叶节点。

2. 找到合适的叶节点进行插入

   • 插入操作总是在叶节点中进行（类似二叉搜索树）；
   • 在目标叶节点中按顺序插入关键字。

3. 检查是否违反最大关键字限制

   • 如果该节点的关键字个数 ≤ m−1：完成插入；
   • 如果 > m−1（即满了），则对该节点进行分裂处理。

4. 节点分裂（Split）过程
   假设一个节点有 m 个关键字（已满），需分裂为两个节点：

   • 取中间关键字K[⌈m/2⌉]作为提升关键字（升到父节点）；
   • 左子节点包含前 ⌈m/2⌉−1 个关键字；
   • 右子节点包含后 ⌊m/2⌋ 个关键字；
   • 原节点保留左半部分，新建右半部分节点；
   • 将中间关键字插入父节点，并添加指向新节点的指针；
   • 若父节点也满，则继续向上分裂，必要时创建新根。

5. 更新父节点或创建新根

   • 如果分裂传播到根节点，且根已满，则将根分裂，并新建一个根节点（树高+1）。

---

🔧 示例：4 阶 B_树插入与分裂

• m = 4 → 每个节点最多 3 个关键字，最多 4 棵子树；
• 最少关键字数：⌈4/2⌉ − 1 = 1；
• 当某节点有 4 个关键字时（超出 m−1=3），必须分裂。

分裂示例：

当前节点关键字为[10, 20, 30, 40]（已满）

[10, 20, 30, 40]

→ 中间位置是第 ⌈4/2⌉ = 2 个关键字 → 升级K₂ = 20到父节点
→ 左节点保留[10]
→ 右节点为[30, 40]
→ 原节点变为[20]并拆分为两孩子：

[20] / \ [10] [30, 40]

如果原节点是根节点，则此时生成新的根节点[20]，树高度加一。

---

💡 Python 简化代码框架（示意）

classBTreeNode:def__init__(self,m,is_leaf=True):self.m=m self.is_leaf=is_leaf self.keys=[]self.children=[]defis_full(self):returnlen(self.keys)>=self.m-1defsplit_child(parent,index):m=parent.m full_node=parent.children[index]mid=m//2# 分裂点索引（对于 m=4，mid=2）median_key=full_node.keys[mid]# 创建新节点（右半部分）new_node=BTreeNode(m,is_leaf=full_node.is_leaf)new_node.keys=full_node.keys[mid+1:]ifnotfull_node.is_leaf:new_node.children=full_node.children[mid+1:]# 修改原节点为左半部分left_keys=full_node.keys[:mid]ifnotfull_node.is_leaf:left_children=full_node.children[:mid+1]else:left_children=[]# 提取中间关键字并插入父节点parent.keys.insert(index,median_key)parent.children[index]=BTreeNode(m,is_leaf=full_node.is_leaf)parent.children[index].keys=left_keys parent.children[index].children=left_children parent.children.insert(index+1,new_node)definsert_non_full(node,key):i=len(node.keys)-1ifnode.is_leaf:# 直接插入并排序node.keys.append(None)whilei>=0andkey<node.keys[i]:node.keys[i+1]=node.keys[i]i-=1node.keys[i+1]=keyelse:# 找到子树位置whilei>=0andkey<node.keys[i]:i-=1i+=1child=node.children[i]ifchild.is_full():split_child(node,i)ifkey>node.keys[i]:i+=1insert_non_full(node.children[i],key)defbtree_insert(root,key):ifroot.is_full():# 根节点已满，创建新根m=root.m new_root=BTreeNode(m,False)new_root.children.append(root)split_child(new_root,0)insert_non_full(new_root,key)returnnew_rootelse:insert_non_full(root,key)returnroot

---

⚠️ 注意事项

• 插入总是发生在叶节点；
• 分裂可能自底向上传播；
• 树始终保持平衡，所有叶节点在同一层；
• 时间复杂度：O(logₘ N)，每次操作涉及 O(h) 次磁盘访问（h 为树高）。

---