Data Structures Algorithms 简明教程
B Trees
B 树是针对 m 路搜索进行了专门优化的扩展二分搜索树，因为 B 树的阶为“m”。树的阶定义为一个节点最多可以容纳的子节点数。因此，b 树的高度相对较低，低于 AVL 树和 RB 树的高度。
B trees are extended binary search trees that are specialized in m-way searching, since the order of B trees is 'm'. Order of a tree is defined as the maximum number of children a node can accommodate. Therefore, the height of a b tree is relatively smaller than the height of AVL tree and RB tree.
它们是二分搜索树的一般形式，因为它包含多个键和两个子项。
They are general form of a Binary Search Tree as it holds more than one key and two children.
B 树的各种属性包括 -
The various properties of B trees include −
-
Every node in a B Tree will hold a maximum of m children and (m-1) keys, since the order of the tree is m.
-
Every node in a B tree, except root and leaf, can hold at least m/2 children
-
The root node must have no less than two children.
-
All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level.
-
A B tree always maintains sorted data.
B 树还广泛用于磁盘访问，因为它高度较低，减少了磁盘访问时间。
B trees are also widely used in disk access, minimizing the disk access time since the height of a b tree is low.
Note - 磁盘访问是计算机磁盘的内存访问，信息存储在其中，磁盘访问时间是系统访问磁盘内存所花费的时间。
Note − A disk access is the memory access to the computer disk where the information is stored and disk access time is the time taken by the system to access the disk memory.
Basic Operations of B Trees
B 树中支持的操作为插入、删除和搜索，每个操作的时间复杂度为 O(log n) 。
The operations supported in B trees are Insertion, deletion and searching with the time complexity of O(log n) for every operation.
Insertion operation
B 树的插入操作类似于二叉搜索树，但将元素插入相同节点中，直至达到最大键。使用以下过程执行插入：
The insertion operation for a B Tree is done similar to the Binary Search Tree but the elements are inserted into the same node until the maximum keys are reached. The insertion is done using the following procedure −
Step 1 - 计算最大 $\mathrm{\left ( m-1 \right )}$ 和最小 $\mathrm{\left ( \left \lceil \frac{m}{2}\right \rceil-1 \right )}$ 的键，一个节点可以保留的键的数量，其中 m 表示 B 树的顺序。
Step 1 − Calculate the maximum $\mathrm{\left ( m-1 \right )}$ and, minimum $\mathrm{\left ( \left \lceil \frac{m}{2}\right \rceil-1 \right )}$ number of keys a node can hold, where m is denoted by the order of the B Tree.
Step 2 - 使用二进制搜索插入将数据插入到树中，一旦键达到最大数量，节点将分成两半，中键成为内部节点，而左右键成为其子节点。
Step 2 − The data is inserted into the tree using the binary search insertion and once the keys reach the maximum number, the node is split into half and the median key becomes the internal node while the left and right keys become its children.
Step 3 - 所有叶子节点必须在同一层。
Step 3 − All the leaf nodes must be on the same level.
键 5、3、21、9、13 根据二进制搜索属性全部添加到节点中，但如果我们添加键 22，则它将违反最大键属性。因此，节点分成两半，中键移动到父节点，然后继续插入。
The keys, 5, 3, 21, 9, 13 are all added into the node according to the binary search property but if we add the key 22, it will violate the maximum key property. Hence, the node is split in half, the median key is shifted to the parent node and the insertion is then continued.
在插入 11 时也会出现另一次小故障，因此节点被分成两半，中键移动到父级。
Another hiccup occurs during the insertion of 11, so the node is split and median is shifted to the parent.
在插入 16 时，即使将节点分成两部分，父节点也溢出，因为其达到最大键数。因此，先拆分父节点，中键成为根。然后，将叶节点分成两半，叶节点的中键移动到其父级。
While inserting 16, even if the node is split in two parts, the parent node also overflows as it reached the maximum keys. Hence, the parent node is split first and the median key becomes the root. Then, the leaf node is split in half the median of leaf node is shifted to its parent.
插入所有元素后，将实现最终的 B 树。
The final B tree after inserting all the elements is achieved.
Deletion operation
B 树中的删除操作与二叉搜索树的删除操作略有不同。从 B 树中删除节点的过程如下：
The deletion operation in a B tree is slightly different from the deletion operation of a Binary Search Tree. The procedure to delete a node from a B tree is as follows −
Case 1 - 如果要删除的键位于叶节点中并且删除不违反最小键属性，则只需删除该节点。
Case 1 − If the key to be deleted is in a leaf node and the deletion does not violate the minimum key property, just delete the node.
Case 2 - 如果要删除的键位于叶节点中，但删除违反了最小键属性，则向其左兄弟节点或右兄弟节点借一个键。如果两个兄弟节点都具有相同数量的最小键，则将节点合并到其中任何一个中。
Case 2 − If the key to be deleted is in a leaf node but the deletion violates the minimum key property, borrow a key from either its left sibling or right sibling. In case if both siblings have exact minimum number of keys, merge the node in either of them.
Case 3 - 如果要删除的键位于内部节点中，则用其左子节点或右子节点中的键替换该键，具体取决于哪个子节点具有更多的键。但是，如果两个子节点都具有最小数量的键，则它们会被合并在一起。
Case 3 − If the key to be deleted is in an internal node, it is replaced by a key in either left child or right child based on which child has more keys. But if both child nodes have minimum number of keys, they’re merged together.
Case 4 - 如果要删除的键位于内部节点中，违反了最小键属性，并且其子节点和兄弟节点都具有最小数量的键，则合并子节点。然后，将其兄弟节点与父节点合并。
Case 4 − If the key to be deleted is in an internal node violating the minimum keys property, and both its children and sibling have minimum number of keys, merge the children. Then merge its sibling with its parent.
