Data structure – binary search tree, B+ tree, red black tree

• Simple summary of binary tree, binary search tree, B tree, B+ tree, red black tree
• B tree and B+ tree are analyzed in combination with index storage in database

Ref

• Basic introduction | the nuggets binary tree
• B and B + tree tree insert, delete, graphic explanation | Blog
• Interview the old enemy of red and black tree | the Denver nuggets

Binary tree

Overview

• In a binary tree, each node can have no more than two children.
• Binary trees are often used to implement binary search trees and binary heaps.
• One tree has a depth ofkAnd there is a2^k-1The binary tree of nodes is calledFull binary tree. This tree is characterized by the maximum number of nodes on each layer.
• withnThe depth of the complete binary tree of nodes isfloor(log2n)+1.
• Depth ofkA complete binary tree, at least2^(k-1)One leaf node, at most(2^k)-1A node.

Binary trees also include the following types

1. Complete binary tree — if the height of the binary tree ish, in addition to the firsthOutside the layer, the other layers (~ 1 h - 1) have reached the maximum number of nodes, nohA layer with leaves that run from left to right is a complete binary tree.
2. Full binary tree — a binary tree in which every node except leaf has left and right cotyledons and leaves are at the lowest level.
3. Balanced binary trees – Balanced binary trees are also known as balanced binary treesAVLTree (different from AVL algorithm), it is a binary sorting tree and has the following properties: it is an empty tree or the absolute value of the height difference between the left and right subtrees is not more than 1, and the left and right subtrees are both balanced binary trees.

Walk through the binary tree

There are three ways to traverse a binary tree

1. The first sequence traversal
2. In the sequence traversal
3. After the sequence traversal

The conclusion here is that by pre-ordering and middle-ordering, or middle-ordering and post-ordering, we can restore the original binary tree; But you can’t restore the original binary tree by preordering and postordering.

• Sequential traversal code implementation

Public static void preTraverseBTree(TreeNode rootTreeNode) {public static void preTraverseBTree(TreeNode rootTreeNode)if(rootTreeNode ! = null) {system.out.println (rootTreenode.getValue ()); / / access preTraverseBTree left node (rootTreeNode getLefTreeNode ()); / / access right node preTraverseBTree (rootTreeNode getRightNode ()); }}Copy the code

• Sequence traversal code implementation

/** * @param rootTreeNode */ public static voidinTraverseBTree(TreeNode rootTreeNode) {

        if(rootTreeNode ! = null) {// Access the left nodeinTraverseBTree(rootTreeNode.getLefTreeNode()); System.out.println(rootTreenode.getValue ())); // Access the right nodeinTraverseBTree(rootTreeNode.getRightNode()); }}Copy the code

Binary search tree

Binary search tree (BST) is characterized by

• It’s a binary tree
• The left child of the current root node is smaller than the root node
• The right child of the current root node is larger than the root node

In fact, the binary tree is mainly proposed to improve the search efficiency. For example, when the commonly used HashMap is dealing with serious hash conflicts, the search efficiency is reduced due to the excessively long zipper, so the red-black tree is introduced.

As we know, binary search can shorten the search time, but it requires that the search data must be in order. Every search, operation to maintain an ordered data set, so there is the concept of binary search tree. It can be seen that binary search trees are very suitable for searching and sorting numbers.

Dynamic binary tree creation (binary lookup tree)

In real life scenarios, it is common to encounter an array and convert it to a binary tree. In order to facilitate subsequent data sorting and searching, we generally create a binary search tree.

Code implementation ideas are also relatively simple

• If smaller than the current root node, place it to the left of the current root node
• If larger than the current root node, place it to the right of the current root node

Because it is created dynamically, you need a class to represent the root node.

public class TreeRoot {

    private TreeNode treeRoot;

    public TreeNode getTreeRoot() {
        return treeRoot;
    }

    public void setTreeRoot(TreeNode treeRoot) { this.treeRoot = treeRoot; }}Copy the code

The code implementation is shown below.

Public static void createTree(treeRoot treeRoot) public static void createTree(treeRoot treeRoot) Int value) {// If the root is empty (first access), use the first value as the root nodeif (treeRoot.getTreeRoot() == null) {
            TreeNode treeNode = new TreeNode(value);
            treeRoot.setTreeRoot(treeNode);

        } else{// Current root TreeNode tempRoot = treeRoot. GetTreeRoot ();while(tempRoot ! = null) {// The current value is greater than the root value, go rightif(value > temproot.getValue ()) {// If there is no root on the right, insert it directlyif (tempRoot.getRightNode() == null) {
                        tempRoot.setRightNode(new TreeNode(value));
                        return ;
                    } else{// If there is a root on the right, go to the root on the right tempRoot = temproot.getrightNode (); }}else{// There is no root on the left, so just insert itif (tempRoot.getLefTreeNode() == null) {
                        tempRoot.setLefTreeNode(new TreeNode(value));

                        return;
                    } else{// If there is a root on the left, go to the root on the left tempRoot = temproot.getLeftreenode (); } } } } }Copy the code

Finally, a test code is given for verification

Int [] arrays = {2, 3, 1, 4, 5}; TreeRoot root = new TreeRoot();for(int value : arrays) { createTree(root, value); } // preTraverseBTree(root.getTreeroot ()); System.out.println("--------------- sequential traversal tree"); // Middle order traversal treeinTraverseBTree(root.getTreeRoot());
    System.out.println("--------------- middle order traversal tree");
Copy the code

The output is

1, 2, 3, 4, 5 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the first sequence traversal tree 2 1, 3, 4, 5 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the sequence traversal treeCopy the code

Query the maximum value of the tree

For binary search tree, the middle order traverses the binary search tree, and the result is sorted according to the data size, so the maximum value of the tree can be directly obtained.

If a binary tree is not a binary lookup tree, how do YOU query the maximum value of the tree? You can use recursive thinking to achieve

1. Let’s look for the maximum value of the left subtree
2. And find the maximum value of the subtree on the right
3. Finally, the two maximum values are compared with the value of the root node

The code implementation is as follows.

** @param rootTreeNode */ public static int getMax(TreeNode rootTreeNode) {if (rootTreeNode == null) {
            return- 1; }else{/ / find out on the left side of the maximum int left = getMax (rootTreeNode. GetLefTreeNode ()); / / to find the right of the maximum int right = getMax (rootTreeNode. GetRightNode ()); Int currentRootValue = rootTreenode.getValue (); Int Max = left;if (right > max) {
                max = right;
            }
            if (currentRootValue > max) {
                max = currentRootValue;
            }

            returnmax ; }}Copy the code

Binary lookup tree performance

In the best case, the search efficiency of binary sorting tree is O(logn), and its access performance is approximately half search. But the worst case is O(n), such as when the inserted elements are ordered and the resulting binary sort tree is a linked list, in which case all the elements need to be traversed (see figure below).

If we can ensure that the binary sort tree does not have the extreme case mentioned above (the inserted elements are ordered, resulting in a linked list), we can guarantee high efficiency.

But this is not easy to control when inserting ordered elements, and by the definition of a binary sort tree, we can’t tell if the current tree needs to be adjusted.

So that’s where the balanced binary tree comes in.

Balanced binary trees

Balanced binary trees (AVL trees) are proposed to ensure that the tree is not too tilted, as much as possible to balance the two sides. So it’s defined as follows

1. A balanced binary tree is either an empty tree
2. Or make sure the difference between the height of the left and right subtrees is no more than 1
3. The subtree must also be a balanced binary tree

In other words, the height of the two left subtrees of the tree does not differ much.

Here, we move on to the binary sorting tree of the previous extreme case and now use it to construct a balanced binary tree.

With 12 as the root node, when 24 is added as its right subtree, the height difference between the left and right subtrees of the root node is 1, which is still balanced. At this time, another element 28 is added

At this time, the root node 12 felt unbalanced, I had no children on the left and two children on the right, exceeding the maximum 1 I said before, no, please adjust it for me!

So we need to adjust the current tree structure to rotate it.

Because the last node is added to the right subtree of the right subtree, you have to figure out how to feed the left subtree of the right subtree, so you have to rotate counterclockwise to make 24 the root node, and 12 right to make 24 the left subtree, and it looks like this

And then we’re back in equilibrium, and we’re adding 37 to 28 right subtrees, and we’re still in equilibrium

If you add another 30, it needs to be to the left of 37

And then we can see that the tree is unbalanced again, the tree with the root of 24 is obviously too heavy on the right, too thin on the left, and in order to maintain balance 24 has to give way to 28, and then it looks like this

Similarly, the balanced binary tree needs to rotate when adding and deleting to keep the whole tree balanced. After such a complicated internal work, when we use it, the time complexity of insertion and search is O(logn), which is quite good.

Red and black tree

Overview

Red-black tree (RED-Black tree) is a self-balanced binary search tree, which is a data structure used in computer science. It is typically used to implement associative arrays.

Red-black tree is essentially a binary search tree, but it adds an extra mark (color) on the basis of the binary search tree, and has certain rules. These rules allow red-black trees to be balanced, with worst-case complexity O(logn) for insertion, deletion, and lookup.

Its statistical performance is better than balanced binary trees (AVL trees), so red-black trees are used in many places. For example, in the Java Collections framework, many parts (HashMap, TreeMap, TreeSet, etc.) have red-black tree applications, and these collections provide good performance.

Since TreeMap is implemented by red-black tree, this paper will use the code of TreeMap related operations to analyze and demonstrate.

Red black tree features

First, add the term black height — the number of black nodes along the path from the root node to the leaf node, called the black height of the tree.

1. Every node is either red or black. Each node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black. All leaf nodes are black.
4. If a node is red, then both its children are black. Both children of each red node must be black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. The path from any node to each leaf node in the subtree contains the same number of black nodes.

One thing to note

• Property 3 specifies that every leaf node of a red-black tree is empty and all leaf nodes are black. But the Java implementation of red-black trees will be usednullTo represent empty nodes, so walking through a red-black tree will not see black leaf nodes, but instead see every leaf node is red.
• Property 4 means that there are no two consecutive red nodes on the path from each root to node, but black nodes can be consecutive. So given the number of black nodes N, the shortest path case is N consecutive black nodes and the height of the tree is zeroN - 1; The longest path has red and black nodes and the height of the tree is2(N - 1)
• Property 5 is the most important condition for being a red-black tree, and subsequent insert and delete operations are to comply with this rule.
• Red-black tree is not a standard balanced binary tree, it uses property 5 as a balancing method to improve its performance.

Red black tree left – right rotation

Left-right rotation of red-black tree is a relatively important operation. The purpose of left-right rotation is to adjust the structure of red-black node and transfer the position of black node, so that it can still maintain the five properties of red-black tree after insertion and deletion.

For example, the result of left-rotation of X is that the black node in the left subtree of Y goes to the right subtree of X.

Let’s take a look at left-right scroll down using code from TreeMap in the Java Collections framework

• Specify left rotation of node X

Private void rotateLeft(Entry p) {if(p ! = null) { Entry r = p.right; // p is x, r is y. // After left-spin, the right subtree of x becomes the left subtree of y βif(r.left ! = null) r.left.parent = p; //β confirms father as X. r.parent = P. parent; // The first step for y to replace X is to recognize X's father as his fatherif(p.parent == null) // If x has no parent, y is the oldest root node root = r;else if(p.parent.left == p) // If x has a father and is the left child of its father, the father of X now considers y to be the left child, not x;else// If x is the father's right child, the father will recognize y as the right child and discard x p.arent. right = r; r.left = p; // the old father x is now its left child. }}Copy the code

As you can see, the left rotation of the x node is turning x into the right child of y, and giving the left child of Y to X as the right subtree.

Simply put, left-rotation moves a node (β) from the right subtree to the left subtree.

• Specifies the right rotation of node Y.

private void rotateRight(Entry p) {
    if(p ! = null) { Entry l = p.left; p.left = l.right;if(l.right ! = null) l.right.parent = p; l.parent = p.parent;if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        elsep.parent.left = l; l.right = p; p.parent = l; }}Copy the code

In the same way, the right rotation of the y node is to turn y into the left child of x and give x the right child of X as the left subtree.

To simplify, right rotation moves a node (β) from the left subtree to the right subtree.

After understanding the methods and meanings of left-rotation and right-rotation, you can understand the main operations of red-black trees: insert and delete.

Balanced insertion in a red-black tree

Reference interview old enemy of red and black tree | the Denver nuggets.

Red black tree balance removed

Reference interview old enemy of red and black tree | the Denver nuggets.

B tree

Overview

B tree, also known as B- tree, is a multi – path balanced search tree. When we describe a B-tree, we need to specify its order, and the order tells us how many children there are at most in a node, and we usually use the letter M for order. When m is equal to 2, it’s our usual binary search tree.

A B-tree of order m is defined as follows

1. Each node has at mostm-1A keyword
2. The root can have at least one keyword
3. Non-root nodes have at least oneMath.ceil(m/2)-1A keyword
4. The keywords in each node are arranged in descending order, with all the keywords in the left subtree of each keyword being smaller than it and all the keywords in the right subtree being larger than it
5. All leaf nodes are in the same layer, or the length from the root to each leaf node is the same

The figure above is a B-tree of order 4. In practical applications, the order M of B-trees is very large (usually greater than 100), so the height of b-trees is still relatively small even if a large amount of data is stored.

Key words are stored in each node (key) and the corresponding data of the keyword (data), and the pointer to the child’s node. We’re going to have akeyAnd its correspondingdataIt’s called a record. However, for the sake of description, unless otherwise specified, it will be used in subsequent articleskeyTo take the place of(key,llenvalue)Key value pairs for this whole thing.

In the database, we use B tree (and B+ tree) as the index structure, which can speed up the query speed. At this time, key in the B tree represents the key, and data represents the logical address of the item corresponding to this key on the hard disk.

B tree insert operation

The insert operation refers to the insertion of a record, that is, the key-value pair of (key, llenValue). If a key-value pair already exists in the B tree, the value to be inserted is used to replace the old value. If the key does not exist in the B tree, it must be inserted into the leaf node.

1. If the number of key codes in this node is less thanm-1, directly insert (corresponding child node)
2. For example, the number of key codes in this node ism-1, will cause the node split. Split the node into two with the intermediate key as the boundary, create a new node, and insert the intermediate key into the parent node (h-1In the layer)
3. Repeat the previous two steps when inserting an intermediate keyword into the parent node. The worst case is to split all the way to the root, create a new root, and add another layer to the whole b-tree, as shown in the figure below.

As shown in the figure above, when trying to insert S into a fourth-order B-tree in the figure above on the left, the number of keywords of node NPQS after insertion is greater than 4-1, so it is split into NP and S, and the intermediate keyword Q is added to the parent node. Here, it is found that the number of keywords of the parent node also exceeds, so it is split again. Making Q the new root makes the height of the tree +1.

The following uses a fifth-order B-tree as an example to describe the insertion operation of a b-tree. In a fifth-order B-tree, a node has at most four keys and at least two keys.

1. Insert 39 into the empty tree

Now the root has only one key, and the root is also a leaf

2. Let’s go ahead and insert 22,97 and 41

The root node now has four keys

3. Continue to insert 53

After the insertion, the number of keywords exceeds the maximum allowed 4, so the key value is 41. The result is shown in the following figure. After the splitting, the pointer of the current node points to the parent node, which meets the b-tree condition. When the order m is even, there will be no key whose order is in the middle when splitting, so we can choose the key before the middle or the key after the middle as the center to split.

4. Inserting 13,21,40 in sequence also causes splitting, as shown in the figure below

5. Insert 30,27, 33; 36,35,34; 24,29, the results are shown in the figure below

(1) After inserting 30, 27 and 33, the corresponding node behaves as follows. At this time, the maximum number of keywords allowed is 4. The intermediate keyword 33 is split and promoted to the parent node

| | | 30 27 to 33 40 | | | 39Copy the code

(2) After inserting 36, 35, and 34, the corresponding node behaves as follows. At this time, the maximum number of keywords allowed is 4. The intermediate keyword 36 is split and promoted to the parent node

34 35 36 39 | | | | | | 40Copy the code

6. Insert the record whose key value is 26. The result is shown in the following figure

The current node needs to split around 27, carry 27 to the parent, and then point to the parent. The result is shown below.

After carrying, the current node (the root node) also needs to be split. The result of splitting is shown in the following figure.

After splitting, the current node points to the new root and no adjustment is required.

7. Finally, records with key 17,28,29,31,32 are inserted successively, and the results are shown in the figure below

In the code implementing b-tree, to make it easier to write the code, we can define the length of the array storing records in the node as M instead of m-1, so that when the node at the bottom inserts a record into the upper layer due to splitting, the upper layer has an extra place to store the record. Also, each node can store references to its parent, eliminating the need to write recursive programs.

In general, the node size is fixed for a certain M and a certain type of record, regardless of how many records it actually stores. However, the method of allocating fixed node size is wasteful, such as the node where key is 28 and key is 29, and there are two unused key positions, but it is impossible to insert any more values because the preceding key is 27 and the next key is 30, and all the integer values are used up. So if records are sorted by key size before being inserted into the B-tree, node utilization is low, at worst 50%.

Delete the B tree

The deletion operation deletes a record based on the key. If no record with the corresponding key exists in the B tree, the deletion fails.

1. If the current key to be deleted is on a non-leaf node, the key to be deleted is overwritten with a successor key, and then deleted in the child branch where the successor key resides. In this case, the subsequent key must be on the leaf node, the process is similar to the binary search tree to delete nodes. After deleting the record, perform step 2
2. The number of keys in this node is greater than or equal toMath.ceil(m/2)-1If no, go to Step 3.
3. If the number of sibling keys is greater thanMath.ceil(m/2)-1, the key in the parent node moves down to the node, and a key in the sibling node moves up. The deletion operation is complete.
4. Otherwise, the key in the parent node is moved down and merged with the key in the current node and its siblings to form a new node. The two child Pointers to the key in the original parent become one child pointer to the new node. Then the pointer to the current node points to the parent node. Repeat step 2.

Some nodes might have both a left sibling and a right sibling, so we can just pick any sibling and operate on it.

The following uses a fifth-order B-tree as an example to describe how to delete a b-tree. In a fifth-order B-tree, a node has at most four keys and at least two keys.

1. The original state

2. Delete 21 in the above B tree, the number of keywords in the node after deletion is still greater than equal 2, so the deletion is complete

3. Then delete 27 in the above case. We know from the figure above that 27 is in a non-leaf node, so we replace it with 27’s successor. As you can see from the figure, 27 is followed by 28. We replace 27 with 28, and then delete 28 from the right child of 28. The result after deletion is shown in the following figure

Found that after deleting the record of the leaf node number is less than 2, and there are 3 records in his brother nodes (the current node and a right brother, choose right brother will appear to merge nodes, no matter choose which one is ok, just finally B tree shape will be different), we can borrow a key from the brother nodes. So 28 in the parent goes down, 26 in the sibling goes up, and we’re done deleting. The result is shown below.

4. In this case, then remove 32, resulting in the following figure

When deleted, there is only one key in the current node and only two keys in its siblings. So we have to move the 30 from the parent down and merge it with the key from the two children, to make a new node, and the pointer to the current node points to the parent node. The result is shown below.

The number of keys in the current node meets the condition, so the deletion is complete.

5. In the above case, we then delete the record with key 40, and the result after deletion is as shown in the figure below

Similarly, the number of records in the current node is less than 2, and there are no more keys in the sibling node, so the key in the parent node moves down and is merged with the sibling (we chose the left sibling here, but we can also choose the right sibling), and the merged pointer to the current node points to the parent node.

Similarly, for the current node, we have to continue merging, and the result is as follows.

After merging, the current node meets the conditions, and the deletion is complete.

B + tree

Overview

B+ trees are a type of tree data structure commonly used in databases and file systems of operating systems. The characteristic of B+ tree is that it can keep the data stable and orderly, and its insertion and modification have relatively stable logarithmic time complexity. B+ tree elements are inserted from the bottom up, as opposed to binary trees.

A B+ tree is a balanced search tree designed for disks or other direct access assistive devices. In a B+ tree, all the record nodes are stored in the leaf nodes of the same layer in order of the size of the key values, and the Pointers to the leaf nodes are connected.

The definition of B+ tree varies from data to data. One way to define B+ tree is to have the same number of keywords and children. Here we take the approach defined in Wikipedia, where the number of keywords is 1 less than the number of children, which is basically equivalent to b-trees. This is a B+ tree of order 4.

In addition, B+ trees have the following requirements

1. B+ trees contain two types of nodes: internal nodes (also known as index nodes) and leaf nodes. The root itself can be either an internal node or a leaf node. The root node can have at least one keyword.
2. The biggest difference between A B+ tree and a B tree is that the internal nodes do not store data, but are only used for indexes. All data (or records) are stored in leaf nodes.
3. M order B+ tree means that there are at most internal nodesm-1The order m also limits the maximum number of records stored in leaf nodes to M-1.
4. For a key in an internal node, all keys in the left tree are smaller than it, and all keys in the right subtree are greater than or equal to it. Records in leaf nodes are also arranged by key size.
5. Each leaf node has a pointer to neighboring leaf nodes, and the leaf nodes themselves are linked in order of the size of the key word.

B+ tree insertion

1. If it is an empty tree, create a leaf node and insert the record into it. The leaf node is also the root node.
2. For leaf type nodes: find the leaf node based on the key value and insert records into the leaf node. After the insertion, if the number of keys in the current node is less than or equal to m-1, the insertion ends. Otherwise, split the leaf node into left and right leaf nodes, with the left leaf node containing the frontm/2The right node contains the rest of the records and sets them/2+1The key of a record is carried into the parent (The parent must be an index type nodeThe left child points to the left node, and the right child points to the right node. Point the pointer to the current node to the parent node, and then perform step 3.
3. For nodes of index type: if the number of keys in the current node is less than or equal tom-1, the insertion ends. Otherwise, split the index type node into two index nodes, with the left containing the front(m-1)/2Three keys. The right node containsm-(m-1)/2A key, will be the firstm/2The left child of the key carried to the parent refers to the left, and the right child of the key carried to the parent refers to the right. Point the pointer to the current node to the parent node, and repeat step 3.

The following is the insertion process of a fifth-order B-tree. The nodes of fifth-order B-number have at least 2 keys and at most 4 keys.

1. Insert 5 into the empty tree

2. Insert 8,10,15

3. Insert 16

After inserting 16, the number of keywords exceeded the limit, so split. When the leaf node is split, two records of the split left node and three records of the split right node are recorded. The middle key becomes the key of the index node. After splitting, the current node points to the parent node (root node). The result is shown below.

Note that the split parent node (shown in gray) is an index node and is not responsible for storing data, so data 10 still needs to be stored in the right child node.

Of course, there’s another way to split it, give the left node three records, the right node two records, and then the key in the index node becomes 15.

4. Insert the 17

5. Insert 18, as shown in the figure below

If the number of keywords in the current node is greater than 5, the node is split. Split into two nodes, left node 2 records, right node 3 records, keyword 16 carry into the parent node (index type), the current node pointer to the parent node.

If the number of keywords of the current node meets the condition, the insertion is complete.

6. After inserting some data

7. Insert a 7 in the figure above, and the result is shown below

The current node has more than 4 keywords and needs to be split. The left node has two records and the right node has three records. After splitting, keyword 7 enters the parent node and points the pointer of the current node to the parent node. The result is shown in the figure below.

The current node has more than 4 keywords and needs to be split. The left node has two keywords and the right node has two keywords. Keyword 16 enters the parent node and points the current node to the parent node. The result is shown in the figure below.

If the number of keywords of the current node meets the condition, the insertion is complete.

B+ tree deletion

If there is no corresponding key in the leaf node, the deletion fails. Otherwise, perform the following steps

1. Delete the corresponding key from the leaf node. If the number of keys in a node is greater than or equal toMath. Ceil (m - 1) / 2-1If no, go to Step 2.
2. If the sibling key has a surplus (greater thanMath. Ceil (m - 1) / 2-1), borrow a record from the parent node, and replace the parent node with the borrowed key. Otherwise, go to Step 3.
3. If no spare key in brother nodes, the nodes and brothers merged into a new leaf node, and deletes the key from the parent node (the parent node of the key children on both sides of the pointer becomes a pointer, pointing to the new leaf node), the current point to the parent node (will) for the index nodes, Perform step 4 (after step 4, the operation is exactly the same as the B-tree, mainly to update the index node).
4. If the number of keys in an index node is greater than or equal toMath. Ceil (m - 1) / 2-1“, the deletion is complete. Otherwise, go to Step 5
5. If the sibling node has a surplus, the parent node key moves down, the sibling key moves up, and the deletion is complete. Otherwise, go to Step 6
6. The current node is merged with its siblings and parent nodes by moving down the key to form a new node. Point the current node to the parent and repeat step 4.

Note that after B+ tree deletion, the key existing in the index node does not necessarily have the corresponding record in the leaf node.

The following is the process of deleting a b-tree of order 5, where nodes of order 5 have at least 2 keys and at most 4 keys.

1. The initial state

2. Delete 22, and the result is shown below

If the number of keys in leaf nodes is greater than or equal to 2, the deletion is complete

3. Delete 15, and the result after deletion is shown in the figure below

After deletion, the current node has only one key, which does not meet the condition, while the sibling node has three keys. You can borrow a record with the key of 9 from the sibling node, and update the key of the parent node from 10 to 9. The deletion is complete.

4. Delete 7, and the result after deletion is shown in the figure below

Current node number is less than 2, keyword (left) also don’t have the luxury of brother nodes keyword (right of the current node has a brother, but analysis select any one is ok, here we select the left), so the current nodes and brothers merged, and deletes the key from the parent node, the node points to the parent node.

At this point, the number of keywords in the current node is less than 2, and there is no surplus of keywords in the sibling node, so the keywords in the parent node move down and merge with the two child nodes, as shown in the figure below.

MySQL index and B+ tree

• MySQL index principle and slow query optimization | Meituan technology