How to understand the problem of using B+ tree in MySQL index structure

1. B-tree and B-tree

Generally speaking, the storage engine of the database uses B-tree or B-tree to store the index. First look at the B-tree, as shown in the figure.

#B-tree is a multi-way balanced tree. If this storage structure is used to store a large amount of data, its entire height will be much shorter than that of a binary tree.

For the database, all data will be saved to the disk, and the efficiency of disk I/O is relatively low, especially in the case of random disk I/O.

So the height determines the number of disk I/Os. The fewer the number of disk I/Os, the greater the performance improvement. This is why B-tree is used as the index storage structure, as shown in the figure. .

MySQL's InnoDB storage engine uses an improved B-tree structure, that is, B-tree, as the index and data storage structure.

Compared with the B-tree structure, B-tree has been optimized in two aspects, as shown in the figure.

#1. All data in the B-tree is stored in leaf nodes, and non-leaf nodes only store indexes.

2. The data in leaf nodes are related using a doubly linked list.

2. Reason analysis

I think that the MySQL index structure uses B-tree for the following 4 reasons:

1. From the perspective of disk I/O efficiency: The non-leaf nodes of the B tree do not store data, so each layer of the tree can store more indexes. In other words, the B tree has the same layer height than the B tree. The tree stores more data, which indirectly reduces the number of disk I/Os.

2. From the perspective of range query efficiency: In MySQL, range query is a relatively common operation, and all data stored in leaf nodes of the B-tree are related using doubly linked lists, so the B-tree When querying, you only need to check two nodes for traversal, while the B-tree needs to obtain all nodes. Therefore, the B-tree is more efficient in range queries.

3. From the perspective of full table scanning: Because the leaf nodes of the B-tree store all data, the global scanning capability of the B-tree is stronger because it only needs to scan the leaf nodes. The B-tree needs to traverse the entire tree.

4. From the perspective of self-increasing ID: a data structure based on B-tree, if self-increasing integer data is used as the primary key, it can better avoid the problem when adding data. The problem of large number of operations caused by leaf node splitting.

The above is the detailed content of How to understand the problem of using B+ tree in MySQL index structure. For more information, please follow other related articles on the PHP Chinese website!