Shulou(Shulou.com)06/02 Report--

This article introduces what is the difference between B-Tree and B+Tree in MySQL. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

The node of B-Tree is a binary array [key,data]. Key is the key of recording, and data is the data corresponding to the key. Each node in B-Tree can contain a lot of keyword information and branches according to the actual situation. Each node has a pointer around each key. The pointer of non-leaf node points to the node of the next layer, and the pointer of leaf node is null, as shown below:

When you want to find a value, you will start with the root node. Each key of the root node has two pointers left and right, through which you can access the next node. Each lookup will compare the lookup value with the key value, according to the comparison results to find the appropriate pointer to enter the next layer node, and finally, repeat, finally find the corresponding value or the value does not exist.

To supplement the knowledge of the disk, when the system reads data from the disk to memory, it takes the disk block (block) as the basic unit, and the data located in the same disk block will be read out at once, rather than what is needed.

There is the concept of Page in the InnoDB storage engine, which is the smallest unit of disk management. The default size of each page in the InnoDB storage engine is 16KB. You can set the page size to 4K, 8K, and 16K by parameter innodb_page_size. In MySQL, you can view the page size by using the following command:

Mysql > show variables like 'innodb_page_size'

On the other hand, the storage space of a disk block in the system is often not so large, so every time InnoDB applies for disk space, it will be several consecutive disk blocks to reach the page size 16KB. InnoDB will take pages as the basic unit when reading disk data to disk. When querying data, if each piece of data in a page can help to locate the location of data records, it will reduce the number of disk Imando O times and improve query efficiency.

B+Tree is an optimization based on B-Tree to make it more suitable for the implementation of external storage index structure. InnoDB storage engine uses B+Tree to implement its index structure.

Each node of the B-Tree structure contains not only the key value of the data, but also the data value. However, the storage space of each page is limited, if the data data is large, it will lead to a small number of key that each node (that is, a page) can store, and when the amount of data stored is very large, it will also lead to a large depth of B-Tree, which will increase the number of disk B-Tree O when querying, and then affect the query efficiency. In B+Tree, all data recording nodes are stored on the leaf nodes of the same layer according to the order of key values, while only key value information is stored on non-leaf nodes, which can greatly increase the number of key values stored in each node and reduce the height of B+Tree.

B+Tree node is a variant of B-Tree. Compared to B-Tree, B+Tree has the following differences:

Non-leaf nodes only store key value information.

There is a chain pointer between all leaf nodes.

The data records are stored in the leaf node.

So much for sharing what is the difference between B-Tree and B+Tree in MySQL. I hope the above content can be helpful to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.