An introduction to B trees
B tree is a balanced multipath search tree, which is used for file system and database implementation.
B tree, B tree, B tree are all equivalent.
For B trees, the value of order M in order M in order B tree is the maximum degree of the node in the whole tree.
Observing the above B trees, we can find some common characteristics:
 A node can store more than 2 elements and have more than 2 child nodes.
 Has some properties of binary search tree;
 Balance: all subtrees of each node are the same height;
 Are short.
Properties of Morder Btrees (M ≥2)
Suppose a node stores x:
 The node is the root node: 1 ≤ x ≤ m − 1
 Node is nonroot node:
┌
m/2┐
− 1 ≤ x ≤ m − 1
Chrysene said upward take the whole, that is, ceiling

If the node has a child node, the number of child nodes y = X + 1 root node: 2 ≤ Y ≤ m Nonroot node: chrysene M /2 gp ≤ Y ≤ m
So if m is equal to 3, 2 ≤ y ≤ 3, we could call it a (2, 3) tree, or a 23 tree if m is equal to 4, 2 ≤ y ≤ 4, we could call it a (2, 4) tree, or a twothreefour tree
The special case, when m = 2, is the binary search tree.
B tree is used in the database, and m is usually 200 to 300.
B tree versus binary search tree
B trees and binary search trees are logically equivalent. A super node can be obtained by merging multiple generations of nodes. The supernode merged in the second generation has at most four child nodes (at least fourthorder Btree). The super node with the merging of 3 generations has a maximum of 8 child nodes (at least 8order Btree); The super node merged in the n generation has at most 2N child nodes (at least 2n order Btree).
M order B tree, at most log2m generation merge.
Common operations on B trees
B tree search
Similar to binary search tree search, B tree search ideas are as follows:
 Elements are searched from small to large inside the node.
 If yes, the search ends.
 If no, search for the element in the corresponding child node and repeat Step 1.
As shown in figure 4 btree, search element 51:1) First search elements inside the root node, compare the size of 51 > 39, enter the right subtree of 39 for search; 2) Search inside the node (59, 79, 94), 51 < 59, enter the left subtree of the node for search; 3) Search inside the node (49, 51, 54), 51 > 49, find the next value inside the node, find 51 == 51 inside the node, find the element, and end the search.
Add B tree
The new element must be added to the leaf node.
According to the current number of leaf node elements, the position of the inserted leaf node can be divided into two situations: for morder Btree: 1) If the number of elements in this node is less than M1, it can be directly inserted. 2) If the number of elements in this node is equal to m1, the node will be split. Additional operations need to be done, which will be classified later.
The following is the corresponding analysis of the above two cases:
If the number of elements in a node is less than M1, insert the node directly.As shown below:
The number of elements in a node is equal to m minus 1, which overflows.
Overflow refers to that after an element is inserted into a node, the number of elements in the node exceeds the maximum number of elements in the node set by the Btree.
As shown in the figure below, element 90 is inserted into the thirdorder Btree. After it is inserted into node Z, the number of elements in node Z is now 3, exceeding the upper limit 2 (i.e., 31) of the number of elements in node limited by thirdorder Btree. Now it overflows.
The solution to the overflow caused by adding is to merge the middle elements of the overflow node upward, and split the left and right parts of the middle elements into the left and right nodes of the upshifted merged elements. The specific splitting steps are as follows: First, the number of elements of the overflow node must be equal to M, and M is the order value of the B tree; Assume that the position of the middle element of the overflow node is K; Merge the element at position K upward with the parent node; Split the element at k position into 2 child nodes; And make these two child nodes children of the element of the upshifted element.
The number of elements of the two child nodes must not be lower than the minimum limit (chrysene m/2 gp − 1).
After a split, the parent node can overflow, and in the most extreme cases, it can split all the way to the root node.
Each overflow node is processed according to the above steps and finally recovered.
Similarly, insert element 90 into the third order B tree above:
 Query the position of the node where 90 should be inserted, between nodes Z (85, 95);
 Judge the number of elements in the node where the elements are inserted. Node Z originally had two elements (for thirdorder Btree: 2 = 31), but after insertion it had exceeded its limit (31 = 2), and an overflow occurred.
 Overflow node (node Z), the middle element 90 is merged with the parent node upward, and the child nodes 85 and 95 of 90 before merging upward are classified as the child nodes of 90 after merging upward.
 When 90 moves up to the node Y after merging, the number of elements is 3 (3 > 31), which also exceeds the number of its limited elements, resulting in overflow. Merge the middle element 75 of node Y upward with the parent node (root node 35 in the figure), that is, repeat step 3.
 Finally split to the root node, complete the problem of adding overflows, restore to a thirdorder Btree.
The whole process is shown in the figure below:
Delete the B tree
The deletion of elements in B tree can be classified into two categories. The nodes where the deleted elements are located are leaf nodes and nonleaf nodes.
 Delete elements on leaf nodes
 If the number of original leaf node elements is greater than
ceil(m/2)  1
(that is, after deleting a>= ceil(m/2)  1
) deletes the element directly;  If the number of original leaf node elements is less than or equal to
ceil(m/2)  1
(That is, after deleting one< ceil(m/2)  1
) :
2.1 The number of sibling elements is greater than or equal toceil(m/2)  1
, then: An element of the parent node moves down, and an element of the sibling node moves up to the parent node, and the deletion is complete
2.2 The number of sibling elements is less than or equal toceil(m/2)  1
, then: an element in the parent node moves down, and merges the element down with the elements of the current node and its siblings to form a new node, and the two child Pointers of the elements in the original parent node become a child pointer pointing to the new node. In this case, after the element of the original parent node moves down, the original parent node may also overflow. You need to continue operations until the location is restored.
 Delete elements on nonleaf nodes
 Replacing the value of the element to be deleted with a successor element and then deleting the successor element from the node where the successor element is located (similar to deleting nodes in a binary search tree) translates to deleting the element above on the leaf node.
The following examples show the deletion process in the above cases:
The deleted element is in the leaf node, and the number of elements of the original leaf node is greater than Ceil (M /2) 1: in the upper part of the 4th order B tree as shown in the following figure, element 11 is deleted (leaf node, and the number of node elements 3 is greater than Ceil (4/2) 1). Therefore, element 11 can be directly deleted (the lower part of the following figure).
The deleted element is on the leaf node, and the number of elements of the original leaf node <= ceil(m/2) 1, and the number of elements of the sibling node > ceil(M /2) 1.
In the upper left part of the btree of order 4 below, element 5 is deleted. After deletion, the number of elements of this node is 0, less than the lower limit 1 (Ceil (4/2) 1). At this time, the number of sibling nodes on its right is 3 (greater than Ceil (4/2) 1), and element 7 in the parent node moves down to the current node. At the same time, the element 9 in its right sibling is moved up to the parent node, as shown in the lower left part of the figure below. The final display results are shown in the right half of the figure below.
The deleted element is on the leaf node, and the number of elements of the original leaf node <= ceil(m/2) 1, and the number of elements of the sibling node <= ceil(m/2) 1.
As shown in Figure 5 btree, delete element 27:
The number of elements on the node where element 27 is located is 2 < (ceil(5/2) 1 = 2), and the number of elements on its sibling node is also <= 2. Therefore, element 25 of its parent node moves down, and the downwardmoving combination, the node and a sibling node are combined, and the adjustment ends. As shown below:
After adjustment, the effect picture is as follows:
Delete element on nonleaf node:
As shown in the figure below, element 22 is deleted from the fifthorder Btree (the node is nonleaf node).
Replace the value with the successor node element 23 and delete the successor node element 23 as shown below:
At this point, it is translated into the deletion of leaf nodes (the number of node elements <= Ceil (m/2) 1, and the number of sibling node elements 3 > Ceil (5/2) 1). So the parent element 23 moves down, while its sibling 21 moves up. As shown below:
After the final adjustment, the effect picture is as follows: