Mysql-index-BTree type [simplified]

I have read a lot of summaries about B-TREE on the Internet, b-tree, B-tree, B+ tree, B* tree (why does Emma still have 4? She is almost confused),

Some of them are really exciting and admirable, but they are all too long. A long paragraph of text is daunting. Let’s just make a simplified version of the summary, introduce it in a simple and mobile way, and talk about their differences.
1. B-tree

##Binary Tree is a binary tree. (The formulas for K, h, and n will not be discussed here. If you are interested, you can search it yourself..)

(1) All non-leaf nodesHave at most two sons(Left and Right);

(2)All node storageA keyword；

(3) The left pointer of a non-leaf node points to less than its key The subtree of a word, the right pointer points to the subtree larger than its keyword; (Simply put, the left side of is smaller than itself, and the right side is larger than itself)

## Figure

B tree

#

#二.B-Tree

Balance Binary Tree --AVL tree [The B here actually means balance~]

(1) The depth of the left subtree and right subtree of the root node differs at most by 1.(This ensures that it will not occur The extreme phenomenon on the right side of the picture above)

(2) The left subtree and right subtree of the root node are both a balanced binary tree .

(3) All nodes have storage Keywords；

No matter what the inserted sequence is, we can build a balanced binary tree through adjustments to ensure that the balance factor of each node in the binary tree will not be greater than 1, Ensures that the depth of the tree reaches the shallowest, so the number of comparisons will be fewer and the time complexity will be reduced

Figure B-Tree

#三.B+tree

The search of B+ is basically the same as that of B-tree. The difference is that B+ tree only hits the leaf node (B-tree can hit non-leaf nodes)

(1) All keywords appear in the linked list of leaf nodes (dense index), and the keywords in the linked list happen to be ordered; ( Only the root node stores the keyword and the end of the tree has a value )

(2) Non-leaf nodes are equivalent to leaf nodes Index (sparse index), leaf nodes are equivalent to the data layer that stores (keyword) data. (Non-root node actually stores the index pointing to the root node)

(3 ) Because of the first two points, it is impossible to store data in non-leaf nodes. (The third difference between B-)
(4) The root node also has a chain pointer horizontally (it’s convenient to follow the clues quickly, but there is no such thing) Pointer, even if the next value is an adjacent neighbor, you have to run in a circle to get it)

Note that most of the index results we generally use, or the B-TREE structure we usually refer to, refer to the B+ structure~~

Picture B+Tree

## Four. B* tree
is the B+
tree Variants,

(1)B+The non-root and non-leaf nodes of the tree add pointers to brothers; [Compare to item 4 of B+ above, in the non-root The node also adds a horizontal linked list]

#Figure B * Tree

##5. Summary:

B tree: binary tree,

Each node Only one keyword is stored. If it is equal, it will hit. If it is smaller, it will go to the left node, if it is greater, it will go to the right node; (

But the B-tree may lead to different structures after multiple insertions and deletions ), for this reason, a balanced binary tree is generated after adding the balancing algorithm, also known as B-tree

##B-tree: Based on the B-tree, plus the balancing algorithm and multi-path search tree,

1. Each node stores M/ 2 to M keywords,

2. Non-leaf nodes store child nodes pointing to the keyword range;

3. All The keyword appears in the entire tree and only appears once,

4. Both leaf nodes and non-leaf nodes can be hit (whether data is stored);

##B+ tree: Based on B-tree,

1. Add a linked list pointer to the leaf node;

2. All keywords appear in leaf nodes,

3. Non-leaf nodes are used as indexes of leaf nodes;

4. The B+ tree always hits the leaf node;

B* tree : Based on the B+ tree, the linked list pointer is also added to the non-leaf nodes, and the minimum utilization of the node is increased from 1 /2 increased to 2/3;

# Question: B* is more efficient, but why do you think b* trees are used less? ????Or where is it useful? ? Maybe I still see too little. . Children's shoes who know something can learn from each other, please give me some advice, thank you in advance~

Answer: I recently learned that there is a person named Reiser4’s file system seems to use this structure. Its author Hans Reiser, killed his wife because she made him cuckold and was imprisoned, which directly affected the progress of the project. . .

Introduction:

Linux File System ReiserFS Author Hans Reiser was sentenced to 15 years in prison for murdering his wife. The development of ReiserFS has not stopped, although it has not yet been merged. Go to the Linux main branch. A small group of developers continues to work on the fourth version of ReiserFS (Reiser4 for short), and they released the new version last month. ##, supports Linux3.5.4 kernel. The above is the content of Mysql-index-BTree type [simplified]. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!

#