B tree and b+ tree

B Trees

B A tree is a multi-path balanced lookup tree . Key value pairs stored in each node , Index and data .m rank B The definition of a tree ：

Each node has at most m Child node , At most m-1 Key words , At least m/2 Key words .（ The root node can have at least one element ）

The keywords in each node are sorted from small to large , All keywords in the left subtree of each keyword are smaller than it , All keywords in the right subtree are larger than it .

All leaf nodes are on the same layer .

B Tree insertion ：

When a keyword is inserted into a node , If the number of keywords in the node is less than or equal to m-1, Insert complete , Otherwise, put the keyword in the middle of the node into the parent node , The left and right parts are split into the left and right subtrees of the parent node .

Example ： stay 5 rank B In the tree , Nodes have at most 4 Key words , There are at least two keywords ：

Insert 23,25,39：

At this time, the keyword of the left subtree has been greater than 4 A the , It needs to be split ：

B Tree delete ：

In the first place to find B Elements to be removed from the tree , If the element is in B There is... In the tree , Then delete the element in its node ; After deleting this element , First, judge whether the element has left and right child nodes , If there is , Move up a similar element in the child's node (“ Left child's rightmost node ” or “ The leftmost node of the right child ”) Go to the parent node , And then the situation after the move ; without , Delete directly .

Delete the element in the leaf node ：

• After deletion, the number of elements in the node is less than m/2, We need to see whether a neighboring brother node is full ;
• If it's full , Then borrow an element from the parent node , Then the first or last element of the adjacent node moves up to the parent node ;
• If none of their neighbors is full , That is, the number of nodes is equal to m/2, Then the node and its adjacent sibling node “ Merge ” Become a node ;

B+ Trees

m rank B+ Trees ：

Each node has at most m Child node , Each subtree corresponds to a keyword , At most m Key words , At least m/2 Key words .

And B The difference between trees ：

1.B+ The data of the tree is stored in the leaf node , Internal nodes do not store data , Store index only . therefore B+ The query time complexity of the tree is fixed as logn, and B The query time complexity of the tree is not fixed , And key The position in the tree is related to , Best for O(1).B+ Because the internal nodes of the tree only store indexes , Therefore, each node can index a larger range ,B+ Trees are more suitable for external storage .

2. Each leaf node has pointers to adjacent leaf nodes , All leaf nodes are linked from small to large according to the size of keywords . It is very suitable for range query .

3. The parent node has the first keyword of each child node .

B+ Tree insertion ：

When the number of node elements is greater than m-1 when , Split into two parts according to the middle element , The intermediate element is split into the parent node and stored as an index , But the middle element itself is still split on the right .

Example ：5 rank B+ Tree species , Minimum nodes 2 Elements , most 4 Elements . Insert 5,10,15,20：

Insert 25, At this time, the number of elements is greater than 4 A the , split ：

Then insert 26,30, Continue to split ：

Reference resources ：

​ ​https://segmentfault.com/a/1190000020416577​​

​ ​https://blog.csdn.net/weixin_43156699/article/details/117216784​​

​ ​https://blog.csdn.net/qq_34515959/article/details/109155630​​

​ ​https://blog.csdn.net/a519640026/article/details/106940115​​