Introduction to the B-Tree Insertion Process

In the previous article https://www.jb51.net/article/154153.htm we introduced the properties of B-tree. In this article we will introduce the insertion process of B-tree.

The insertion process and the tree construction process are essentially the same, that is, both perform insertion operations and adjust the B-tree after insertion.

We set the order of the B-tree to 5. Construct a B-tree using the key sequence {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}.

Because the order of the tree is 5, each node has at most 5 child nodes, and the number of keywords in each node is 3 to 4.

So, the first step is to insert 1, 2, 6, 7 as a node.

Then insert 11 and get 1, 2, 6, 7, 11. Because the number of nodes exceeds 4, the node needs to be split. Select the middle node 6 and promote it to the parent node, so we get:

There is a rule that newly inserted nodes always appear on leaf nodes. Then insert 4, 8, and 13 directly, and you get

Then insert 10. We get

Because there are 5 elements in the lower right node, which exceeds the maximum number of 4, it needs to be split and the middle node 10 is promoted to be together with 6 to form the following structure.

Then insert 5, 17, 9, 16, and get the following

Then insert 20. After inserting 20, the number of elements in the lower right node is 5, which exceeds the maximum number of 4. Therefore, 16 needs to be increased to form the following structure

Then insert 3, 12, 14, 18, and 19 to form the following structure.

Then inserting 15 will cause 13 to be promoted to the root node. At this time, the root node will have 5 nodes. Then, 10 in the root node will be promoted again, forming the following structure.

Finish.

Summarize

The above is the full content of this article. I hope that the content of this article will have certain reference learning value for your study or work. Thank you for your support of 123WORDPRESS.COM. If you want to learn more about this, please check out the following links