The index

Reference:

• How does MySQL run: From the root understand MySQL
• MySQL > MySQL
• High Performance MySQL (Version 3)

MySQL index

Index is to improve the efficiency of data query, just like the table of contents of a book, we can use the table of contents to quickly find the page of a certain knowledge point. Similarly, for a database table, an index is essentially a “directory” of table data.

Indexes are implemented in the MySQL storage engine layer, so each storage engine may not support the same index, and even if multiple storage engines support the same type of index, the underlying implementation may be different. The table below shows the index types supported by different storage engines.

The index type	InnoDB engine	MyISAM engine	The Memory engine
B + Tree index	Y	Y	Y
A Hash index	N	N	Y
R – Tree indexes	N	Y	N
Full – Text index	N	Y	N

B+Tree index and Hash index are two commonly used index data storage structures:

• B+Tree index is implemented by B+Tree. It is stored in an ordered order, so it has advantages in sorting and range search.

• Hash indexes are suitable for key-value pair query. The complexity of query data is O(1) regardless of the size of the table data, and the performance of query using Hash indexes is higher than that of other indexes. The disadvantage is that hash indexes are slow to do interval queries because they are not ordered. Therefore, the hash table structure is suitable for scenarios where there are only equivalent queries.

B + Tree index

Data page

B+Tree index is achieved by B+Tree, you can balance binary Tree, B Tree, B+Tree, B* Tree this article to understand the data structure principle of B+Tree.

The smallest unit of InnoDB disk management is a page, and each node in the B+Tree index is a data page. Before we explore the B+Tree index, let’s review what we’ve learned about pages.

The information recorded in the File Header section of the page structure is as follows:

Here are some important things to keep in mind:

• FIL_PAGE_OFFSET: Indicates the page number of the current page. Each page has a unique number
• FIL_PAGE_PREV: a bidirectional linked list pointing to the previous page of the current page
• FIL_PAGE_NEXT: a bidirectional linked list pointing to the next page of the current page
• FIL_PAGE_TYPE: The type of page, index and data are storedFIL_PAGE_INDEX (0 x45bf)In this type of page, the data page.

A data page holds rows of records. The Compact row record format is shown below:

The information recorded in the recording header is as follows:

Two important things to keep in mind here:

• record_type: Type of record:
  • 0: indicates common user records
  • 1: records of directory entries
  • 2: minimum record
  • 3: indicates the maximum record
• next_record: points to the next record on the page

With this information, you can form a simple bidirectional linked list to store data, with pages connected by FIL_PAGE_PREV and FIL_PAGE_NEXT. A page contains rows of records. Each row is connected by next_record to form a single necklace table. Each page has a minimum record (Infimum, record_type=2) and a maximum record (Supremum, record_type=3). Then there is the normal user record (record_type=0).

B+Tree Index formation process

Using the account table used in the previous test, we first create a primary key index for the ID column.

CREATE TABLE `account` (
  `id` bigint(11) NOT NULL AUTO_INCREMENT COMMENT 'primary key',
  `card` varchar(60) NOT NULL COMMENT 'number',
  `name` varchar(60) DEFAULT NULL COMMENT 'name',
  `balance` int(11) NOT NULL DEFAULT '0' COMMENT 'the balance'.PRIMARY KEY (`id`),
  UNIQUE KEY `account_u1` (`card`) USING BTREE,
  KEY `account_n1` (`name`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Account sheet';
Copy the code

Whenever a B+Tree index is created for a table, a root node page is created for the index and does not move. The page number of the root node is recorded, and when the index is needed to access the table, the root node page is retrieved to access the index.

For example, when creating a primary key index, a root node page with page number 30 is created. Data is first inserted into the root node page.

Note that a row contains not only user records, but also hidden transaction IDS (trx_id), rollback Pointers (roll_pointer), and so on, which are not shown in the figure.

Assume that a page is full with at most 3 records.

Insert another record with ID =4, the root node page is full, a new page is allocated (page 35), and all records in the root node are copied to this newly allocated page. Because page 35 is full, a new page (page 38) is reassigned, and the new record is inserted into page 38.

The problem here is that the records on the index are sequential, and the primary key value of the user record on the next data page must be greater than the primary key value of the user record on the previous page. The largest record on page 35 is id=5. If you insert a record with id > 5, you can insert it into page 38 without problem. So the insertion of id=4 is accompanied by page splitting, moving id=5 to page 38 and then inserting id=4 into page 35.

This process indicates that in the process of adding, deleting and modifying records in a page, some operations such as record movement are carried out to ensure that the primary key value recorded in the next data page is always greater than the primary key value recorded in the previous page. This process can also be called page splitting.

The pages where user records are stored may not be physically next to each other (such pages are called user record pages), so if you want to quickly locate the pages of some records based on their primary key, you need to create a directory for them.

The root node page becomes the directory page, which contains records of type record_type=1, which is the directory entry record. The structure of the directory entry record is similar to that of ordinary records, except that its data part stores only the primary key value and page number. Each user record page will correspond to a directory entry record, and the primary key value of this directory entry record is the record with the smallest primary key value in this user record page.

In this case, there will be two entries in the following node page, the first record is the page number 35, ID =1; The second record has a page number of 38 and id=5.

As user records are inserted, the number of user records pages becomes larger and the directory page becomes full, and it becomes impossible to insert another directory entry record. Take the last record below.

In fact, as before is similar, will also be accompanied by the page split operation. The root node page never moves and copies all records to a newly allocated page. Now you can see that the directory page has two layers.

The picture above now looks like an upside-down tree, which is actually a B+ tree, a data structure used to organize data.

Both the data page for user records and the data page for directory entry records are stored in the B+ tree data structure. As can be seen from the figure, user record pages are stored in the lowest nodes of the B+ tree, which are also called leaf nodes or leaf nodes. The other nodes used to store directory items are called non-leaf nodes or internal nodes, among which the node at the top of the B+ tree is called the root node.

Look up records in the index

Now that a B+ index has been formed, let’s say we want to find the record with id=11.

• IO first reads the root node page of the index (page 30) into memory, and then iterates through the entries in the root node page in memory. These entries can be divided into several intervals based on the primary key: (Infimum, 1), [1, 15), [15, Supremum) id=11 falls within the range [1, 15), so the corresponding page number is 52.

• Then I/O reads page 52 into memory and iterates through the records on the page, where id=11 falls in the range [10, Supremum), so locates the record with id=10 and the corresponding page number is 45.

• Then I/O reads page 45 into memory and iterates through the records in the page to locate the user record with id=11.

Note that both the Directory Page and the user record Page have a Page Directory, or Page Directory, through which you can quickly navigate to a record in the Page through dichotomy, rather than traversing from left to right. For Page Directory please refer to: MySQL series (4) — InnoDB data Page structure.

Note that the B+ tree index does not find the specific row of a given key value, only the page of the row being searched. The database then reads the page into memory, looks it up in memory, and finally gets the data to look for. So there will be IO operations in the above steps.

The number of disk I/OS is equal to the height of the B+ tree. That is, the number of I/OS will depend on the height of the B+ tree. Disk I/OS are often a bottleneck for database performance. How many levels can a B+Tree index have?

We assumed a maximum of three records per page, but a 16KB page is a lot of records. Suppose the leaf node data page that holds user records can hold 100 user records and the inner node data page that holds directory entry records can hold 1000 directory entry records:

• If B+Tree has one layer, that is, only one node for storing user records, it can hold up to 100 records.

• If B+Tree has two layers, a maximum of 1000 x 100= 100,000 records can be stored.

• If B+Tree has three layers, it can store a maximum of 1000×1000×100= 100 million records.

• If B+Tree has four layers, a maximum of 1000×1000×1000×100=100 billion records can be stored.

A table rarely has more than 100 million records, let alone 100 billion. Therefore, in general, B+Tree does not exceed 4 levels.

To find a record by primary key value, we only need to do a maximum of four Page searches (to find three Directory item pages and one user record Page), and because there is Page Directory in each Page, we can quickly locate records in the Page by dichotomy.

So once you have an index, it’s really fast to look up data by index. Without an index, you can only scan the entire table, read each page to memory traversal, there will be a lot of disk IO, this performance is very low.

Clustering index

The ID primary key index created above is actually a kind of clustered index, the most important feature is that the leaf node of B+ tree stores the complete user record, that is, stores the values of all columns in a row of records (including hidden columns).

In addition, the clustering index uses the size of the record primary key value to sort records and pages in the following ways:

• The records in the page are arranged in a one-way linked list in order of the size of the primary key.
• Each page storing user records is also arranged in a bidirectional linked list according to the primary key size of user records in the page.
• The pages that store directory entry records are divided into different levels. The pages in the same level are also arranged in a bidirectional linked list according to the primary key size of directory entry records in the page.

InnoDB storage engine tables all have primary keys. If we do not explicitly define a primary key for a table and do not define a unique index in the table, InnoDB automatically adds a hidden column with row_ID as the primary key. Therefore, InnoDB always automatically creates clustered indexes. In InnoDB, clustered indexes are how data is stored. All data is stored on the leaves of this B+ tree.

Secondary index

When InnoDB creates a table, it creates a clustered index with a primary key by default. All other indexes are secondary indexes, also known as secondary indexes or non-clustered indexes.

A clustered index is useful only if the search criteria are primary keys, because that’s where the directory page is stored and the data in the B+ tree is sorted by primary key. If we want to query against other non-primary key columns, such as the name column in the previous account table, we can create a secondary index for the name column.

The biggest difference between the secondary index and the cluster index is that the leaf node stores not the complete user record, but the index column + primary key value, and the directory page stores the value of the index column. Meanwhile, the secondary index uses the size of the index column to sort records and pages.

For example, here is a secondary index created for the name column. It can be seen that the lowest leaf node only contains the data of the name + ID column, and the data is sorted according to the size of the name column. The directory page also stores the value of the Name column.

This secondary index is used when the data is searched against the name column, similar to the lookup process for a clustered index. The main difference is that the data searched by using the secondary index is not a complete user record, so after finding the record on the leaf node, it will return to the primary key index according to the corresponding primary key value and then find the corresponding complete record according to the primary key value. This process is also called back to the table.

For example, if name=H is found on page 69, the primary key id=11 for name=H will be found on page 69, and then the full record id=11 will be found on the cluster index.

When using secondary index lookup, it is not necessary to return to the table. If the data we are looking for already exists on the secondary index, we will not return to the table. SQL select name, id WHERE name=’H’; SQL select name, id where name=’H’; SQL select name, id where name=’H’;

Joint index

We can also use the size of multiple columns as sorting rules and create indexes for multiple columns at the same time. An index created by multiple columns is called a joint index, which is essentially a secondary index or secondary index.

For example, if the name and balance columns are indexed, the name, balance and ID columns will be stored on the leaf node, and the directory page will be stored by name, balance and page number.

Associative indexes are sorted by the first column, then by the second column if the first column is the same, and so on. For example, the combined index of name and balance is sorted by the name column. If the value of name is the same, the value is sorted by the balance column.

Index in MyISAM

InnoDB engine table clustering index contains both index directories and complete data, index and data are stored together in a B+ tree.

MyISAM engine tables store indexes and data separately:

• User data is stored separately in the insertion order of records in a file called a data file, which is a file with the suffix.myd. The file does not divide data pages, but inserts all records in the order they are inserted, and then accesses a record quickly using the physical address of each row.

• The index information is stored in a separate index file with the.myi suffix. MyISAM creates a separate index for the primary key of the table, but instead of storing the complete user record in the leaf node of the index, it stores a combination of primary key values and physical addresses. That is, first find the physical address of the row through the index, and then find the corresponding record through the physical address.

That is to say, all indexes established in MyISAM engine are equivalent to secondary indexes, no matter the primary key or other column indexes are created, they need to return to the table according to the physical address, to search for complete user records in the data file.

Index to summarize

The index rules

According to the previous study, we first summarized and familiar with the InnoDB engine B+ tree index rules.

• Each index corresponds to a B+ tree, which generally has no more than four levels, with the lowest level being the leaf node and the rest being the inner node. All user records are stored in the leaf node of the B+ tree, and all directory entry records are stored in the inner node.

• The InnoDB storage engine automatically creates a clustered index for the primary key. The leaf nodes of the clustered index contain the complete user record.

• You can create a secondary index based on actual requirements. The leaf node of the secondary index only contains index column + primary key. Therefore, if you want to find the complete user record through the secondary index, there will be a table-back operation, that is, after finding the primary key value through the secondary index, you will find the complete user record in the cluster index.

• In B+ tree index, data page nodes of each layer are sorted in order of index column values from small to large to form a bidirectional linked list. Records in each page (whether user records or directory entries) form a unidirectional linked list in order of index column values from small to large.

• Pages and records in a joint index are sorted by the column that precedes the joint index and, if the column has the same value, by the column that follows the joint index.

• Finding records by index starts at the root of the B+ tree and goes down level by level. Because each Page has a Page Directory based on the value of the index column, lookup within these pages is also very fast.

It is important to remember that the order of index columns is related to the characteristics of the index itself, as well as to the performance optimizations and limitations of many queries.

The index advantages

Index is mainly to improve the query performance of the database, summed up mainly has the following advantages:

• Indexes greatly reduce the amount of data that the server needs to scan and can quickly locate a record. And because the index column stores the actual value, some queries can complete the entire query using the index alone without going back to the table.

• Indexes help the server avoid sorting and temporary tables because indexes are sorted BY index columns and the data is already sorted, so they are useful for range queries, sorting ORDER BY, and grouping GROUP BY.

• Indexes can turn random I/ OS into sequential I/ OS because the data is sorted by index columns.

The index cost

The first thing to be clear about is that more indexes is not always better, and their use comes at a price.

• The cost in space

A B+ tree is created for each index. Each node in the B+ tree is a data page, and each page takes up 16KB of storage space by default. The more data a table has, the larger the B+ tree will be and the more space it will take up.

• The cost in time

Each B+ tree index needs to be modified every time data in the table is added, deleted, or modified. Each node of B+ tree is a bidirectional linked list in ascending order according to the value of the index column, and the records in the node are also a one-way linked list formed by ascending order according to the value of the index column. Adding, deleting, and changing operations may damage the ordering of nodes and records, so the storage engine needs extra time to perform operations such as record shifting, page splitting, and page reclamation to maintain the ordering of nodes and records. So the more indexes you build, the more time it takes to add, delete, and change indexes.

Therefore, the more indexes a table has, the more storage space it takes up, and the worse performance it will have when adding, deleting, or modifying records. Indexes can only improve overall performance if they are used and created correctly, otherwise they can backfire.

An index is only effective if the benefit of finding a record outweighs the extra work it does. For very small tables, a simple full table scan is more efficient in most cases. For medium to large tables, indexes are very effective.

The index application

All values match

Full value matching is when the columns in the query condition match the columns in the index.

For example, to create a federated index idx_cnb for (card, name, balance), suppose a query uses all three columns:

SELECT * FROM account WHERE card = 'A' AND name = 'A' and balance = 0;
Copy the code

First of all, idx_cnb is a union index. The index is sorted according to card column. If the card column is the same, the index is sorted according to name column.

So this query looks for records where card =’A’ and then quickly finds records where name=’A’, and uses the balance column if card and name are the same.

The order of the search criteria in the WHERE clause has no effect on the query result. The MySQL query optimizer automatically optimizes the SQL statement and determines which query criteria to use first and which to use later, depending on the index to be used.

Matches the leftmost prefix

For a federated index, you can use only part of the left column. You may not have all of the columns in the federated index, but only the consecutive left column.

For example, the following query uses the idX_CNB joint index, but uses only the first two columns of the index.

SELECT * FROM account WHERE card = 'A' AND name = 'A';
Copy the code

If only the middle column is used, the combined index is not used. For example, the following SQL query is based on name, because the idx_CNB index is installed first card column sort, the name column will be used only if the card column is the same. So you can’t skip the card column and look up data directly from the name column.

SELECT * FROM account WHERE name = 'A';
Copy the code

For example, in the following SQL, only the first column of the IDx_CNB index will be used, because balance is sorted according to the name column first, so for card=A data, balance may not be ordered. Therefore, all data of card=A should be queried into memory and then data of balance=0 should be filtered out.

SELECT * FROM account WHERE card = 'A' AND balance = 0;
Copy the code

Matching column prefix

The matching column prefix matches only the beginning of a column’s value.

For example, the following query matches only records whose card begins with A, or the IDx_CNB index can be used to quickly locate records.

SELECT * FROM account WHERE card LIKE 'A%';
Copy the code

However, if only the suffix or a string in the middle is given, the index cannot be used. For example, the following query looks for records whose card ends in A, and cannot use the index because the order before the end of A is not known.

SELECT * FROM account WHERE card LIKE '%A';
Copy the code

Matching range value

Matching range value is the use of index orderliness, can be very convenient to find records in a certain range.

For example, in the following SQL statement, a range lookup based on the CARD column can use the idx_CNB index.

SELECT * FROM account WHERE card > 'A' AND card < 'H';
Copy the code

Note, however, that if a range lookup is performed on multiple columns in a federated index, the index can be used only for the leftmost column of the index. Because the second column is not ordered after the first column is queried using the range query, remember that the second column is only sorted if the first column values are the same.

For example, in the following query, the records of cards between (A and B) are queried first. In this case, there may be multiple records of different cards, so the names in these records are not in order. Therefore, you need to find the records between (A, B) and filter out the records whose name > A one by one. So this query only uses the CARD column of the IDX_CNB index, not the name column.

SELECT * FROM account WHERE card > 'A' AND card < 'H' AND name > 'A';
Copy the code

Matches exactly one column and ranges exactly the other

The previous section said that if the first column is a range query and the second column is also a range query, the second column does not move the index.

But if the left column is an exact match and the next column is a range query, you can use the index, because if the left column is an exact match, the next column is sorted.

For example, in the following query, the card column is an exact match, and then a range search is performed on the name column. This query will use the card and NAME columns of the IDX_CNB index.

SELECT * FROM account WHERE card = 'A' AND name > 'A';
Copy the code

Sorting and grouping

We often use the ORDER BY clause to sort records. In general, the database can only load records into memory and sort them in memory using some sort algorithm. In some cases, if the result set is too large to be sorted in memory, disk space may be used to hold intermediate results, and the sorted result set may be returned to the client after the sorting operation is complete. In MySQL, this method of sorting files in memory or on disk is called filesort, and the performance of file sorting is generally low.

However, if the ORDER BY clause uses indexed columns, it is possible to eliminate sorting in memory or files.

For example, the following query uses the idx_CNb index. Since card and name are already sorted, the query can directly extract data from the IDx_CNb index and then query back into the table. (Of course, the idX_cnB index already contains the entire table, so there is no table back step)

SELECT * FROM account ORDER BY card, name;
Copy the code

Similarly, ORDER BY can use only part of the B+ tree index column, or use the following column when the value of the left column of the union index is an exact match. For example, the following query:

SELECT * FROM account ORDER BY card, balance;

SELECT * FROM account WHERE card='A' ORDER BY name;
Copy the code

Note that the column after the ORDER BY clause must be in the same ORDER as the index column, otherwise the index will not be used. For example, the following query:

SELECT * FROM account ORDER BY name, card;
Copy the code

When sorting using a federated index, the sorting order of the columns is required to be the same, either ASC ascending or DESC descending.

Because if one is in ASC ascending order and one is in DESC descending order, this is always the opposite of the order in the index, and if restrictions such as LIMIT are applied, the specific records can only be determined after the order is sorted. So MySQL thinks this is not as fast as sorting files, so it doesn’t use indexes.

For example the following query statement:

SELECT * FROM account ORDER BY name ASC, card DESC;
Copy the code

If the columns used to sort are not in the same index, this case cannot be sorted using the index, for similar reasons. If the acount table has other columns, such as the following query, the country column does not belong to idx_CNb, so this query sort does not use idx_cnb.

SELECT * FROM account ORDER BY name, country;
Copy the code

Grouping and sorting are similar in the way they use indexes.