[MySQL Indexing and Optimization] Index data structure

Article directory

• • 1 Overview
  • 2. Common index structures
  • • 2.1 Clustered index
    • 2.2 Secondary index (auxiliary index, non-clustered index)
    • 2.3 Joint index
  • 3. Things to note about InnoDB’s B+ tree index
  • • 3.1 The location of the root page remains unchanged for thousands of years.
    • 3.2 Uniqueness of directory entry records in internal nodes
  • 4. Index scheme in MyISAM
  • 5. Comparison between InnoDB and MyISAM
  • 6. Summary
  • 7. Supplement: The rationality of MySQL data structure
  • • 7.1 Full table traversal
    • 7.2 Hash structure
    • 7.3 Binary search tree
    • 7.4 AVL tree
    • 7.5 B-Tree
    • 7.6 B+Tree
    • 7.7 R-tree
  • 8. Thinking questions
  • • 8.1 Think about the storage capacity of B + tree? Why is it said that generally searching for records only requires 1 to 3 disk IOs at most?
    • 8.2 Why is B+ tree more suitable than B-tree for file indexing and database indexing of operating systems in practical applications?
  • 9. Summary

1. Overview

Index is a data structure that helps MySQL obtain data efficiently, which is equivalent to the table of contents of a book. If the table is large and contains tens of millions of data, it means many disk I/O are required to find the required data. After establishing the index, if you query based on the index (the innodb storage engine uses a B + tree structure), compared with searching in sequence, it will greatly reduce the number of disk I/0 and speed up the search; reduceThe IO cost of the database, which is also the main reason for creating an index

Indexes are implemented in storage engines, so the indexes for each storage engine are not necessarily identical, 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.

Disadvantages:

1. Creating and maintaining indexes is time-consuming, and as the amount of data increases, so does the time it takes.
2. Indexes require disk space
3. Indexes slow down updates to the table . When adding, deleting, or modifying data in the table, the index must be dynamically maintained, which reduces the data maintenance speed.

Therefore, when choosing to use an index, you need to consider the advantages and disadvantages of the index.

Indexes can improve the speed of queries, but they will affect the speed of inserting records. In the face of frequent additions, deletions and modifications, the best way is to delete the index in the table first, then insert the data, and then create the index after the insertion is completed.

2. Common index structures

First of all, you need to know that the MySQL database fetches data from the disk to the memory in the smallest unit data page, which is mentioned in the buffer pool in the architecture chapter of the previous chapter (the default data page size is 16KB).

2.1 Clustered Index

Features:

1. Using the size of the record’s primary key value to sort records and pages has three implications:

   • The records in the page are arranged in a one-way linked list in order of the size of the primary key.
   • Each page that stores user records is also arranged into a double linked list based on the primary key size of the user records in the page.
   • Pages that store directory entry records are divided into different levels. Pages in the same level are also arranged into a double-linked list based on the primary key size of the directory entry records in the page.

2. The leaf node of the B + tree stores complete user records

   The so-called complete user record means that the values of all columns (including hidden columns) are stored in this record.

We call the B + tree with these two characteristics a clustered index, and all complete user records are stored at the leaf nodes of this clustered index. This kind of clustered index does not require us to explicitly use the INDEX statement in the MySQL statement to create it. The InnoDB storage engine will automatically create a clustered index for us (The index is the data).

Disadvantages:

• Insertion speed depends heavily on the insertion order. Inserting in the order of primary keys is the fastest way, otherwise page splits will occur, seriously affecting performance. Therefore, for InnoDB tables, an auto-incremented ID column is generally defined as the primary key.
• Updating the primary key is expensive because it causes the updated rows to move. Therefore, for innoDB tables, we generally define the primary key as non-updatable
• Secondary index access requires two index searches, the first time to find the primary key value, the second time to find the row data based on the primary key value

Limitations:

• Currently, only the InnoDB data engine of MySQL database supports clustered indexes, while MylSAM does not support clustered indexes.
• Since there can only be one physical storage sorting method for data, each MySQL table can only have one clustered index. Usually it is the primary key of the table
• If no primary key is defined, lnnodb will select non-empty unique index instead. If there is no such index, lnnodb will implicitly define a primary key as a clustered index.
• In order to make full use of the clustering characteristics of the clustered index, the primary key column of the innodb table should try to use ordered sequential IDs. It is not recommended to use unordered IDs such as UUID, MD5, HASH, and string columns as the primary key, which cannot guarantee the data. sequential growth

2.2 Secondary index (auxiliary index, non-clustered index)

The clustered index introduced above can only work when the search condition is primary key value, because the data in the B + tree is sorted according to the primary key. So what should we do if we want to use other columns as search conditions? We certainly cannot traverse the records along the linked list from beginning to end.
Answer: We can build more B+ trees, and the data in different B+ trees adopt different sorting rules. For example, we use the size of column c2 as the data page and the sorting rule for the records in the page, and then build a B + tree. The effect is as shown in the figure below:

This B+ tree has one major difference from the clustered index above:

• The leaf nodes of the B + tree do not store the complete user record, but the values of the two columns c2 column + primary key

Secondary index search process:

When searching through the secondary index, first find the primary key value through the secondary index, then use the primary key value to search for data in the clustered index through the primary key value (this process is return table); if the index contains the data column you are looking for, such as c2, then there is no need to return to the table and the data can be retrieved directly. At this time This index is called a covered index

There will be other processing when the c2 values are the same. Please see 3.2 for details later.

2.3 Union index

We can also use the size of multiple columns as the sorting rule at the same time, that is, create indexes for multiple columns at the same time. For example, we want the B + tree to be sorted according to the size of c2 and c3 columns. This Contains two meanings:

• First sort the records and pages according to column c2
• When the c2 column of the records is the same, the c3 column is used for sorting.

The schematic diagram of the index established for columns c2 and c3 is as follows:

As shown in the figure, we need to pay attention to the following points:

• Each directory entry record is composed of three parts: c2, c3, and page number. Each record is first sorted according to the value of column c2. If the records in column c2 are the same, they are sorted according to the value of column c3.
• The user record at the B + tree leaf node consists of c2, c3 and primary key c1 columns

The B+ tree established with the size of columns c2 and c3 as the sorting rule is called a joint index, which is essentially a secondary index.

3. Things to note about InnoDB’s B + tree index

3.1 The root page position remains unchanged for thousands of years

The formation process of B + tree:

• Whenever a B + tree index is created for a certain table (clustered indexes are not created manually, they are available by default), a root node page will be created for this index. When there is no data in the table at the beginning, there are neither user records nor directory entry records in the root node corresponding to each B + tree index.
• When subsequently inserting user records into the table, first store the user records in this root node
• When the available space in the root node is exhausted, records will continue to be inserted. At this time, all records in the root node will be copied to a newly allocated page, such as page a , and then perform the page split operation on this new page to obtain another new page, such as page b. At this time, the newly inserted record will be allocated to page a or according to the size of the key value (that is, the primary key value in the clustered index, the value of the corresponding index column in the secondary index) code>page b, and the root node is upgraded to a page that stores directory entry records

Special attention should be paid to this process: the root node of a B + tree index will not move from the date of its birth. In this way, as long as we create an index on a certain table, the page number of its root node will be recorded somewhere, and then whenever the InnoDB storage engine needs to use this index, it will be Take out the page number of the root node from that fixed place to access this index.

3.2 Uniqueness of directory entry records in internal nodes

In the above-mentioned secondary index, if the same value exists in the second-level directory entry, and a same value needs to be inserted at this time, it will not be possible to know which leaf node page the value to be inserted should be inserted into, so in fact, the second-level index In order to maintain the uniqueness of the internal nodes, the index also adds the primary key value to the directory entry. In this way, when the directory entry c2 is the same, the primary key value can be compared to determine where the leaf node should be inserted. As shown below:

In this case, when we need to insert (9, 1, x’), we know that we need to insert it into page 5.

4. Index scheme in MyISAM

Index/Storage Engine	MyISAM	InnoDB	Memory
B + tree index	Supported	Supported	Supported

Even if multiple storage engines support the same type of index, their implementation principles are also different. The default index of Innodb and MyISAM is B + tree index; while the default index of Memory is Hash index.

The MyISAM engine uses B + Tree as the index structure, and the data field of the leaf node stores the address of the data record.

Although MyISAM’s index scheme also uses a tree structure, it stores the index and data separately:

• Store the records in the table in the order of insertion of the records in a separate file, called data file. This file is not divided into several data pages. Just put as many records as there are into this file. Since the data is not sorted according to the primary key size when inserting the data, we cannot use the binary method to search on this data.
• Tables using the MyISAM storage engine will additionally store index information in another file called index file. MyISAM will create an index for the primary key of the table separately, but what is stored in the leaf node of the index is not the complete user record, but the combination of primary key value + data record address

Assume that the table has three columns in total. Assume that we use Col1 as the primary key. The picture above is a representation of the primary index (Primary key) of a MyISAM table. It can be seen that MyISAM’s index file only saves the address of the data record. In MyISAM, there is no structural difference between the primary key index and the secondary index (Secondary key). It is just that the primary key index requires the key to be unique, while the keys of the non-primary key index can be repeated. Therefore, the primary key and non-primary key indexes of MyISAM are both two. level index.

Therefore, the index retrieval algorithm in MylSAM is: First, search the index according to the B + Tree search algorithm. If the specified Key exists, take out the value of its data field, and then use the value of the data field as the address to read the corresponding data record.

5. Comparison between InnoDB and MyISAM

The indexing methods of MyISAM are all “non-clustered”, which is different from InnoDB which contains a clustered index. The differences between the indexes in the two engines are:

• In the InnoDB storage engine, we only need to perform a search on the clustered index based on the primary key value to find the corresponding record, but in MyISAM we need to perform a table return operation, which means that all indexes created in MyISAM are equivalent to secondary indexes
• The data file of lnnoDB itself is an index file, while the MyISAM index file and data file are separated. The index file only saves the address of the data record.
• The non-clustered index data field of lnnoDB stores the corresponding record the value of the primary key, while the MylSAM index records the address. In other words, all non-clustered indexes in InnoDB reference the primary key as the data field
• MyISAM’s table return operation is very fast because the address offset is used to fetch data directly from the file. In contrast, InnoDB obtains the primary key and then searches for the record in the clustered index. Although It’s not slow, but it’s still not as good as accessing it directly using the address.
• lnnoDB requires that the table must have a primary key (MyISAM may not have it). If not specified explicitly, the MySQL system will automatically select a column that can be non-null and uniquely identify the data record as the primary key. If such a column does not exist, MySQL automatically generates an implicit field as the primary key for the InnoDB table. This field is 6 bytes long and of type long integer.

6. Summary

1. It is not recommended to use a field that is too long as the primary key because all secondary indexes refer to the primary key index, and a primary key index that is too long will make the secondary index too large.
2. It is not a good idea to use non-monotonic fields as primary keys in innoDB because the InnoDB data file itself is a B + Tree, and non-monotonic primary keys will cause the data file to be maintained when new records are inserted. Due to the characteristics of B + Tree, frequent splitting and adjustment are very inefficient, and using auto-increment fields as primary keys is a good choice (distributed systems must consider the uniqueness of primary keys, such as snowflake algorithm, etc. Solution follow-up research)
3. Joined indexes should put data with less duplication at the front so that the corresponding data can be found as quickly as possible according to the field on the left side of the index.
4. The joint index follows the leftmost matching principle, that is, the search logic is to first search for the leftmost field of the index and compare it one by one, and cannot start from the right field of the index.

7. Supplement: The rationality of MySQL data structure

From the perspective of MySQL, a practical issue that has to be considered is disk IO. If we can make the data structure of the index minimize the I/O operations of the hard disk, the time consumed will be smaller. It can be said that the number of disk I/O operations is crucial to the efficiency of index usage.

Searches are all index operations. Generally speaking, the index is very large, especially in relational databases. When the amount of data is relatively large, the size of the index may be several G or more. In order to reduce the memory occupation of the index, the database index is stored on external disk. When we use index query, it is impossible to load the entire index into the memory. We can only load it one by one. Then MySQL’s standard for measuring query efficiency is the number of disk IOs.

7.1 Full table traversal

Data pages need to be loaded one by one. If it is the last page, the entire table needs to be traversed and all data pages loaded into memory, which requires a large number of I/O operations.

7.2 Hash structure

The average time complexity of hash query/insertion/modification/deletion is O(1), but the index structure still adopts a tree structure. The specific reasons are:

1. Hash indexes can only satisfy (=) (<>) and IN queries. If range query is performed, the time complexity of hash-type index will degrade to O(n); while the “ordered” characteristic of tree type can still maintain the high efficiency of O(log2N)
2. There is another flaw in the Hash index. The data is stored in no order. In the case of ORDER BY, using the Hash index also requires reordering the data.
3. In the case of a joint index, the Hash value is calculated by merging the joint index keys. It is impossible to query a single key or several index keys.
4. For equivalent queries, Hash indexes are usually more efficient, but there is also a situation where if there are many duplicate values in the index column, the efficiency will be reduced. This is because when a Hash conflict occurs, it is necessary to traverse the row pointers in the bucket to compare and find the query keyword, which is very time-consuming. Therefore, Hash indexes are usually not used on columns with many repeated values, such as gender, age, etc.

In addition, InnoDB itself does not support Hash index, but provides Adaptive Hash index (Adaptive Hash index) . Under what circumstances will an adaptive Hash index be used? If a certain data is frequently accessed, and when certain conditions are met, the address of the data page will be stored in the Hash table. In this way, the next time you query, you can directly find the location of this page. This allows B + trees to also have the advantages of Hash indexes.

Adaptive Hash index variables are enabled by default:

show variables like '?aptive_hash_index';

7.3 Binary search tree

If a tree structure is used as the index structure, the number of disk IOs is related to the height of the index tree. If the inserted data keeps getting larger, the binary search tree will form a chain, and the time complexity of finding the data will degrade to O(n). In order to improve query efficiency, you need to reduce the height of the tree code>, it is necessary to change the original “skinny and tall” tree structure into a short and fat one. The more branches at each level of the tree, the better.

7.4 AVL tree

In order to solve the problem of binary trees degenerating into linked lists, people proposed a balanced binary search tree (Balanced Binary Tree), also known as an AVL tree (different from the AVL algorithm). In this way, the time complexity of the search can be stabilized at Log2N, but when the amount of data is large, the depth of the tree will also be very high, and each node access is allowed to perform a disk I/O operation, which requires It also takes a lot of time.

7.5 B-Tree

In response to the above problems, if the binary tree is changed to an M-fork tree (M>2), the height of the M-fork balanced tree will be much smaller than the height of the binary tree, so the tree can be made more “short and fat”. The English name of B-tree is Balance Tree, which is multi-way balanced tree. The abbreviation is B-Tree (- indicates that two words are connected, pronouncing a horizontal bar instead of B minus tree). The typical difference from B + tree is that non-leaf nodes will also store data. For a large amount of index data, the B-tree structure is very suitable because the height of the tree is much smaller than the height of the binary tree.

7.6 B + Tree

B + tree is also a multi-way search tree, which is improved based on B tree. Mainstream DBMS supports B + tree indexing method, such as MySQL. Compared with B-Tree, B + Tree is suitable for file indexing systems.

The fundamental difference between B + Tree and B-Tree is that the intermediate nodes of B + tree do not directly store data. What are the benefits of this?

• The query efficiency of B + tree is more stable because the intermediate nodes do not need to store data. To find the data, you must find the leaf nodes of the data.
• B + tree query efficiency is higher because intermediate nodes do not need to store data. B + tree is usually stubbier than B tree, and the disk I/O required for query locks is smaller. There will be fewer, the same disk page, B + tree can store more node keys
• B + tree query range is more efficient. There are pointers between leaf nodes of B + tree, and the data is increasing. Range search can be searched through pointer connection, while in B tree, in-order traversal is required, which is more efficient. much lower

Both B-tree and B+-tree can be used as index data structures. In MySQL, B+-tree is used, but B-tree and B+-tree each have their own application scenarios. It cannot be said that B+ tree is better than B-tree.

Note: The index tree will not be loaded at once (a large amount of data will inevitably lead to an increase in the index), but each disk page will be loaded one by one, because the disk page corresponds to the node of the index tree.

7.7 R-tree

R-Tree is rarely used in MySQL and only supports geometry data type. The only storage engines that support this type are myisam, bdb, innodb, ndb, and archive. Give an example of what R-tree can solve in the real world: find all restaurants within 20 miles. How would you solve it if there was no R tree? Generally, we will divide the coordinates (x, y) of the restaurant into two fields and store them in the database. One field records the longitude and the other field records the latitude. In this case, we need to traverse all restaurants to obtain their location information, and then calculate whether the requirements are met. If there are 100 restaurants in an area, we will have to perform 100 location calculation operations. If applied to very large databases such as Google and Baidu Maps, this method will definitely not be feasible. R trees are very good at solving this high-dimensional space search problem. It extends the idea of B-tree to multi-dimensional space very well, adopts the idea of B-tree dividing space, and adopts the method of merging and decomposing nodes when adding and deleting operations to ensure the balance of the tree. Therefore, R-tree is a balanced tree used to store high-dimensional data. Compared with B-Tree, the advantage of R-Tree is range search

8. Thinking questions

8.1 Think about the storage capacity of B + tree? Why is it said that generally searching for records only requires 1 to 3 disk IOs at most?

The page size in the InnoDB storage engine is 16KB. The primary key type of the general table is INT (occupies 4 bytes or BIGINT (occupies 8 bytes)). The pointer type is generally 4 or 8 bytes, which means a page (A node in B + Tree) stores approximately 16KB/(8B + 8B) = 1K key values (because it is an estimate, to facilitate calculation, the value of K here is 10^3. In other words, a depth of A B + Tree index of 3 can maintain 10^3 * 10^ 3 * 10^3 = 1 billion records. (This assumes that a data page also stores 10^3 row record data)

In actual situations, each node may not be fully filled, so in the database, the height of B + Tree is generally 2~4 levels. MySQL’s InnoDB storage engine is designed so that the root node is resident in memory, which means that only 1 to 3 disk I/O operations are needed to find the row record of a certain key value.

8.2 Why is B+ tree more suitable than B-tree for file indexing and database indexing of operating systems in practical applications?

1. The disk read and write cost of B + tree is lower. The internal nodes of B + tree do not have pointers to specific information of keywords. Therefore, its internal nodes are smaller than B-tree. If all the keywords of the same internal node are stored in the same disk block, the more keywords the disk block can hold. The more keywords that need to be searched are read into the memory at one time. Relatively speaking, the number of IO reads and writes is reduced.
2. The query efficiency of B + tree is more stable

9. Summary

Using indexes can help us quickly locate the data we want to find from massive amounts of data. However, indexes also have some shortcomings, such as taking up storage space, reducing the performance of database write operations, etc. If there are multiple indexes, it will also increase the time of index selection. . When we use indexes, we need to balance the advantages (improved query efficiency) and disadvantages (cost of maintaining the index) of the index.

In actual work, we also need to determine whether to use an index based on demand and the distribution of the data itself. Although indexes are not omnipotent, it is unimaginable not to use indexes when the amount of data is large. , after all, the essence of index is to help us improve the efficiency of data retrieval