Shulou(Shulou.com)05/31 Report--

This article will explain how to insert B-tree for you in detail. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

The insertion process is essentially the same as the tree construction process, that is, both insert operations and adjust the inserted B-tree.

We set the order of the B-tree to 5. A B-tree is constructed by using keyword sequence {1, 2, 6, 7, 11, 4, 8, 13, 10, 5, 9, 16, 20, 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-4.

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

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

There is a rule that the newly inserted node always appears on the leaf node, and then insert 4, 8, 13, and then insert directly to get the

Then insert 10. Get

Because there are five elements in the lower-right node, which exceeds the maximum number of 4, you need to split and upgrade the intermediate node 10 to join with 6 to form the following structure.

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

After inserting 20, after inserting 20, the number of elements in the lower right node is 5, exceeding the maximum number of 4. Therefore, 16 needs to be promoted to form the following structure.

After inserting 3, 12, 14, 18, 19, the following structure is formed.

Then insert 15, will cause 13 to promote to the root node, at this time, the root node will have 5 nodes, then 10 of the root node will be promoted again to form the following structure.

End.

This is the end of the article on "how to insert B-Tree". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.