MySQL index bottom layer (I)

Database notes

• Mysql Index bottom layer （ One ）
• Explain Tools and index optimization （ Two ）
• SQL stay MySQL Execution process in （ 3、 ... and ）
• MySQL Index optimization （ Four ）
• MySQL Transactions and locks （ 5、 ... and ）
• MVCC and BufferPool（ 6、 ... and ）

Indexes

Definition of index

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

Index data structure

Binary search tree

1. Definition

According to the binary search tree definition （ Left small right big ）, Index

• key —— The value of the index

• value —— Memory address of the data item

2. shortcoming
stay key In a monotonous situation , Will degenerate into a linked list structure , Don't use

3. chart

hash structure

1. Definition

Hash the index to get the storage location

2. characteristic

• Evaluation of index key Do it once. hash Calculation can locate the location of data storage

• A lot of times Hash Index is better than B+ Tree indexing is more efficient

• Can only satisfy “=”,“IN”, Interval queries are not supported 【 Use B+ The reason for the tree 】

•hash The question of conflict

3. chart

B Trees

1. Definition

Is a multi-path balanced lookup tree , Nodes store data and indexes

2. characteristic

• Orderliness —— The data indexes in the node are incrementally arranged from left to right
• Uniqueness —— All index elements are not duplicate
• leaf —— Leaf nodes have the same depth , Leaf node pointer is null

3. B Tree as index

• Lifting performance —— B Trees can be effective Reduce The depth of the tree I/O Frequent reading and writing The problem of

• data data Bound in index , It is more convenient to find data

MySQL The index of does not use B Trees

4. chart

B+ Trees

1. Definition

Is a multi-path balanced lookup tree , Non leaf nodes store only indexes

MySQL The indexes of databases such as B+ Tree data structure to store indexes

2. characteristic

• Large storage capacity —— Non leaf nodes do not store data, Store index only （ redundancy ） More indexes can be placed
• It's easy to find the interval —— Two way linked list structure is used between leaf nodes , It's easy to find the interval
• Orderliness —— The data indexes in the node are incrementally arranged from left to right
• Uniqueness —— All index elements are not duplicate
• leaf —— Leaf nodes have the same depth , Leaf node pointer is null

3. Read data step

example ： Inquire about key=30 The data of

1. Load the data of the root node from disk to memory once I/O
2. In memory , Use binary search to find key Address on the next page Two points search
3. According to page address , Load the data of the next node from disk to memory once I/O
4. repeat 2,3
5. Find the leaf node , Can read data data

4. InnoDB Page size of

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

adopt B+ Trees store data ,（ Suppose the data item size is 1KB） Can be stored 1170*1170*16 Data items

MySQL The index of the root node will be cached in memory , Greatly improve the query speed , Usually, the query only costs one disk I/O Time for

5. chart

Storage engine

MyISAM

1. Definition

MyISAM yes MySQL The default database engine for （5.5 Prior to version ）, Index files and data files are separate 【 Non aggregation 】

2. form
MyISAM Data sheet , All by... Stored on the hard disk 3 File The composition of

File naming ：【 Data table name + Different extensions 】

• .frm－－ Storage data table definitions
• .MYD－－ Store real data
• .MYI－－ Store index information

4. chart

InnoDB

1. Definition

InnoDB, yes MySQL One of the database engines of , Now is MySQL The default storage engine for

2. form
InnoDB Data sheet , All by... Stored on the hard disk 2 File The composition of

File naming ：【 Data table name + Different extensions 】

• .frm－－ Storage data table definitions
• .ibd－－ Store data and index

4. characteristic

• B+Tree —— The data table file is based on B+Tree Organization's index structure file
• Leaf nodes —— Leaf nodes contain complete data records
• primary key —— A table must have a primary key
• Non primary key index —— The leaf node of non primary key index structure stores the primary key value 【 Uniformity 】

5. chart

Index classification

Clustered index

1. Definition

   The leaf node of its index tree stores the whole row of data , The physical order of the rows in the table and the logic of the key values （ Indexes ） Same order .【 Through two-way linked list to achieve 】 A table can only contain one clustered index . Because index （ Catalog ） You can only sort in one way .

Xinhua dictionary , A clustered index is like a Pinyin Directory

2. Check data

   The clustered index passes key Find find specific data items

Nonclustered indexes

1. Definition

   Because the index file and the data file are separated , The logical order of the indexes is different from the physical storage order on the disk

   Nonclustered index （ General index ） The content of the leaf node is the value of the primary key . stay InnoDB in , Non primary key indexes are also called secondary indexes （secondary index）.

Nonclustered indexes are like the partial Dictionary of Xinhua dictionary , The sequence of other structures may not be consistent with the actual storage sequence

2. Check data
   1. The nonclustered index passes through key To query the value of the record primary key
   2. Query specific data items according to the value of the record primary key 【 Back to the table 】

Joint index

1. Definition

A union index is an index composed of multiple fields .

2. How to use the union index ？

Use according to the leftmost prefix principle

Index leftmost prefix principle

1. Definition

When walking the union index , The conditions should be satisfied from left to right , An integral

2. Example

Set up a joint index

idx_a_b_c (a,b,c) USING BTREE

• SQL One

  select  * from test where a = '333' and b = '333' and c = '333';
  

  Let's go , Because there is bc In the presence of ,a There is

• SQL Two

  select  * from test where  b = '333' and c = '333';
  

​ It's not going to be a union index , because bc In the presence of ,a non-existent

• SQL 3、 ... and

  select  * from test where a = '333' and b = '333';
  

​ Let's go , because b In the presence of ,a There is

3. summary

The so-called leftmost prefix principle , Namely where Condition must have the first field of the union index , Otherwise, the union index will not be used .

problem

Q： Why use indexes ？

• Random data storage —— The records in the table are randomly stored on disk , It doesn't have to be continuous , Reading data , Do it once with the disk I/O Interaction

• Quickly locate data —— Index based , It is not necessary to scan the whole table , Quickly navigate to data

Q：B Trees and B+ Tree difference ？

• performance —— B+ The tree is on disk I/O When , No data items need to be loaded , Just load the index entries ; and B The tree needs to load data and indexes ,B+ Trees perform better
• Interval search —— When interval search is required ,B+ The tree can be searched according to the bidirectional linked list structure of leaf nodes , Than B Trees perform better

Q： Why? InnoDB It is recommended to create a primary key for the table , It also recommends the auto increment primary key of integer type ？

1. Primary key

   • InnoDB Of ibd Files need to be created through a primary key B+ Index structure of tree
   • If there is no primary key ,InnoDB Will scan each column and select one not null And unique Columns as indexes
   • If you find a column that meets the requirements , A built-in... Is generated by default 6 Byte long ROWID Column As an index

2. Since the primary key

   • Use auto increment primary key
     • Every time a new record is inserted , Records are added to the subsequent locations of the current inode in order , The order of primary keys is arranged according to the insertion order of data records , Automatic ordering . When a page is full , Will automatically open a new page
   • Use non self incrementing primary keys
     • The value of each inserted primary key is approximately random , So every time a new record is inserted into the middle of the existing index page , Move the data in order to insert the new record in the right place , Even the target page may have been written back to disk and purged from the cache , Now I want to read it back from the disk , This adds a lot of overhead , At the same time, frequent movement 、 Paging causes a lot of fragmentation , Get an index structure that is not compact enough , I have to go through OPTIMIZE TABLE To rebuild the table and optimize the page population .

Q： Why do leaf nodes of non primary key index structure store primary key values ？

The non primary key index structure is a secondary index

• Save storage space —— InnoDB The data itself is already in the primary key index B+ on the tree , The secondary index does not need to save another copy of data , Save a space .
• Uniformity —— When data needs to be updated , Just modify the clustered index , There is no need to refactor the secondary index , No need to maintain multiple copies of data .

Q： Why should the union index follow the leftmost prefix principle ？

Because the data structure of the federated index is still B+ Organized in a tree structure , The index is maintained with First field to prioritize , When the query condition does not have the first field, there is no way to compare the positioning data through the index

When there is no first field , If the second field goes through the union index, it will be unable to be sorted , Because the order of the second field is a local order based on the equality of the first field . The following fields are the same