MySQL's heart index

Indexes

Indexes Help MySQL Efficient access to data Arrange order well Of data structure .

1. Why index ？

Indexes Help MySQL Efficient access to data Arrange order well Of data structure .

• If there is no index , The lookup table starts from the first row of data , It will make the database and disk directly do a lot of IO operation . Reduce efficiency .

  such as ：select * from t where t.col = 89; Will take out one by one for comparison .

2. What is? B+ Trees ？

• B+ The non leaf node of a tree , Save index only , Without saving data , therefore B+ Tree ratio B The trees are shorter and stronger . That means ,B+ Tree retrieval will be faster

• B+ The leaf node of a tree is a Orderly Double linked list , Traversal query is more convenient .

• B+ A node of the tree occupies a page , One page is about 16k. Each query , Load a page into memory to query （ For example, binary query ）. Here's the picture , It's just a node （ One page ）：

  

  h=3 Of B+ Trees can almost put 2 Millions of data .

B+ Tree query process

• RAM It's memory

Why not use a binary search tree ？

• If the data is incremental （ Or decreasing ） Of , The search binary tree becomes a linked list . It's the same as full table query .

Why not use the red and black trees ？

A red black tree is a binary balanced tree . The height difference between the left and right subtrees shall not exceed 1.

• Red black tree is also a kind of binary tree , So when there's a lot of data , The height of the tree is high .

b Where trees are stronger than red and black trees

• Red black tree is a kind of " Binary search tree ", Every node Only one pair of nodes can be saved key,value

• B or B+ Trees are a kind of ” Multiple search trees “, Every node Nodes can store multiple data

• therefore , By comparison ,B perhaps B+ Trees are lower than red and black trees , Lower height means faster retrieval .

Why not Hash surface

• Can only satisfy =, IN Query for , Range query is not supported

  Such as query col > 10

• hash There is a problem of conflict

Why not B Trees ？

B Trees

• B+ Compare trees B Trees , There are two advantages

  • Shorter and stronger ：B+ The non leaf node of a tree , Save index only , Without saving data , therefore B+ Tree ratio B The trees are shorter and stronger . That means ,B+ Tree retrieval will be faster

  • Leaf nodes are ordered and bidirectional linked ：B+ The leaf node of a tree is a Ordered two-way linked list , Traversal query is more convenient , In particular, it supports range search . and B Not trees .

3. Why suggest innoDB A table must have a primary key , And is auto_increment

• If you do not use self incrementing primary keys ,B+ The tree will select a unique column that does not duplicate to create data , without , Will maintain a row_id, But it's going to make me happy MySQL Multidimensional protection of a column of data , And this data itself can avoid .

• The primary key should be self incremented ：B+ The leaf nodes of the tree are arranged in order , If the primary key index is not self increasing , Newly inserted data may be inserted between intermediate nodes , This may lead to tree imbalance and take time to rebalance .

What is return watch

The back table will be based on the query of non primary key index Go back to the primary key index tree search The process of . That is, when a field other than the index column value is found through the non primary key index , Will return to the table .

such as ：

create table T (
    ID int primary key,
    k int NOT NULL DEFAULT 0, 
    s varchar(16) NOT NULL DEFAULT '',
    index k(k)) engine=InnoDB;
​
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

Execute at this time select * from T where k between 3 and 5：

1. First in k Index tree found k = 3 Data record of , find id = 300

2. Then go to the primary key index tree , find id = 300 Data record of

3. This process is going back to the table

reason ：

• Because the non primary key index is established B+ The data table of the tree leaf node stores the index column values and primary keys .（ The clustered index stores the primary key and all other column values ）

• therefore , If you want to query a value other than the index value , First, find the corresponding primary key value through the non primary key index , Then go through the primary key value Cluster index B+ Trees Find the corresponding data row , Read again and get the data to be queried .

• such as ,MySQL Adopt non primary key index name As an index , So the bottom floor B+ Trees store name Column value and primary key id. If you use it at this time sql Inquire about

  select * from student where name = "James"

  that MySQL You can only query name Column values and corresponding id, Other column values must pass this id, Then go to the cluster index to save B+ Trees , Find the corresponding data and read . This is the back table .

How to avoid returning to the table

By overwriting the index .

• Is to establish a joint index , Make the query time , The desired result is already on the leaf node , There is no need to perform the operation of returning tables .

• For example, if you want to check orderId and orderName, Then take these two fields as the joint index . such orderId and orderName Save it as data in B+ The leaf node of the tree , There is no need to return to the table .

Overlay index

Fields to be queried , Build it into a joint index

scene 1： Full table count Query optimization

The original table is ： user(PK id, name, sex);

direct ： select count(name) from user; Cannot use index overlay .

Add index ： alter table user add key(name); We can use index coverage to improve efficiency .

What is a joint index ？

Leftmost prefix principle / Left most matching principle

B+ Tree is an index structure , Available with index “ Left most prefix ”, To locate records .

(I) For example, the index in the above figure is index(name, age)

• such as

  • The query conditions are where name = ' Zhang San ', Then we find (" Zhang San ", 10), id=4 The record of , Then go back and iterate over all the values that meet the conditions

  • The query conditions are where name like ' Zhang %', Then we find (" Zhang Liu ", 30), id=3 The record of , Then go back and iterate over all the values that meet the conditions

• therefore , As long as the leftmost prefix is satisfied , You can use the index to speed up the search .

  therefore , When indexing , Consider the index order . such as , The index of resident identity information only needs to be established (card_id, name) and (name) That's it , You can't create one alone (card_id)

Index push down

When there is a joint index (name, age) when , If we execute the following statement ：

select * from user_info where name=" king %" and age=20 and ismale=1;

• stay mysql 5.6 Before , The query will first pass name Go to the union index (name, age) Query in tree , Find multiple matches name=" king %" The data of , And then according to id Trigger the table return operation , Go to the primary key index to find qualified data , The whole process needs to be reported many times .

• mysql 5.6 after , With index push down . Inside the index, you will first judge age Is it equal to 20, In this way (name, age) Only one data will be found in the union index tree , Then take id Go back to the table and find the data . The whole process only needs to be reported once .

Clustering / Nonclustered index

characteristic ：

1. Use Primary key Value to sort records and pages .

   • The records in the page are arranged into a one-way linked list according to the size of the primary key

   • Each data page is arranged into a two-way linked list according to the size of the primary key

2. MySQL A table has only one clustered index .

3. If there is no primary key defined .

   • InnoDB Will choose a non empty unique index to replace .

   • If there is no such index , be InnoDB Will implicitly define a primary key as the cluster index .

shortcoming ：

1. The insertion speed depends heavily on the insertion order . So it's best to Self increasing ID Primary key , Otherwise, insertion will bring B+ The split of the tree .

2. Updating the primary key is expensive , Therefore, the primary key should be non updatable .

MySQL How to create an index ？

Three ways

1. CREATE INDEX <index_name> ON TABLE <table_name> (<column_name>)

2. ALTER TABLE <table_name> ADD INDEX <index_name>(<column_name>);

1. CREATE TABLE tableName(  
     id INT NOT NULL,   
     columnName  columnType,
     INDEX [indexName] (columnName(length))  
   );