The principle of MySQL index algorithm and the use of common indexes

MySQL Index principle

1、 data structure

B Tree refer to Balance Tree, That's the balance tree . Balance tree is a search tree , And all the leaf nodes are on the same layer , as follows ：

B Tree

B+ Tree Is based on B Tree And leaf nodes , It has B Tree Balance , And provide query performance through sequential pointers , Here's the picture ：

B+ Tree

2、 Data manipulation

DDL： Start the binary search from the root node , Find one key The pointer where the , Then recursively find the node indicated by the pointer . Until you find the leaf node , Then binary search on the leaf node , find key The corresponding data.

DML： Adding or deleting will destroy tree Balance , After insert delete , Need to be right tree Make a split 、 Merge 、 Rotation and other operations to maintain balance .

MySQL Index type

MySQL The index of is divided into two categories according to the storage mode ： Clustered index ： Also known as Clustered Index. The physical order of relational table records is the same as the logical order of indexes . Because a table can only be stored in one physical order , A table can only have one clustered index at most . Compared to nonclustered indexes , Clustered index has faster retrieval speed .

MySQL Only in Li INNODB Tables support clustered indexes ,INNODB Table data itself is a clustered index , That is to say IOT, Index organization table . Non leaf nodes are stored in primary key order , The leaf node stores the primary key and the corresponding row records . So for INNODB It's very fast to scan the whole table sequentially .

Nonclustered indexes ： Also called Secondary Index. It means that non leaf nodes are stored according to the key value order of the index , The leaf node stores the index key value and the corresponding primary key value .MySQL In addition to INNODB Outside the primary key of the table , The others are secondary indexes .MYISAM,memory The table indexes of the engine are all nonclustered indexes . To put it simply , The index is stored separately from the row data . A table can have multiple secondary indexes .

Suppose the table contains the following data ：

select * from t1;
+-------+----------+--------+------+--------------+
| id    | username | gender | age  | phone_number |
+-------+----------+--------+------+--------------+
| 10001 |  floret      |  Woman      |   18 | 18501877098  |
| 10005 |  petty thief      |  Woman      |   21 | 15827654555  |
| 10006 |  The small white      |  male      |   38 | 19929933000  |
| 10009 |  Xiao He      |  male      |   35 | 19012378676  |
| 10002 |  Xiao Wang      |  male      |   20 | 17760500293  |
| 10003 |  Xiao zhao      |  Woman      |   29 | 13581386000  |
| 10004 |  indigo plant      |  Woman      |   25 | 13456712000  |
| 10007 |  millet      |  male      |   23 | 19800092354  |
| 10008 |  Xiao Xu      |  Woman      |   22 | 18953209331  |
+-------+----------+--------+------+--------------+

MYISAM Storage engine introduction

Primary key field index tree ：

Nonclustered index tree ：

INNODB Storage engine

Primary key field index tree ：

Nonclustered index tree ：

1、B+ Tree Indexes

majority MySQL By default, all storage engines are B+ Tree, Because you do not need to perform a full table scan , Just search the tree , So the query speed will be much faster .InnoDB Of B+Tree Index is divided into primary index and secondary index . The leaf node of the primary index data The domain records the complete data record , This way of indexing is called clustering index . Because you can't store rows in two different places , So a table can only have one clustered index . Of the leaf node of the secondary index data The domain records the value of the primary key , So when using a secondary index to look up , You need to find the primary key value first , Then go to the main index to find .

2、 Hash index

Hash index can be used to O(1) Time to search , But there's no order ：

• Cannot be used for sorting and grouping ;
• Only exact search is supported , Cannot be used for partial and range lookups .

InnoDB The storage engine has a special function called “ adaptive hash index ”, When an index value is used very frequently , Will be in B+Tree Create a hash index above the index , In this way B+Tree Index has some advantages of hash index , For example, fast hash lookup .

Distribution map of hash index （ Picture source network ）

3、 Full-text index

MyISAM The storage engine supports full-text indexing , Used to find keywords in text , It's not a direct comparison of equality .InnoDB Storage engine in MySQL 5.6.4 Full text indexing is also supported in the release .

4、 Spatial index

MyISAM The storage engine supports spatial data indexing （R-Tree）, It can be used for geographic data storage . Spatial data indexes index data from all dimensions , You can effectively use any dimension to perform combined queries .

Common index

1、 Independent columns

An index column cannot be part of an expression , It can't be an argument to a function , Otherwise, the index cannot be used .

select * from t_data_json where v_commission_amount+1 >30 limit 10

2、 Multi column index

When you need to query with multiple columns as criteria , Using multiple column indexes is better than using multiple single column indexes .

3、 The order of index columns

Put the most selective index column first . Index selectivity means ： The ratio of the non duplicate index value to the total number of records . The maximum value is 1, At this time, each record has a unique index corresponding to it . The more selective , The more distinct each record is , The more efficient the query is . This is why some fields of enumerated values are not recommended to be indexed .

4、 Prefix index

about BLOB、TEXT and VARCHAR Column of type , Use prefix index properly , Index only the beginning characters . Select the appropriate prefix length , It can save space , You can also avoid adding more query costs . The higher the discrimination, the higher the performance , This means that there are fewer duplicate values .

The advantages of indexing

• Greatly reduce the number of data rows that the server needs to scan .
• Help servers avoid sorting and grouping , And avoid creating temporary tables （B+Tree The index is ordered , It can be used for ORDER BY and GROUP BY operation . Temporary tables are mainly created during sorting and grouping , There is no need to sort and group , There is no need to create temporary tables ）.
• Will be random I/O Change to order I/O（B+Tree The index is ordered , Will store the adjacent data together ）.

Reference resources B+ Tree Demo address ：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Index design （ Prefix index ）：https://opensource.actionsky.com/20210120-mysql/

Index design （MySQL Index structure of ）：https://opensource.actionsky.com/20201111-mysql/