Data Structures Algorithms 简明教程
B Trees
B 树是针对 m 路搜索进行了专门优化的扩展二分搜索树，因为 B 树的阶为“m”。树的阶定义为一个节点最多可以容纳的子节点数。因此，b 树的高度相对较低，低于 AVL 树和 RB 树的高度。
它们是二分搜索树的一般形式，因为它包含多个键和两个子项。
B 树的各种属性包括 -
-
B 树中的每个节点最多容纳 m 个子项和 (m-1) 个键，因为树的阶为 m。
-
B 树中的每个节点（除根节点和叶节点外）至少可以容纳 m/2 个子节点
-
根节点必须至少有两个子节点。
-
B 树中的所有路径都必须在同一级别结束，即叶子节点必须在同一级别。
-
B 树始终维护排序后的数据。
B 树还广泛用于磁盘访问，因为它高度较低，减少了磁盘访问时间。
Note - 磁盘访问是计算机磁盘的内存访问，信息存储在其中，磁盘访问时间是系统访问磁盘内存所花费的时间。
Insertion operation
B 树的插入操作类似于二叉搜索树，但将元素插入相同节点中，直至达到最大键。使用以下过程执行插入：
Step 1 - 计算最大 $\mathrm{\left ( m-1 \right )}$ 和最小 $\mathrm{\left ( \left \lceil \frac{m}{2}\right \rceil-1 \right )}$ 的键，一个节点可以保留的键的数量，其中 m 表示 B 树的顺序。
Step 2 - 使用二进制搜索插入将数据插入到树中，一旦键达到最大数量，节点将分成两半，中键成为内部节点，而左右键成为其子节点。
Step 3 - 所有叶子节点必须在同一层。
键 5、3、21、9、13 根据二进制搜索属性全部添加到节点中，但如果我们添加键 22，则它将违反最大键属性。因此，节点分成两半，中键移动到父节点，然后继续插入。
在插入 11 时也会出现另一次小故障，因此节点被分成两半，中键移动到父级。
在插入 16 时，即使将节点分成两部分，父节点也溢出，因为其达到最大键数。因此，先拆分父节点，中键成为根。然后，将叶节点分成两半，叶节点的中键移动到其父级。
插入所有元素后，将实现最终的 B 树。
Deletion operation
B 树中的删除操作与二叉搜索树的删除操作略有不同。从 B 树中删除节点的过程如下：
Case 1 - 如果要删除的键位于叶节点中并且删除不违反最小键属性，则只需删除该节点。
Case 2 - 如果要删除的键位于叶节点中，但删除违反了最小键属性，则向其左兄弟节点或右兄弟节点借一个键。如果两个兄弟节点都具有相同数量的最小键，则将节点合并到其中任何一个中。
Case 3 - 如果要删除的键位于内部节点中，则用其左子节点或右子节点中的键替换该键，具体取决于哪个子节点具有更多的键。但是，如果两个子节点都具有最小数量的键，则它们会被合并在一起。
Case 4 - 如果要删除的键位于内部节点中，违反了最小键属性，并且其子节点和兄弟节点都具有最小数量的键，则合并子节点。然后，将其兄弟节点与父节点合并。
