Illustration of the insertion process of b+ tree

B+ Trees are common in modern databases , If we know it , It may be better for performance optimization in work ！

I've been thinking about B+ What determines the height of a tree . Know I understand B+ Tree insertion process , There is a feeling of sudden enlightenment ！

Some information on the Internet is disorderly , Different databases may also have pairs B+ Trees have different implementations . But everything is the same ,B+ The definition of a tree , It's roughly as follows ：

To sum up ,B+ Under the tree 5 An important feature .

1. B+ The tree contains 2 Kinds of nodes ：
   1. Internal nodes （ Also called index node ） And leaf nodes .
   2. The root node itself can be an internal node , It can also be a leaf node .
   3. The minimum number of keywords in the root node can be 1 individual .
2. B+ Trees and B The biggest difference in the tree is that the internal nodes do not save data , Index only , All the data （ Or record ） All stored in leaf nodes .
3. m rank B+ The tree indicates that there are at most m-1 Key words （ Or internal nodes have at most m Subtree ）, Order m At the same time, the maximum storage of leaf nodes is limited m-1 A record .
4. In the internal node key All in order from small to large , For one of the internal nodes key, All in the left tree key All smaller than it , In the right subtree key Are greater than or equal to it . The records in the leaf node are also in accordance with key The size of .
5. Each leaf node has a pointer to the adjacent leaf node , Leaf nodes themselves are linked in large order according to the size of keywords .

According to the above characteristics , Let's see B+ Tree insertion process .

1. Below is a tree 5 rank B+ Tree insertion process ,5 rank B+ The tree has the least nodes 2 individual key, most 4 individual key.

2. Insert again 3 Index keywords ,8,10,15.

3. Then insert keywords 16.

B+ Tree node key Value reached 5, Now the split condition is met . So we need to split nodes .
Insert 16 After the number of keywords exceeded the limit , So split up . When leaf nodes split , Suppose the split left node has 2 A record , Right node has 3 A record , middle key Become... In the index node key, Will become a parent node , Both split nodes point to the parent node （ Root node ）.

4、 Suppose we insert 17 This keyword .

 

  Be careful , Nodes are ordered .

5、 then , Let's insert another 18.

here , We find the node on the right , The splitting condition is satisfied , So we have to split .

 

Before and after division , The keywords on the node remain in order .
That's it , When we plug in again 10 After data , The assumed structure is as follows ：

 

 

  when , The number of keywords in the root node exceeds 4, It needs to be split . After the split , Left node 2 Key words , Right node 2 Key words , keyword 16 Go to the parent node , Point the split node to the parent node , The results are shown in the following figure .

  And so on , When the inserted data meets the node split, it will be split . But after division , Keywords are ordered .
According to this insertion process , One B+ The height of the tree , How many keywords can a node store , That is, the index determines . Usually , A tree MySQL Of B+ Trees , Tree height is 3 Words , About hundreds of millions can be saved . If the height of the tree is too high , Query efficiency will be greatly reduced ！