B+ super tree helps you know the underlying structure of MySQL

B Trees

B- Trees (B Trees )

The tree and B+ The biggest difference between trees is , All nodes of the tree store data .
Before learning , Find out first B The characteristics of the tree :

1. M rank B A tree indicates that a node can store at most M Child node
2. Each node has at most M-1 Elements
3. Specify that each node must have at least two child nodes , And the elements of each node are arranged in ascending order

B The rules that a tree needs to know when storing elements at a node are : Continuously store elements until the maximum number of elements can be stored in the node , Once the element storage limit is exceeded , First simulate the storage location , Then raise the middle element , As shown in the figure above .
When we fill a node with four elements , And then put in 53, Because it's a fifth order tree , No more storage , Can only be simulated and stored in 41 and 97 Between , Then, the middle element of the node is promoted , That is to say 41, Let's talk about the remaining nodes 41 The left and right children of the node .

B+ Trees

B+ Trees and B- There are two differences between trees : Non leaf nodes only store indexes , The leaf node can be indexed through this index , secondly , Leaf nodes are stored in a linked list structure , In this way, the child can find other leaf nodes through one leaf node , Don't index again .

When inserting data, it is also similar to B- The tree is like a retreat , Only when the node element is full , Let's talk about how to raise the index of a node .

application

Two kinds of B In fact, the most commonly used tree is on the disk IO Yes , You can think of each node as a disk block , Then you can find the corresponding disk according to the range and brush it , Reduce the number of disk retrievals . common MySQL The bottom layer is to use B+ Tree structure , Why not B- Trees , Because B- Each node of the tree stores data , So if you want to index the data of the leaf node , All nodes in front of the leaf node must be able to go through , In the process of walking through , We have to take out the data for comparison , To find the corresponding disk according to the range , And in the process of getting data , It will produce the operation of brushing the disc , In this way, the number of leaf nodes is increased in order to find them IO The number of times . therefore MySQL Used B+ Trees , Do not store data on non leaf nodes , Instead, it stores the index that can find the leaf node , The leaf node is the real data storage node (MyISAM The attentive storage is also the index ), In this way, every time we index leaf nodes, we don't have to brush the disk of non leaf nodes , Reduce IO frequency .