preface

Hello, I’m here again. It’s almost the end of the year, and as an aspiring coder, I want to make a year-end summary for myself. Since the last part of the manual set up Redis cluster and MySQL master-slave synchronization (non Docker) and the last part of the manual implementation of MySQL read-write separation and failover, simply this database is the most core is the most difficult to understand the content, that is, the index, to share with you. In this blog POST I will share my own thoughts on index structures and how to finally understand them from scratch, layer by layer.

Start with a simple table

create table user(
	id int primary key,
    age int,
    height int,
    weight int.name varchar(32))engine = innoDb;
Copy the code

We will start with the simplest table and work our way through the MySQL index structure.

First, let’s insert some data into the table.

INSERT INTO user(id,age,height,weight,name)VALUES(2.1.2.7.'小吉');
INSERT INTO user(id,age,height,weight,name)VALUES(5.2.1.8.'little,');
INSERT INTO user(id,age,height,weight,name)VALUES(1.4.3.1.'little tiger');
INSERT INTO user(id,age,height,weight,name)VALUES(4.1.5.2.'little beauty');
INSERT INTO user(id,age,height,weight,name)VALUES(3.5.6.7.'XiaoCai');
Copy the code

Let’s check to see if this data is already in the table.

select * from user;
Copy the code

As you can see, the data has been completely placed in the user table that we created.

But I don’t know if you found anything, it seems that something very strange happened, the data we inserted seems to be out of order…

MySQL seems to have quietly sorted us by ID.

Why does MySQL sort things for us without explicitly sorting them? When was it sorted?

The introduction of the page

I don’t know how long it has been since you graduated. As a poor student who has just learned the operating system, the concept of page is still in my mind and has not become cool. There are also logical storage units in MySQL that are similar to pages.

In the concept of an operating system, when we fetch data from disk, let’s say the size of the data to be fetched is 1KB, but the operating system does not fetch only 1KB of data, it will fetch 4KB of data because a page entry of the operating system is 4KB. So why is it that we only need 1KB of data, but the operating system is fetching 4KB of data? That has implications for a program, the concept of locality, the concept of specific I back not pure, is “a program during a visit to a data, in after will be a great article may once again to access the data and access data of the adjacent data”, so just 4 KB of data to be loaded directly into memory, the next time to access this page data, directly from memory, You can reduce disk I/O times, as we know, disk I/O is a major factor affecting program performance, because disk I/O and MEMORY I/O speed is not the same.

Maybe it’s a bit abstract after reading that long description, so let’s go back to the database level and re-understand the concept of pages.

All of that aside, let’s say we’re looking for the data that we just inserted, and now we’re looking for the data that id is equal to 5, and the primitive way we’re going to think about it is going to be traversal, and yes, that’s the way we used to look for data when we first started learning computers. So let’s see, in a traversal way, how many disk I/OS do we need to go through to find the data with ID =5.

First, we need to read from the data with id=1 and determine if it is the data we need. If not, we need to read from the data with ID =2 and determine again. Needless to say, after MySQL sorted it for us, it took us five disk I/OS to find and read data number 5.

So let’s take a look at how we read data after introducing the concept of pages.

After introducing the concept of page, MySQL will store multiple data in a data structure called “page”. When MySQL reads the data with ID =1, it will read the whole page of the data with ID =1 into memory, and then perform traversal judgment in memory. Since the I/O speed of memory is much higher than that of disk, compared with disk I/O, It’s negligible, so let’s see how many disk I/OS we need to go through to read the data this way (assuming we can store 4 data per page). So we’re going to read the first disk I/O, and we’re going to read the first disk I/O from id=1 to ID =4, and then we’re going to read the second disk I/O from ID =5. So we only need to go through 2 disk IO to find the data with ID =5.

But in fact, in MySQL’s InnoDb engine, the page size is 16KB, 4 times the size of the operating system, and the data of int type is 4 bytes, and the number of bytes of other types of data is usually less than 4000 bytes, so a page can store many, many pieces of data. MySQL data is grouped in pages.

The figure above is the structure of a page as we understand it so far. It contains multiple pieces of our data. In addition, MySQL data is composed of pages, so it has Pointers to the next page and Pointers to the previous page.

MySQL actually sorts pages when we insert data into them, but we’ll keep that in the back of our mind.

Impact of sorting on performance

We asked the question above, why does the database sort data when it inserts it? Wouldn’t it be nice if we inserted the data in normal order?

This will involve a database query process, in any case, we are not going to insert data to complicate the process by adding an operation, so insert data sorting must have a purpose, is to optimize the efficiency of the query.

It is not difficult to see that the module storing data inside the page is essentially a linked list structure, which is characterized by fast addition and deletion and slow query, so it is necessary to optimize the efficiency of query.

  • Query flow based on single-page schema storage

    Again, based on the page diagram in section 1, we insert five data with ids ranging from 1 to 5, so suppose I want to find an ID that does not exist in the table. Suppose ID =-1, then the query flow is as follows:

    Take out the whole page of data with ID =1 and compare them one by one. Then when we find the data with ID =1, we find that the ID is greater than the id we need to find. Since the database has sorted the data when inserting the data, then the data with ID =1 will be followed by the data with ID >1. So we don’t need to go any further.

    If we didn’t sort when we inserted, then of course, we need to go down and look until we get to the end and we don’t find the data, and then we return the data that doesn’t exist.

Of course, this is just the tip of the sort optimization iceberg, so read on.

Possible problems with the above page pattern

Having said that, let’s look at the graph we showed in the first section, and see if it has any drawbacks for large data volumes, or to put it another way, how we can optimize this pattern.

It is not difficult to see that in the page mode we know at the present stage, there is only one function, which is to directly load a whole page of data into memory when querying a certain data, so as to reduce the I/O times of hard disk and improve the performance. However, we can also see that inside the current page schema, a linked list structure is actually adopted, with the previous data pointing to the next data, and in essence, specific data is extracted by comparing data one by one. So let’s say we have a million pieces of data on this page, and the data we’re looking for happens to be the last one, do we have to go back and find that one? If so, we need to look up a million times, even in memory, which is not very efficient. So what can you do to optimize search efficiency in this case?

Introduction of page directories

For example, when we are reading a book, if we want to find a certain section, and we do not know which page it is, do we have to go back and forth to find the page number of the content we need? The answer is no, because at the front of the book, there is a table of contents that tells you which page the section is on, for example, the first section is on page 1 and the second on page 13. This directory structure is actually used in the pages of the database, called the page directory.

So when we introduce the page directory, our understanding of the page structure looks like this:

Analyze this picture, in fact, page directory like when we read books directory, directory entry 1 is equivalent to the first quarter, entries 2 is equivalent to the second quarter, and each data is equivalent to the every page of book, this picture can be interpreted as, in the first quarter from the first page, starting from the third page, in the second quarter and, in fact, Each directory entry will hold the smallest id of its own, that is, directory entry 1 will hold 1 and directory entry 2 will hold 3.

Let’s compare the search process of the database when there is no page directory. Suppose you want to search for data with ID =3. If there is no page directory, you need to search for the data with ID =1, ID =2, and ID =3 three times before finding the data. And then directly via the directory entry for the data, if in the directory is not found under this data, you can directly determine the data does not exist, thus greatly improve the efficiency of the database to find, but the implementation of the page directory, first needs to be based on the data is in has been sort of scenarios, can play its role, So now you can see the second question, why does the database sort when it inserts, and that’s where sorting really comes into play.

The expansion of the page

In the previous article, we basically covered the concept of pages in MySQL database, how it can reduce disk I/O times based on pages, and how sorting can optimize query efficiency. So let’s think about the third question: Page said at the beginning of the concept of time, we have said, the size of each page in the MySQL only 16 KB, will not automatically as the data inserted into the expansion, so the 16 KB could not save us all the data, then will have more than one page to store data, so in many cases, the page is how to organize the pages in MySQL?

To solve this problem, let’s go ahead and draw the multi-page structure we now know:

As you can see, in the growing number of cases, the data will be to open up a new MySQL to store new data pages, each page has a pointer to the next page and a pointer to the previous page, will organize all the pages (revise the data, each column of the data in the data area, one of the first space before representative id), Id in the first page data for 1 to 5, the second page stored id data for the 6-10, the third page stored id data for 11 to 15, it is important to note at the time of opening the new page, we insert data doesn’t have to be on a new page, but to all pages of data comparison, to determine the data on which this article insert page, After the data is inserted, the resulting multi-page structure looks like the one in the figure above.

Multi-page mode

In multi-page mode, MySQL can finally complete the storage of multiple data, which is to open a new page, put multiple data in different pages, and then use the same linked list data structure, each page connected. Then we can consider the fourth question: does multi-page query have an impact on query efficiency?

  • The impact of multi-page schema on query efficiency

    For this question, since the question is asked, then the answer is yes, multiple pages will have a certain impact on query efficiency, the impact is mainly reflected in that the essence of multiple pages is also a linked list structure, as long as the linked list structure, the query efficiency will not be high. If the data is more again, the database will be opened up so many new pages, and these new pages will be like the list together, when we want to be in so many pages query for a data, it will start node traverse to the existence of we want to find the data of page, we very not easy to through the page directory page was optimized efficiency of data query, Now we have page-by-page lists, and that’s all gone, right?

  • How to optimize multi-page schema

    Since the multi-page pattern can affect query efficiency, there must be a way to optimize queries in the multi-page pattern. As some of you have already guessed, if we can optimize the data area within a page using the page table of contents, we can optimize the multi-page situation in a similar way. Yes, the in-page data area and the multi-page schema are essentially linked lists, so they can indeed be optimized in the same way, the table of contents page.

    Therefore, we compare the in-page data area to analyze how to optimize the multi-page structure. In a single page, we use the page directory entry to point to a row of data, which is the smallest data in the directory entry, so we can find the required data through the page directory. So you can also use this approach for multi-page structures, using a directory entry to point to a page, and this directory entry holds the index value of the smallest data stored in that page. The difference with page directories is that they are managed at the page level, whereas page directories are managed at the row level.

    At this point in the analysis, the structure of our multi-page pattern will look like the following:

    There is a directory page to manage the page directory, and the data in the directory page is the smallest data in the pointed page.

    One thing to note here is that the essence of a directory page is also a page. The data stored in a normal page is project data, and the data stored in a directory page is the address of a normal page.

    Let’s say we’re looking for data with ID =19, and the old way of looking, we start on page 1, we find it’s not there and then we go to page 2, we go to page 4 to find the data with ID =19, but if we have a table of contents page, we can compare it with the table of contents page, If 19 is greater than any other item, go to the page where id=16 and search directly and then through the page directory row level data search, you will soon find the data with ID = 19. As more data becomes available, the efficiency of this structure becomes more and more advantageous over the normal multi-page schema.

    Back to the topic, I believe those of you who are familiar with MySQL have discovered that the final picture we drew is a kind of index structure in MySQL — B+ tree.

Introduction of B+ trees

The characteristics of B+ trees I have described in detail in “[from entry to ground] bald database design”, here will not repeat the narrative, if you do not know the students can go to see this blog.

Moving on, we macroscopize the multi-page template we drew for the existing catalog page to form the following image:

This is a B+ tree that we’ve gone from simple to complex. A bit different from a regular B+ tree, this is a B+ tree in the MySQL sense, an index structure in MySQL, where each node is understood as a page, whereas leaf nodes are data pages, and other nodes are directory pages. It can also be seen from the figure that non-leaf nodes only store indexes, while only leaf nodes store real data, which is also in line with the characteristics of B+ trees.

  • B+ tree advantage

    1. Because leaf nodes hold all the data and are connected by Pointers, each leaf node is logically connected, making it user-friendly for range lookups.
    2. All the data of B+ tree are on the leaf node, so the query efficiency of B+ tree is stable, usually three times.
    3. B+ trees facilitate database scanning.
    4. B+ trees are good for disk I/O, because the height of a tree rarely increases as data grows (a three-layer tree can hold about 20 million data).

The complete structure of the page

Said these concepts and pages how step by step after combination structure called a B + tree, believe that everyone has a page for more clear cognition, so here is about to start about official concept, based on the above, give a full page structure, also be understanding above your page structure a supplement.

The File Header field is used to record the Header information of the Page. The most important fields are FIL_PAGE_PREV and FIL_PAGE_NEXT. Virtually all pages form a bidirectional linked list with two fields. The Page Header field records the Page status. The Infimum (lower bound) records a value smaller than any primary key value on the page, and the Supremum (upper bound) records a value greater than any primary key value on the page. This pseudo-record forms the boundary of the records on the page, respectively.

The User Records store the actual data row Records, the structure of which is described in more detail in section 2 of this article. Free Space stores Free Space. Deleted rows are recorded as Free Space. Page Directory records information related to binary lookups. File Trailer stores data such as checksums for checking data integrity.

Source: www.cnblogs.com/bdsir/p/874…

MySQL > B+ tree MySQL > B+ tree

See here, we have seen the MySQL from a single data to page through to reduce the number of disk I/o, and implements in page page directory page to optimize the query efficiency, multi-page model is then used to store a large amount of data, the final use catalog pages to achieve more mode of query efficiency and form the index structure of our mouth – B + tree. While we’re at it, let’s talk about some other things about MySQL.

  • Clustered index and non-clustered index

    About clustering index and the clustering index in/from entry to the grave is a hair loss of the underlying database design in this article has detailed introduction, here simply to say, the so-called clustering index, is to index and data together, find index also in finding the data, we just saw the B + tree index is a kind of clustering index, Non-clustered index is to separate the data from the index. When searching, it needs to find the index first and then find the corresponding data through the index back to the table. InnoDB has one and only one clustered index, while MyISAM has all non-clustered indexes.

  • The leftmost prefix matching principle for federated indexes

    In MySQL database, you can not only create an index for a single column, but also create a joint index for multiple columns. There is a concept of the left-most prefix matching principle in the joint index. It is relatively easy to understand the left-most prefix matching principle based on B+ tree.

    First we create a joint index based on the table above:

    create index idx_obj on user(age asc,height asc,weight asc)
Copy the code

    We have seen the index data structure is a B + tree, also understand the B + tree to optimize the query efficiency is one of the factors on the data sorting, so we are creating idx_obj this index, also is equivalent to create a B + tree index, the index is based on the members of the joint index to sort, This is age,height,weight. Those of you who read my previous blog post know that as long as a primary key is defined in InnoDB, the primary key column is treated as a clustered index and all other indexes are treated as non-clustered indexes, so naturally this index will be a non-clustered index.

    So from these we can come to the conclusion that:

    1. Idx_obj is an index that will sort by age,height,weight
    2. Idx_obj The idX_obj index is a non-clustered index that needs to be queried back to the table

    So the first thing you need to know from these two conclusions is, how do you rank?

    Single-column sorting is easy, anyone can do it, but what are the rules for multi-column sorting (important)?

    In fact, in MySQL, there is a sort principle that the index is sorted from left to right. For example, if the index is created, it will compare the size of age first. If age is the same, then it will compare the size of height. Finally sort the index.

    So we can also draw a B+ tree based on this order, which is not as detailed as we drew above, so let’s simplify it:

    Data:

    B + tree:

    Note: at this time, because it is not a clustered index, the leaf node does not have data, but a primary key index is saved, and the data will be queried back and forth through the primary key index.

    Now that we have our B+ tree structure, we can use this to understand the leftmost prefix matching principle.

    Let’s start with a query

    SELECT * FROM user WHERE age=1 and height = 2 and weight = 7
Copy the code

    Needless to say, this statement must follow the index idx_obj.

    So let’s look at another statement:

    SELECT * FROM user WHERE height=2 and weight = 7
Copy the code

    Think about it, does this SQL go through the index?

    The answer is no, so the direction of our analysis is why this statement does not go to the index.

    Idx_obj is age,height,weight from left to right. Therefore, when we use height and weight as query conditions, due to the absence of age, the index idx_obj is age,height,weight. So you can’t compare from age. If you use height and weight, you can compare them. So, for example, if we write the missing column as a hello, then the query condition for this statement would be, ok? 27, so let’s start at the root of the B+ tree. There are 127 and 365 on the root of the B+ tree. If we compare the height and weight of the B+ tree, we must go 127. For example, 427,527,627, if the cable leads to query data, data will be lost, error query. So in this case, the index will never be queried. This is where the leftmost prefix matching rule comes in.

    MySQL > select * from (a,b,c,d); MySQL > select * from (a,b,c,d); MySQL > select * from (b, C,d); MySQL > select * from (a,b,c,d); If the index (a,b,d,c) can be used, the order of a, B,d can be arbitrarily adjusted. 2.= and in can be in random order, such as a=1 and b=2 and c=3 to create (a,b,c) index can be in any order, MySQL query optimizer will help you optimize the form to be recognized by the index.

    Based on what we know, we can conclude that:

    As long as you can’t compare the size of the sort, you can’t go to the union index.

    Here are a few more statements:

    SELECT * FROM user WHERE age=1 and height = 2
Copy the code

    This statement can be idx_obj indexed because it can compare (12? < 365).

    SELECT * FROM user WHERE age=1 and weight=7
Copy the code

    This statement can also index ind_obj, because it can also compare (1? 7<365), but the actual weight does not use the index, because according to the left-most matching principle, if there are two pages of age equal to 1, then the height will be compared, but the height is not used in the query condition. So MySQL will load both pages into memory for the final weight field comparison and scan query.

    SELECT * FROM user where age>1
Copy the code

    This statement does not index, but it can. What does that mean? This SQL is very special, due to the existence of comparable index, so it went index can also check out the results, but because of this kind of circumstance is range query and whole field queries, if walk index, also need to be back to the table and MySQL query optimizer will think go index of efficiency is lower than a full table scan, so MySQL to optimize it, Tell him to run a full table scan.

    SELECT * FROM user WEHRE age=1 and height>2 and weight=7
Copy the code

    This statement can be indexed because it can be compared by age, but weight does not use an index because height is a range lookup. Similar to the second statement, if there are two pages with height greater than 2, MySQL will load the data from both pages into memory. It then matches the correct data by weight.

  • Why InnoDB has only one clustered index instead of using clustered indexes for all indexes?

    Because clustered indexes store indexes and data in leaf nodes, if all indexes use clustered indexes, each index will store a piece of data, resulting in data redundancy. In the case of a large amount of data, such data redundancy is very resource-consuming.

Add two points about the index

These two points are also missing from the last blog I wrote about indexes.

  1. What happens when you create an index, but execute it without passing the index? An SQL statement query can have different execution schemes. As for the final choice of which scheme, the optimizer needs to choose the scheme with the lowest execution cost. Before a single table query statement is actually executed, MySQL’s query optimizer finds all possible alternatives for executing the statement and compares them to find the least costly alternative. This lowest-cost option is known as the execution plan. The optimization process is as follows: 1. Find out all possible indexes according to the search criteria; 2. Calculate the cost of full table scan; 3. Reference link: juejin.cn/post/684490…

    The query optimizer does not remove the index from the table where the index is not clustered:

    SELECT * FROM user where age>1
Copy the code

  2. In the case of sparse index, it is usually necessary to query data back to the table through the pointer of the leaf node. When is it not necessary to query data back to the table? A covering index means that the execution of a query can be obtained only from an index, not from a table. You can also call it index coverage. When a query statement meets the conditions of overwriting an index, MySQL can return the data required by the query only through the index. In this way, the operation of returning to the table after the index is queried is avoided, which reduces I/O and improves efficiency. For example, the table covering_index_SAMPLE has a common index IDx_KEY1_KEY2 (key1,key2). Select key2 from covering_index_SAMPLE where key1 = ‘keytest’; Can be queried by overwriting the index without returning to the table. Reference link: juejin.cn/post/684490…

    Such as:

    SELECT age FROM user where age = 1
Copy the code

    This sentence does not need to do back table query.

conclusion

This article focuses on the MySQL index structure, slowly build a B+ tree index from scratch, and according to this process to talk about how the B+ tree to optimize the efficiency of the query step by step.

A brief summary is as follows:

Sort: The root of query optimization, sorting at insert time is actually to optimize query efficiency.

Page: used to reduce I/O times, but also can use the principle of program locality, to slightly improve query efficiency.

Page directory: used to avoid the weakness of the linked list, avoid the list scan in the query.

Multiple pages: Open a new page to save data when the amount of data increases.

Directory page: “special page directory” where the data stored is the address of the page. During query, you can quickly locate a page using the directory page to avoid multi-page scanning.

Welcome to visit my personal Blog: Object’s Blog