Index in MySQL

What is index ？

simply , The emergence of index is to improve the efficiency of data query , It's like a catalogue of books , You can quickly check and browse the contents of the whole article .

Common models of indexes ：

1. Hashtable ：

        Hash represents a key - The structure in which values store data , We just type in The key to be found is key, You can find the corresponding value, that is value. The idea of hash is ： Put the value into the array , Then use a hash function to put key Convert to a certain location , And then put value Put this in the array ;

         But there are disadvantages in this way , It may cause position repetition ; Multiple key Value is converted by hash function , The same situation may occur . One way to deal with this situation is to list a linked list .

        Take the following example ： Suppose you now maintain a table of names of new information on your ID card , You need to find the corresponding name according to the ID number. , The diagram corresponding to hash is as follows ：              

        Look at the picture and you can see ID_card_n2 and ID_card_n4 The calculated values are N, But you can see it all N Behind is a linked list , It has User4 and User2 Block of , If you want to check User2 The data of , First ID_card_n2 The value calculated by the hash function is N, Then traverse the list in order to find , eureka user2.

        In front of the diagram ID_card_n1,ID_card_n2... These values do not increase incrementally , When they are increasing, they only need to add later , In this case, add new User When , It's going to be fast , But corresponding , Because it is not input in order , Therefore, the speed of interval search will be very slow （ So when searching, you can use the method of equivalent search ）

  Ordered array ：

The performance of ordered arrays in equivalent interpolation and range query scenarios is excellent .

Still take the above example ： In the case of an ordered array , It is saved in the order of increasing the number of arrays ; So when you also want to find ID_card_n2 Corresponding name , It is OK to use the way of binary search to query

Two points search ： Binary search is also called half search , But to use the binary search method, the data that needs to be stored is in a sequential storage structure , Suppose there are array elements 50 In turn, increasing , The number you want to query is 11, So first of all 50 It is divided into 1~25 and 26~50, Compare and teach first 11 Which one is it in , Then continue to 25 Divide it in half , Continue to judge , Finally, the sequence traversal is carried out in the half element for comparison , Find the corresponding matching number .

  You can see it , When there is no duplicate ID number , The order he arranges is saved by increasing , And the binary search method can quickly be split and found , But because the ordered array is saved in an increasing order , So it will be troublesome to update the data , In particular, it will be more troublesome to insert in the middle . therefore Ordered array indexes are only available for static storage engines for example ： It is very suitable to save all the population information of a city in a certain year, etc., which will not be modified .

Number of binary searches

Binary search tree can also be called binary search tree , That is, each node has a tree structure with at most two subtrees , Subtrees are usually called left subtrees and right subtrees

The characteristics of binary search tree are ： The value of all nodes in the left child tree of the parent node is less than that of the parent node , The value of all nodes in the right subtree is greater than that of the parent node . Also take ID number to find your name as an example ,

  Looking for ID_card_n2 When the corresponding name , The order of inquiry he experienced :【UserA>UserC>UserF>User2】 This time complexity is O(log(N)).

To maintain this time complexity , You need to keep this tree a balanced binary tree , Again , For this guarantee , The updated time complexity is also O(log(N)).

Balanced binary trees ：

Each node of this balanced binary tree has a data area , This means that every access requires access to the disk ; So in order to minimize the number of disk reads for a query , The query process must access as few data blocks as possible . Then binary trees should not be used , But to use “N” Fork tree , there N It depends on the size of the data block .

Here comes a problem ：N Fork tree N Whether it can be artificially modified ？

(38 Bar message ) MySQL /“N Fork tree ” Of N Values in MySQL Can it be adjusted manually _Ruo_Xiao The blog of -CSDN Blog

  At the same time, it involves B- Trees and B+ The concept of trees .

InnoDB The index model of

        stay InnoDB in , Tables are stored in the form of indexes according to the order of primary keys , The table with this storage method is called index organization table . meanwhile InnoDB It uses B+ Index model of tree , So data exists B+ In the tree ; At the same time, each index is in InnoDB Corresponding to a lesson B+ Trees .

        The leaf node of the primary key index stores the whole row of data . stay InnoDB in , Primary key indexes are also called clustered indexes

        The leaf node content of the non primary key index is the value of the primary key , stay InnoDB in , Non primary key indexes are also called secondary indexes

What's the difference between a query based on a primary key index and a normal index ？
        for instance ： If the statement is select*from T where ID =500, That is, the primary key query method , Just search ID The star B+ Trees ; If the statement is select *from T where k=5; That is, common index query method , You need to search for elements first K Tree index , obtain ID The value of is 500, Until then ID Index tree search once , This process is called back to table .

          Suppose you build a data table , Set the primary key column as ID, There are fields in the table K, And in K There's an index on .

create table T(
id int primary key,
K int not null,
name varchar(16),
index(k))engine=InnoDB;

When we are executing a query statement ：select*from T where K between 3nd 5; 

  In this way, we can divide into 2 Index tree , Namely K Index and ID The index of , If you want to execute a SQL Query statements , First, in the K Found on the index tree of K=3 The record of , got it ID=300, And then in ID Search on the index tree of ID by 300 Username , When ID=300 When ,name=R3.

        In the process , Go back to the process of searching the primary key index tree , It's called back watch . by K The index tree goes to ID The process of index tree .