preface

The paper come zhongjue shallow, and must know this to practice.

describe

At present myself into Lin Xiaobin big man mysql combat 45 speak, I believe many people have seen, just see 04-05 simple index, think it is very important, so make a note, we can also learn at the same time I also make a note.

Common Interview Questions

  • A common model for indexing
  • InnoDB index model
  • Back to the table
  • Index overwrite
  • Left-most prefix rule
  • An index pushdown

The index

Baidu Encyclopedia explanation

In relational databases, an index is a single, physical storage structure that sorts the values of one or more columns in a database table. It is a set of values of one or more columns in a table and the corresponding logical pointer list to the data page in the table that physically identifies these values. Index function is equivalent to a book catalog, you can quickly find the required content according to the page number in the catalog.

Easy to understand

When we were in primary school, our teacher taught us to use xinhua dictionary. If you want to look up a single word “zhou”, do you want to turn over the page by page or directly look up the z in the catalog? The answer is definitely to look up the catalog, so the index also means the same thing.

A common model for indexing

Hash table

Hash table is a kind of key-value storage structure. As long as we input the value to be searched (key), we can find its corresponding value (value). The idea of hashing is very simple, you put the value in an array, you use a hash function to convert the key to a certain location, and then you put the value in that location in the array. Inevitably, when multiple keys are converted to hash functions, the same value will occur. One way to handle this is to pull out a linked list.

An overview of the

So in the diagram above, the rule of his query is, for example, he calculates N by ID_card_n2, and then he calculates the corresponding value from the linked list of N, and then he loops through the linked list, and notice that it’s not ordered, so we get the hash table.

Hash table as index conclusion

Hash tables are only suitable for single equal scenarios, not for interval look-up.

Orderly array

An ordered array is a special kind of array in which the elements are arranged in a certain order, and we’re going to assume that they’re arranged from smallest to largest

An overview of the

Ordered array can make up for the deficiency of hash table in range. Ordered array has excellent performance in equivalent query and range query scenarios, but it is not perfect, because the cost of updating data and inserting data is too high.

Ordered array as index conclusion

Ordered array indexes are only suitable for static storage engines. Ordered arrays are suitable for look-ups on ranges, not for scenarios where inserts and updates are frequent.

Search tree

An overview of the

The binary search tree

The characteristics of

The characteristic of binary search tree is that the left son of each node is smaller than the parent, and the parent is smaller than the right son. So if you want to look up ID_card_n2, the search sequence is UserA -> UserC -> UserF -> User2. This is order log N. Of course, in order to maintain order log(N) query complexity, you need to keep this tree balanced binary. To make this guarantee, the update time is also order log(N), and the index is not only stored in memory, but also written to disk.

You can imagine a 1 million-node balanced binary tree, 20 tall. A query may require access to 20 data blocks. In the days of mechanical hard disks, reading a block of data randomly from a disk took about 10 ms of addressing time. That is, for a 1 million row table, if stored in a binary tree, it might take 20 10 ms to access a single row, which is a really slow query

conclusion

Because of the tree height, higher may affect efficiency, so the binary search tree is not suitable

InnoDB index model

InnoDB uses B+ tree. In InnoDB, tables are stored in the form of indexes according to the order of primary keys. Tables in this storage mode are called indexed organized tables. The B+ tree works well with the read/write feature of the disk, reducing the number of disk accesses in a single query. You can take a look at the principle of the B+ tree, which is not summarized here.

Back to the table

An overview of the

The process of returning to the primary key index tree is called back to the table.

How can I avoid the back table process

Index coverage is used in the index coverage.

Indexes cover

Select ID from T where k between 3 and 5; select ID from T where k between 3 and 5; select ID from T where k between 3 and 5; In other words, in this query, index K has “overridden” our query requirements, which we call the overridden index. Because overwriting indexes can reduce the number of tree searches and significantly improve query performance, it is a common performance optimization method to use overwriting indexes.

My understanding of index coverage

In this case, I think it’s k, but in the case where you already have an index, your ID is the primary key index, which means that the index overwrite needs to have an ID. Because index coverage of the entire table is the reduction of back.

Left-most prefix rule

For example,a union index (a,b,c) hits from the left when I query, such as a, AB, ABC hits.

Federated primary key indexes

In fact, it is the same as the union index, you can look at the union index, the hit rule also follows the left-most prefix principle

An index pushdown

Before MySQL 5.6, you could only return tables one by one from ID3. Find the rows on the primary key index and compare the field values. The index condition pushdown feature introduced in MySQL 5.6 can be used to determine the fields contained in the index during index traversal and filter out the records that do not meet the conditions to reduce the number of table returns.

Overview of the teacher

Each dotted arrow in figure 3, figure 1 and Figure 4, figure 2 represents a return to the table. In Figure 3, I have deliberately removed the age value from the index (name,age). InnoDB does not look at the age value, but simply fetches the “name first word is’ zhang ‘” entries one by one. Therefore, you need to return to the table four times.

The difference between Figure 4 and Figure 3 is that InnoDB determines whether age is equal to 10 within the index (name,age), and skips records that are not equal to 10. In our example, we only need to judge the two records of ID4 and ID5 back to the table to fetch data, and only need to back to the table 2 times.

Teacher’s Understanding

Before MySQL 5.6, you could only return tables one by one from ID3. Find the rows on the primary key index and compare the field values. The index condition pushdown feature introduced in MySQL 5.6 can be used to determine the fields contained in the index during index traversal and filter out the records that do not meet the conditions to reduce the number of table returns.

At the end

Mysql practice is 45 lectures in total, I will write a few, maybe, come on, if there is a mistake or wrong can point out, everyone can give me a little praise.