Comics: What is a B-tree?

— — — — — —

Binary search tree structure:

Disk I/O for the first time:

Second disk I/O:

Third disk I/O:

Fourth disk I/O:

The following is a detailed description of the B-tree. A M-order B-tree has the following characteristics:

1. The root node has at least two children.

2. Each intermediate node contains K-1 elements and K children, where m/2 <= k <= m

3. Each leaf node contains K-1 elements, where M /2 <= k <= m

4. All leaf nodes are in the same layer.

5. Elements in each node are arranged from small to large, and k-1 element in the node is exactly the range division of elements contained by K children.

Disk I/O for the first time:

Locate in memory (compared with 9) :

Second disk I/O:

Locate in memory (compared with 2,6) :

Third disk I/O:

Locate in memory (compared with 3 and 5) :

Looking at the node position of 4 from the top down, we find that 4 should be inserted between node elements 3 and 5.

Nodes 3 and 5 are already two-element nodes and cannot be added. Parent nodes 2 and 6 are also two-element nodes and cannot be added. The root node 9 is a single-element node that can be upgraded to a two-element node. Split nodes 3,5 and 2,6, and upgrade root node 9 to two-element node 4,9. Node 6 is independently the second child of the root node.

Finds the node position of element 11 from the top down.

After 11 is deleted, node 12 has only one child, which does not meet b-tree specifications. So find the median of 12,13, and 15,13, and replace node 12, which itself moves down to become the first child. (This process is called sinistral rotation)