Application, addition and deletion of B-tree

B- Trees

B- The application of tree

B- Trees are suitable for Disk storage Application .

Because disk operation is compared with CPU Reading operation is time-consuming , and B- Compared with binary tree , There are fewer searches , More efficient .

Use an example to illustrate ：
If there is 1024 Data , If stored in binary tree , There will be 10 The height of the tree of the layer . Retrieving data from the root node to the leaf node requires multiple data comparison operations . In disk operation, the next node to find after each comparison is disk addressing . If If the level is higher , Will look for many times . relatively speaking B- The addressing times of the tree will be much less .（ Because a node contains multiple key value , In general, it will reduce the height of the tree ）.

B- The characteristics of the tree

One M rank B- Trees , The following conditions are met (M Order refers to the B- Trees are M Fork tree ):

1. Each node has at most M A daughter tree
2. The root node has at least two subtrees
3. Except for the root node , Each of the remaining branch nodes has at least M/2 A daughter tree
4. All the leaf nodes are on the same layer
5. Yes k The branch nodes of the subtree exist k-1 Key words , Keywords are sorted in ascending order
6. Outside the root node , The number of keywords meets ceil(M/2)-1 <= n <= M-1

Analyze these conditions :

This is a picture of 6 rank B- Trees

Conditions 1： such as （0012 0016 0022 0025 0028） This node , At most, you can only connect 6 Under the root line ;

Conditions 2 It's easy to understand

Conditions 3： Each branch node must have 3 And more than trees

Conditions 4： Leaf nodes are on the first floor , Maintain absolute balance .

Conditions 5： such as （0003 0006） This node has 2 Key words , It has 3 Subtree . Because there are three ranges , Corresponding to three subtrees . for example {x < 0003; 0003 < x < 0006; x > 0006} Three ranges .

Conditions 6： This 6 rank B- In the tree , The number of keywords meets 2≤n≤5.

Satisfy this 6 One condition is B- Trees .

B- Tree operation

Adding values

B- Adding values to a tree involves split operation . Because when the number of key words added to a node is equal to the order , It will be satisfied by splitting B- Properties of trees .

Or to 6 rank B- Trees, for example ：

from （0001 0002 0003 0004 0005） Add 0006 keyword ,

When the node exceeds 5 individual key When the value of , Will perform split operation .

Value deletion

B- The deletion of values in the tree involves Consolidation and borrowing operation .

With 6 rank B- Trees, for example ：

Merge operation

Delete 0001 keyword ,

Due to deletion 0001 after , This node has only 0002 A keyword , Not meeting the conditions 6, Therefore, it is necessary to merge .

Borrow operation

Delete 0002 keyword ,

Due to deletion 0002 after , This node has only 0003 A keyword , At this time, borrow the root node 0006, take 0007 Upgrade to root node .