What is an index? Why is there a MySQL index, what problem is it solving, and what is the underlying principle? Why use B+ trees as a solution? Wouldn’t it work with something like a hash index or a B-tree?
A brief understanding of indexes
First of all, what is an Index? If I told you that an index is an ordered data structure in a database management system, you might get a little confused.
To avoid this, I’m going to give you a few examples that will help you understand indexes more easily.
When we query the dictionary, we can find the corresponding word according to the radicals and strokes of the word, so that we can quickly find the page of the corresponding word, at the beginning of the dictionary that thing is called the index
There is also a table of contents of the book to help us quickly jump to different chapters, and in this case the table of contents is also an index
And even a map of the area that tells you where you are right now, where the other places are, and this map is an index in some ways, right
Combined with the technical explanation at the beginning, you might be able to understand what an index is.
Why an index is needed
Now that we understand the concept of indexes, we need to know why do we need indexes? As you can see from the example above, the purpose of an index is:
- The index in the dictionary helps us find the corresponding word quickly
- The table of contents of the book helps us quickly jump to the chapters we need to read
- The map of the scenic spot helps us quickly find the way to the scenic spot we want to go to
In the database, the index can help us quickly query to the corresponding data row, so that the data of all columns can be extracted smoothly. This process has to be fast, and for today’s Web applications, a slow response of the DB will directly affect the response time of the entire request, which is disastrous for the user experience.
If you click a button and wait several seconds for it to return, chances are that users will never use your app again.
Indexes in MySQL
First of all, MySQL is not directly related to indexes. Indexes are actually a concept in InnoDB, the storage engine used in MySQL. In InnoDB, indexes are divided into:
- Clustering index
- Non-clustered index
For clustered indexes, this is the index built by InnoDB based on the Primary Key. For the moment, you can think of it as Key as the primary key, and Value as the whole row. And a table can only have one clustered index.
Of course, you don’t have to define a primary key. But normally we would either create a monotonically increasing primary key, or we would generate it using a uniform ID generation algorithm. If you don’t define any primary keys, InnoDB has its own back-up strategy. InnoDB will select the first unique index we define where none of the values is empty as the cluster index.
However, in a real production environment, there will be such a Corner Case. InnoDB also has a bottom line. If the only remaining unique index does not meet the requirements, InnoDB creates a hidden primary key of 6 bytes, ROWID, and then generates a cluster index based on this hidden primary key.
A non-clustered Index is an Index created on a specified column, also known as a Secondary Index. Up to 64 Secondary indexes can be created in one table. Key is the value of the column in which the secondary index is created, and Value is the primary key. In other words, if you query through the non-clustered index, you can only get the value of the index column itself + the value of the primary key. If you want to get the complete column data, you need to query in the clustered index again according to the obtained primary key. This process is called back to the table.
For the record, there are a lot of blogs saying that MySQL can only create 16 indexes per table when using InnoDB. First of all, this is wrong, it is clearly copied from somewhere else, without any verification.
A table can create a maximum of 64 unclustered indexes, and the number of columns cannot exceed 16 when creating a non-clustered index.
Note that no more than 16 columns can be created for a non-clustered index!
By the way, as a side note, what is rigorous about technology? We take a skeptical view of what you might have learned from other sources, called the author’s opinion at best, and try to verify it for ourselves. Prove it, and it will become a fact.
Instead of trying to memorize certain terms, there’s a lot of new stuff out there, but when you go back to the roots, you find that’s the way it is.
Principle of index base
I mentioned the index types in InnoDB, simple understanding of their classification and differences, then InnoDB index how to speed up the query? What is the underlying principle? The underlying structure of indexes in InnoDB is B+ tree, which is a variation of B tree.
To give you an idea of what a B+ tree looks like, here is a B+ tree with the numbers “1-7”.
<img src=”https://tva1.sinaimg.cn/large/008i3skNgy1gqhyirkodxj30uh0akt9h.jpg” style=”zoom:67%;” />
As you can see, each node in a B+ tree can have multiple children, whereas in the familiar binary tree, each node can have at most two. Moreover, in B+ trees, nodes store data in order, and an ordered data structure allows for fast exact matching and range queries. And leaves in the B+ tree have Pointers to the next node between them, whereas leaves in the B tree don’t have any.
In the actual implementation of MySQL InnoDB, there is actually a double-linked list between the page nodes, storing Pointers to the previous node and the next node
The following diagram shows the B-tree with the integers “1-7”, which should help you understand the difference.
And, in the B+ tree, all the nodes store Pointers to the next node, except for the leaf nodes, which store the actual data. In other words, the data is all on the leaf node. In a B-tree, all nodes can store data, which is a major difference.
Now that we know what the B tree and B+ tree infrastructure looks like, we need to take a closer look at how InnoDB uses B+ trees to store data. First of all, MySQL does not store data in memory. Memory is used as a runtime optimization. I have written an article about InnoDB’s memory architecture, so if you are interested, you can read it first.
InnoDB stores the data on disk, and when we query the data, the OS loads the data from disk into memory page by page. Pages here are a way for the OS to manage memory, and when it loads data into memory, it loads data on a disk block according to the size of the page. In this case, you can think of each node in the B tree as a disk block.
So since both B trees and B+ trees have to do I/O to load the required nodes into memory when looking up, what’s the advantage of B+ trees over B trees?
In my opinion, there are three main points.
One is that B+ trees reduce the number of I/O. Why? Why should B+ trees reduce the number of I/O when the data structure is almost the same length? As mentioned earlier, a single node represents a disk block, and the size of a single disk block is fixed. A B+ tree stores values only at leaf nodes, and a single disk block in a B+ tree can hold more data than a B tree in which all nodes store complete data.
The smaller the size of the elements stored on a single disk block, the greater the number of elements that can be stored. In other words, one I/O can load more data into memory, and those extra elements are more likely to be used by you, thus reducing the number of I/O.
In addition, the number of elements that can be stored on a single node can also reduce the height of the tree.
Second, the query efficiency is more stable. What does that mean more stable? In other words, this request may take 10ms, and the next time the same request clicks, it may take 20ms. This is very unacceptable. Considering the interface performance, it also depends on the mood of your database.
So why is it that using B+ trees can achieve stable query efficiency? Since B+ tree non-leaf nodes do not store data, if you want to retrieve the final data, you must look up the leaf node. In other words, the number of I/O per query is the same. As all nodes of B tree can store data, some data may be queried in one I/O, while some data can not be found until the leaf node is queried, which will lead to unstable query efficiency.
The third is to be able to better support the range of queries. So why can’t B trees be well supported? Let’s go back to the B tree.
Suppose we need to query the data in the interval [3, 5], what will we experience? No nonsense, just give me the picture.
As you can see, if the complete data is still not found at the leaf node, it will return to the root node and traverse again. On the other hand, when B+ tree finds leaf nodes, it can directly traverse the linked list through the pointer between leaf nodes, which can greatly improve the efficiency of range query.
Once you know this, you can see why InnoDB does not use Hash for the underlying data structure. Even though the Hash of the query is even O(1) in time.
Finally, I/O
I/O has been mentioned many times throughout the article, and in MySQL index design, I/O should be minimized. Because I/O is expensive. What happens when we perform an I/O?
Originally like to talk about the disk structure in detail, but a glance at the space, has been nearly over, so here is a brief talk about good
In a mechanical hard disk, an I/O operation consists of three steps:
The first step is to seek, which means that the head of the disk moves over the track on the disk. This time is usually within 3-15ms.
Then there is rotation, where the disk rotates the disk that stores the corresponding data below the head. This takes another 2ms or so, depending on the speed of the disk.
Finally, data transfer.
After a wave of operation, the cost is around 10ms. Don’t think 10ms is okay… Compared to SSDs and memory in microseconds and nanoseconds, there is a world of difference.
This is why random I/O has a significant impact on query performance in MySQL.
Well, that’s all for this blog. Welcome to WeChat search for “SH full stack notes”, reply to “queue” for MQ learning materials, including basic concept analysis and RocketMQ detailed source code analysis, continuing to update.
If you find this article helpful, please like it, leave a comment, share it, or leave a comment.
