B tree and b+ tree

---

One 、 B Trees

1、B The concept of tree

B A tree is an absolutely balanced multiway lookup tree ,B The maximum number of subtrees of all nodes in the tree is called B The steps of the tree , use m Express . One m Step B If the tree is not null, The following properties must be satisfied ：

• The number of each node in the tree is m-1 Key words , At most m Kezi tree .
• Except for the root node , All non leaf nodes contain at least [m/2]-1 Key words , So at least [m-2] Kezi tree .（ Leaf nodes are all null）.
• The root node keyword can be less than [m/2]-1, There can be no subtree , If there is a subtree, at least 2 individual , because B Trees are absolute Balance tree , The height difference is 0.
• The non leaf node structure is ：
  [ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-1NTkptFU-1655360655348)(C:\Users\ZhaLeMaoDeMao\AppData\Roaming\Typora\typora-user-images\image-20220615105523125.png)]

k Represent keyword , also k1 < k2 < k3 ······< kn

p Represents the subtree pointed to on both sides of the keyword .

problem n Keywords m rank B Trees ：

1、 How many leaf nodes are there

n+1

2、 What's the minimum height

The fattest tree is the smallest , That is, each node satisfies the maximum keyword m-1

m^h

Height	The maximum number of nodes	Maximum number of keywords
1	1	$5^1$ -1
2	5	$5^2$ -1
3	25	$5^3$ -1
h	$m^h$	$m^h$-1

therefore The minimum height is $m^h$-1 >= n

namely h >= $\log_m (n+1)$

3、 What is the maximum height

The thinnest tree is the largest , That is, each node has the minimum number of key words [m/2]-1, Each layer meets the minimum number of points [m/2], Set the minimum number of nodes as k, Then the number of key words is k-1.

Height	The minimum number of nodes	Minimum number of key words
1	1	1
2	2	5=4+1
3	6	17=12+4+1
h	2$k^{h-2}$	2$k^{h-2}$(k-1)

therefore h The number of high keywords is 1+2（$k^0$+ $k^1$+$k^2$········$k^{h-2}$ ）*（k-1）<= n

Simplify to ：1+2（$k^{h-1}$ -1）<=n

h <= $\log_k\frac{n+1}{2}$+1

2、B Insertion of trees

Mainly in the process of division , If you don't need to split, just put it in .

Split method ：

​ 1、 From the middle, that is [m/2] The position of the split , Divide keywords into two parts , The keyword on the left is still in the original node , The keyword on the right is placed on the new node of the same layer , The middle position is inserted into the parent node of the original node .

​ 2、 If after the previous step , The parent node has exceeded the upper limit of keywords , Split the parent node , Until it reaches The root node , If The root node also exceeds the limit , The root node continues to split , Generate a new root node , The height of the tree plus one .

Demonstrate the insertion process ： First , Declare a fifth order B Trees

One 、 Insert 30、40、20、60

Two 、 Continue to insert 40, It needs to split up , First, follow the above Split method 1 perform , And then execute Split method 2, Generate a new root node

3、 ... and 、 Continue to insert 23、28

Four 、 Continue to insert 25, Split up , according to Split method 1.

5、 ... and 、 Continue to insert 22、24、26、29

6、 ... and 、 Continue to insert 21、27、 At this time The root node keyword has reached the maximum value

7、 ... and 、 Continue to insert 55、70

8、 ... and 、 Continue to insert 80, here The rightmost subtree splits ,60 Move to the parent node , But the position of the parent node has reached the maximum , Split again to produce a new root node .

3、B Delete tree

1、 if B The deleted node of the tree is located in the terminal node , And the number of key words of the node Greater than [m/2]-1, Then delete it directly .

2、 if B The deleted node of the tree is located in the terminal node , But the number of key words in this node be equal to [m/2]-1, Then to the sibling node （ Left or right ） Node keyword Greater than [m/2]-1 The node of borrows a keyword , But it is not borrowed directly, but Take the node of the parent node , There are three situations

​ 2.1、 Keyword of the deleted node Are smaller than the parent node , Only the right brother , take The smallest keyword of the parent node Put it in that position , The smallest keyword of the right brother Put it in the parent node .

​ 2.2、 Keyword of the deleted node Are larger than the parent node , Only the left brother , take The largest keyword of the parent node Put it in that position , Left brother's biggest keyword Put it in the parent node .

​ 2.3、 The keyword of the deleted node is located in The middle of the parent node , There are right brothers , And left brother , If you borrow from brother youyou , In fact, that is 2.1; If you borrow from brother Zuo , In fact, that is 2.2.

3、 if B The deleted node of the tree is located in the terminal node , And the number of keywords in this node is equal to [m/2]-1, The keyword of the sibling node adjacent to the node is also equal to [m/2]-1, Add the keywords in the parent node to the current node and adjacent nodes （ Split keywords ） A merger . If the merge results in the parent node keyword being less than [m/2]-1, Then traverse upward with the parent node , All the way to the root .

4、 If the keyword to be deleted is not in the terminal node , Then use the Direct precursor perhaps Direct follow-up Instead of keywords , Up to the terminal node , Turn the problem into a terminal node .

​ Direct precursor ： Current keyword The left node is the rightmost Key words of .

​ Direct follow-up ： Current keyword The leftmost node on the right Key words of .

Demonstration process ： B The tree is shown in the figure below ：

One 、 Delete 42, Compliance 1 , Delete directly

Two 、 Delete 33, Compliance 2

3、 ... and 、 Delete 29, Compliance 3

Four 、 Delete 35, Corresponding situation 4

5、 ... and 、 Delete 40, Corresponding situation 2, Move the split node down , The maximum value of the left sibling node moves up

Two 、B+ Trees

1、B+ The concept of tree

B+ Trees and B The trees are very similar , First look at The same thing ：

• The root node has at least one element

• Non root node range ：[m/2] <= k < = m-1

Difference ：

• B+ Treelike Only leaf nodes store data , Non leaf nodes do not store data , This is the B The biggest difference about trees .
• 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 .
• 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 .
• The parent node holds the index of the first element of the right child .

2、B+ Insertion of trees

​ B+ Trees and B The insertion of trees is very similar , The difference is

When the number of node elements is greater than m-1 When , Split into two parts according to the middle element , The intermediate elements are split to the parent node for index storage , however , The middle element itself splits the right part , Leaf nodes are connected by pointers .

Demonstrate the insertion process ： First declare a 5 rank B+ Trees

One 、 Insert... In turn 10、20、30、40

Two 、 Insert 50 , Split up

3、 ... and 、 Continue to insert 45、60, Split up

3、B+ Delete tree

With the above B Trees are like , A little different .

1、 The number of nodes is greater than [m/2] Delete directly , If the parent node keyword points to the node where the deleted keyword is located , Update parent node index .

2、 Number of deleted nodes be equal to [m/2], Elements of sibling nodes Greater than [m/2], The leaf node has a pointer , When borrowing elements from sibling nodes , No need to go through the parent node , Instead, you can move directly through the sibling node , Then update the index of the parent node .

3、 The number of deleted nodes is equal to [m/2], And the sibling node element is not greater than [m/2], Then merge the current node and the sibling node , Then update the index of the parent node .

Example ： Make a statement 5 rank B+ Trees

One 、 The initial is as shown in the figure

Two 、 Delete 60, Just delete it

3、 ... and 、 Delete 45, Need merger , And update the parent node keyword （ Actually, it was deleted ）

Four 、 Delete 25

summary

B+ Trees are relative to B Trees have some advantages , It can be summed up in the following points .

• A single node stores more elements , Make the query IO Fewer times , So it makes it more suitable to be a database MySQL The underlying data structure of .
• All queries need to find leaf nodes , Query performance is stable , and B Trees , Each node can find data , So it's not stable .
• All the leaf nodes form an ordered list , It's easier to find .