Understanding MySQL clustered indexes and how clustered indexes grow

In this note, we briefly describe

• What is the B+Tree index of MySQL?
• How does the clustered index grow taller?

If you look at it bit by bit, it's actually quite easy to understand.

If you have read my previous notes, you must know that MySQL performs CRUD in memory, that is, in the Buffer Pool. Then you also know that when there is no data required by MySQL in the memory, MySQL will read the data from the disk into the memory through IO operations. The unit of reading is: data page

The general data page length is as follows

That’s right, real data is stored in the data pages, and the data pages are organized in the memory as a two-way linked table! As shown below

In the setting of B+Tree, it requires that the primary key index is incremented, that is to say, if the primary key index is incremented, then all the data in the data page on the right must be larger than the data in the data page on the left. But it is obvious that the above picture does not match, so it needs to be adjusted to the following by page splitting.

OK, now think back, you must have heard before: MySQL's B+Tree clustered index, only the leaf nodes store real data, and the non-leaf nodes store index data, and the leaf nodes are connected by a bidirectional linked list.

That’s right, all the leaf nodes of the B+Tree are the data pages in the above figure, and they are indeed linked by a doubly linked list!

Let's continue reading. If we only look at the doubly linked list connected by data pages in the above figure, what will happen if we retrieve the data row with id=7?

Obviously we have to start the scan from scratch!

Then you might ask: Didn’t we just say that B+Tree requires the primary key to be increasing? And there is a page split mechanism to ensure that all data in the data page on the right is larger than the index value of the data page on its left. Why not do a binary search?

Answer: Yes, it is indeed possible to perform binary search in a single data page, but the organizational relationship between data pages is a linked list, so traversal from the beginning is inevitable.

So what about MySQL?

As shown below: MySQL abstracts an index directory for many data pages

With this index directory, it will be much easier for us to search among many data pages! Directly have the ability of binary search!

And this directory actually exists in the data page. What is different from the leaf node is that it only stores index information, while the leaf node stores real data?

The birth of the index page also means that the prototype of B+Tree has been born!

As users continue to select, the number of data pages in the buffer pool increases, and the number of data in the index page will also increase. When the existing index size exceeds 16KB (the capacity of a data page), a new index page must be created to store the new index information. At this time, the B+Tree will slowly become fatter and fatter.

Then you also know that B+Tree is a variant of B-tree, and B-tree can actually be a general term for M-order trees such as 2-3 tree, 2-3-4 tree, etc. When the elements that can be stored in each node reaches the upper limit, the tree will grow taller (mentioned in the previous article).

Just like the following picture:

The above is the detailed content of MySQL clustered index and how clustered index grows, which can be understood at a glance. For more information about MySQL clustered index, please pay attention to other related articles on 123WORDPRESS.COM!