1. Why use an index
An index is a data structure used by a storage engine to quickly find data records. It is like the table of contents of a textbook. By finding the page number of the corresponding article in the table of contents, you can quickly locate the desired article. The same is true in Mysql. When searching for data, first check whether the query condition hits a certain index. If it matches, then use the index to find the relevant data. Records that meet the conditions (as shown in the figure below), the time complexity is O(n).
If you use a data structure such as Binary Tree to store the data at this time, as shown in the figure below:
Time complexity is O(log2n)
Adding an index to the field Col2 is equivalent to maintaining an index data structure for Col2 on the hard disk, that is, the Binary Search Tree . Each node of the binary search number stores a (k, v) structure, the key is Col2, and the value is the file pointer of the line where the key is located. For example: the root node of the binary search tree is: (34, 0x07). Now that an index is added to Col2, when searching for the record Col2=89, it will first search for this record Binary search tree (traversal search of binary tree). Read 34 to the memory, 89>34; continue with the data on the right, read 89 to the memory, 89=89; find the data and return. After finding it, quickly locate the address corresponding to the record to be searched according to the value of the current node. We can find that it only needs to search twice to locate the recorded address, and the query speed is improved.
This is why we use indexes, the purpose is to reduce the number of disk I/O and speed up query efficiency.
2. Indexes and their pros and cons
2.1 Overview of Index
MySQL’s official position on the index is: An index is a data structure that helps MySQL universities obtain data.
Essence of an index: An index is a data structure. You can simply understand it as a “sorted fast search data structure”, which satisfies a specific search algorithm. These data structures point to the data in some way so that advanced lookup algorithms can be implemented on top of these data structures.
‘The index is implemented in the storage engine‘, so the index of each storage engine may not be exactly the same. And each storage engine does not necessarily support all index types. At the same time, the storage engine can define the maximum number of indexes and maximum index length for each table. All storage engines support at least 16 indexes per table, with a total index length of at least 256 bytes. Some storage engines support more indexes and larger index lengths.
2.2 Advantages
1. Similar to the catalog index of a university library, it improves the efficiency of data retrieval and reduces the io cost of the database. This is also the main reason for creating an index.
2. By creating a unique index, you can ensure the uniqueness of the data in each row in the database table.
3. In terms of data referential integrity, it can accelerate the connection between tables. In other words, it can improve query efficiency when querying child tables and parent tables that have dependencies.
4. When using grouping and sorting clauses for data query, it can significantly reduce the time of grouping and sorting in the query, and reduce the consumption of cpu.
2.3 Disadvantages
Adding indexes also has many disadvantages, mainly in the following aspects:
1. It takes time-consuming to create and maintain indexes, and as the amount of data increases, the time spent will also increase.
2. Indexes need to occupy disk space. In addition to the data space of the data table station, each index also occupies a certain amount of physical space, which is stored on the disk. If there are a large number of indexes, index files may reach their maximum file size sooner than data files.
3. Although the index greatly improves the query speed, it will reduce the speed of updating the table at the same time. When adding, deleting and modifying the data in the table, the index should also be maintained dynamically, which reduces the data maintenance speed.
3. Deduction of indexes in InnoDB
3.1 Search before index
1. Search within a page
Assuming that there are relatively few records in the current table, all records can be stored in one page. When searching for records, there are two cases according to different search conditions:
Use the primary key as the search condition:
You can use Dichotomy in the page directory to quickly locate the corresponding slot, and then quickly find the specified record by traversing the records in the corresponding group of the slot.
Use other columns as search criteria:
Because there is no so-called page directory for non-primary key columns in the data page, we cannot quickly locate the corresponding slot through the dichotomy method. In this case, we can only start from the minimum record and traverse each record in the singly linked list in sequence, and then compare whether each record meets the search criteria. Obviously, this search efficiency is very low.
2. Find across many pages
In most cases, there are a lot of records stored in our tables, and many data pages are needed to store these records. Searching for records in many pages can be divided into two steps:
1. Navigate to the page where the record is located
2. Find the corresponding record from the page where it is located.
In the absence of an index, no matter whether it is based on the primary key column or other values, since we cannot quickly locate the page where the record is located, we can only from the first page along the >Doubly linked list keeps searching down, and searches for the specified record in each page according to our above search method. Because all the data needs to be traversed, this method is obviously super time-consuming. What if a table has 100 million data records? This is where Index comes in.
3.2 Design Index
Create a table:
CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY (C1) ) FOW_FORMAT = CompactThe newly created index_demo table has 2 columns of type INT and a column of type CHAR(1), and we specify that column c1 is gradual, and this table uses the Compact row format to actually store records. Here we simplify the row format diagram of the index_demo table;
We only show these parts of the record in the diagram:
recory_type: An attribute of record header information, indicating the type of record, 0 means normal record, 2 means minimum record, 3 means maximum record, 1 has not been used yet;
next_record: An attribute of the record header information, indicating the address offset of the next address relative to this record. We use arrows to indicate who the next record is;
The value of each column: Here are only three columns recorded in the index_demo table, namely c1, c2 and c3
Other information: all information except the above three information, including the values of other hidden columns and additional information recorded;
The schematic for putting some records into a page is:
1. A simple index design
Why do we traverse all the data pages when we are looking for some records based on a certain search condition? Because the records in each page are not regular, we don’t know that our search conditions match the data in those pages, so we have to traverse all the data pages in turn. So what if we want to quickly locate the records we need to find in those data pages? We can create a directory for quickly locating the data page where the record is located. To create this directory, the following things must be done:
~ The primary key value of the user record in the next data page must be greater than the primary key value of the user record in the previous page.
Assumption: Each data page can store up to 3 records. With this assumption, we want to insert 3 records into the index_demo table:
INSERT INTO index_demo VALUES (1,4,'u'), (3,9,'d'), (5,3,'y');Then these records have been concatenated into a single-item linked list according to the size of the primary key value, as shown in the figure:
It can be seen from the figure that all three records in the index_demo table have been inserted into the data page numbered 10. Now let’s look at inserting a record:
INSERT INTO index_demo VALUES(4,4,'a');Since page 10 can only hold up to 3 records, we have to allocate a new page:
Note that the newly allocated data page numbers may not be consecutive. They just establish a linked list relationship by maintaining the number of the previous page and the next page. In addition, the largest primary key of the user record in page 10 is 5, and the primary key of a record in page 28 is 4, because 5 > 4 , so this does not meet the requirement that the primary key value of the user record in the next data page must be greater than the primary key value of the user record in the previous page, so when inserting a record with a primary key value of 4, it needs to be accompanied by a Record movement, that is, move the record with the primary key value of 5 to page 28, and then insert the record with the primary key value of 4 into page 10. The schematic diagram of this process is as follows:
This process shows that in the process of adding, deleting, and modifying records in the page, we must always ensure this state through some operations such as record movement: the next data is also in the user record The primary key value must be greater than the primary key value of the user record in the previous page. We call this process page splitting.
~ Create a directory entry for all pages.
Since the numbers of the data pages may be discontinuous, after inserting many records into the index_demo table, the effect may be as follows:
Because these 16KB pages are discontinuous in physical storage, so if you want to quickly locate some records based on the primary key value from so many pages page, we need to make a table of contents for them, each page corresponds to a directory item, and each directory item includes the following two parts:
– The smallest primary key value in the user record of the page, we use key to represent
– The page number, which we denote with page_no.
So our table of contents for the top few pages looks like this:
Take Page 28 as an example, it corresponds to Catalog Item 2, which contains the page number 28 of this page Minimum primary key value of 5 for user records. We only need to store several directory items consecutively on the physical memory (for example: an array), and then we can realize the function of quickly searching for a certain record according to the primary key value. For example: to search for records whose primary key value is 20 , the specific search process is divided into two steps:
1. Firstly, according to the dichotomy method, quickly determine that the record whose primary key value is 20 is in directory item 3 (because 12 < 20 < 209 ), which corresponds to page is page 9
2. Locate specific records in Page 9 according to the method of searching for records in the page mentioned above.
At this point, the simple directory for the data page is done. This directory has an alias called index.
2. Index scheme in InnoDB
1. Iterate 1 time: the page recorded by the directory entry
The above is called a simple indexing scheme, because we assume that all directory items can be stored in the physical memoryContiguous storage, but there are several problems with doing so:
~ InnoDB uses pages as the basic unit of storage space management, and can guarantee a continuous storage space of 16kb at most, but as the number of records in the table increases, a very large continuous storage space is required to put down all the directory entries, which is unrealistic for a table with a very large number of records.
~ We will always add and delete records, assuming we delete all the records in Page 28, that means Directory Item 2 is also There is no need to exist anymore. This just needs to move forward the directory after directory item 2, so the operation efficiency of the whole body is very poor.
So, we need a way to flexibly manage all directory items. We found that the directory item looks similar to our user record, except that the two columns in the directory item are primary key and page number. In order to do it with the user record To distinguish between them, we call these records used to represent directory entries as directory entry records. How does InnoDB distinguish whether a record is a normal user record or a directory entry record? Use the record_type attribute in the record header information, and its values represent the following meanings:
~ 0: normal user
~ 1: directory entry record
~ 2 : minimum record
~ 3: maximum record
This is how we put the directory items we used earlier into the data page:
As can be seen from the figure, we newly allocated a page numbered 30 to store directory entry records. Here again, the difference between Directory Entry records and normal User records is emphasized:
~ The record_type value of Directory Entry Record is 1, while the record_type value of General User Record is 0.
~ There are only two columns of primary key value and page number in directory entry records, while the columns of ordinary user records are defined by users themselves, which may contain many columns, and there are also hidden columns added by InnoDB List.
~ Understand: There is also an attribute called min_rec_mask in the record header information, only the directory entry record with the smallest primary key value in the page storing the directory entry record have a min_rec_mask value of 0.
The same point: both use the same data page, and both will have the primary key value birth date Page Directory (page directory), so when searching according to the primary key value, you can use the dichotomy to speed up the query .
Now take the record whose primary key is 20 as an example, the steps to find a record based on a certain primary key value can be roughly divided into the following two steps:
1. First go to the page where Directory Item Record is stored, that is, on page 30, use the Dichotomy to quickly locate the corresponding directory item, because 12 < 20 < 209 , so the page where the corresponding record is located is page 9
2. Go to page 9 where the user records are stored and quickly locate the user records whose primary key value is 20 according to the dichotomy.
Iterate 2 times: pages with multiple catalog entry records
Although the Directory Item Record only stores the primary key and the corresponding page number, which is much smaller than the storage space required by the user record, but no matter how you say a page is only 16KB in size, The directory item records that can be stored are also limited, so if there are too many data in the table, so that one data page is not enough to store all the directory item records, how to deal with it Woolen cloth?
Here we assume that a page that stores directory entry records can only store up to 4 directory entry records, so if we insert a user record with a primary key value of 320 in the upper diagram at this time, then Need to allocate a new page to store Category-like records.
As can be seen from the figure, we need two new data pages after inserting a user record with a primary key value of 320:
~ page 31 is newly created to store the user record;
~Because the original page 30 capacity for storing directory entry records is full, a new page 32 has to be needed to store the corresponding page 31 directory entry for
Now because there are more than one page for storing directory item records, if we want to find a user record based on the primary key value, it takes roughly three steps. Take finding the record with the primary key value 20 as an example;
1. OK Directory Item Records Page
We now have two pages for storing directory item records, namely Page 30 and Page 32, and because the primary key value range of the directory item represented by page 30 is [1,320], page 32 indicates that the primary key value of the directory entry is not less than 320, so the directory entry corresponding to the record with the primary key value of 20 is recorded on page 30.
2. By determining the page where the user record is actually located on the directory entry record page.
The way to locate a directory entry record by its primary key value in a page that stores Catalog Image Records.
3. Locate the specific record in the page that actually stores user records.
Iterate 3 times: catalog page of catalog item record page
Here comes the problem. In the first step of this query step, we need to locate the pages that store directory entry records, but these pages are not continuous. If there are a lot of data in our table, >Generate many pages that store directory entry records, so how can we quickly locate a page that stores directory entry records based on the primary key value? Then generate a higher-level directory for these pages storing directory item records, just like an additional multi-level directory, big directory manages small directory, small directory manage data,
As shown in the figure, we have generated a page 33 that stores more advanced directory items. The two records in this page represent page 30 and page 32 respectively. If the primary key value of the user record is between [1,320], then go to the page 30 to find more detailed directory entry records, if the primary key value is not less than 320, then go to page 32 to find the data.
As the records in the table increase, the directory level will continue to increase. If we simplify it, we can use the following diagram to describe it:
This data structure, its name is B + tree.
4. B+ tree
Whether it is a data page storing user records or a data page storing directory item records, we have stored them in the data structure of B + tree, so we also These pages of data are called nodes. It can be seen from the figure that our actual user records are actually stored on the bottom nodes of the B + tree. These nodes are also called leaf nodes, and the rest of the nodes used to store directory items are called It is a non-leaf node or a internal node, where the topmost node of the B+ tree also becomes the root node.
The nodes of a B + tree can actually be divided into several layers, and the bottom layer, which is the layer where our user records are stored, is defined as the 0 layer, which will be added one at a time, as we did before A very extreme assumption: the page storing user records can store up to 3 records, and the page storing directory item records can store up to 4 records. In fact, the number of records stored on a page in the real environment is very large. Assume that the data pages represented by all leaf nodes storing user records can store 100 user records, and all internal nodes that store directory item records represent The data page can store 1000 directory entry records, then:
~ If the B+ tree has only 1 layer, that is, there is only one node for storing user records, it can store up to 100 records.
~ If the B + tree has two layers, it can store 1000*100=100000 records at most.
~ If the B+ tree has three layers, it can store up to 1000*1000*100=100000000 records.
~ If the B+ tree has four levels, it can store up to 1000*1000*1000*100=10000000000 records.
Can you store 1000000000 records in your table? So under normal circumstances, the B + tree we use will not exceed 4 layers, Then we only need to search a record in 4 pages at most through the primary key value, and because There is a so-called pageDirectory in each page, so the dichotomy method can also be used to quickly locate records in the page.
