Exploration of MySQL index

1 The essence of index

Index is help mysql A well ordered data structure for efficient data acquisition .

• Now suppose that the data structure of the index is to find the binary tree structure , The table structure shown in the figure above , The index field is col2, Building a lookup binary tree is the structure on the right ,eg:
• Now there's one sql sentence ,select * from t where t.col2 = 89;
• The process is to find the binary tree first , find 89 This node ( Node is a <k,v> The structure of storage ,k Is the index value 89,v Is the disk storage pointer of the row where the index is located 0x77).
• according to v Disk storage pointer , Make a disk io Operation can get data .

Be careful

• But if we don't have an index , The disk is traversed one by one in order io, Efficiency is too low , When the amount of data is large , It's impossible .
• When the index is a binary tree structure , What's the problem ？
  Or the example above , When our index is col1 Field time , At this time, the structure of the search binary tree is as follows , It has become a linked list structure .
  
  Similar to the above structure , Efficiency is too low , Every time you look for data , You have to go through it from the beginning in memory . So indexing binary tree is not feasible .

1.1 Red and black trees are indexed ？

• Characteristics of the red black tree ：
  • The root node is a black node ;
  • A red node , The corresponding child nodes are all black nodes ;
  • Leaf nodes are all black nodes , by NUll;
  • The number of black nodes on the path from any non leaf node to leaf node is the same ;
• Red black tree as a balanced binary tree , But it's different from AVL Trees , The red black tree changes by changing the color between node paths , The index will not appear. One path is the of other paths 2 Times longer , Compared with AVL Trees , The frequency of its self rotation balance is reduced a lot , In terms of performance AVL Better trees .
• Now it's still the above example , With col1 The field is index , Building a red black tree ：
  
  As mysql Index words , The problem is that when there are tens of millions of data in the table , So the depth of red and black trees is too deep , Queries are too slow . stay
  Looking at the use of col1 structure AVL The look of the tree ：
  
  AVL The tree is building (1-7) Spin when 4 Time , But the red and black tree spin is 3 Time , The performance of index red black tree is better .

1.2 mysql The underlying index is B+Tree structure ：

• Let's talk about it first B-Tree structure ：
  
  characteristic ： Multiforked tree , The depth of leaf nodes is the same , There are no pointers between leaf nodes ;
  All index elements are not duplicate , From left to right is self increasing .
  And the disk file pointer of index data is stored on the location of each index element ;
• B+Tree structure ：
  

1.3 mysql Storage engine MyisAM

• The table of the storage engine falls on the disk, and the corresponding files are three : xx.frm xx.MYI, xx.MYD
• xx.frm What is stored is the data related to the table structure ;
• xx.MYI Stored is index data ;
• xx.MYD What is stored is the data of the table ;
  
  The picture above is MyisAm The index storage structure of , Index and data are separated .

1.4 InnoDB Storage engine for

Index and data together .
The corresponding file on the disk is :xx.frm Table structure information
xx.ibd Store data and index
Leaf nodes store complete data , Reduce the operation of returning to the table .
Why? innodb The primary key of is recommended to be self incremented ？ Because the underlying data store is organized according to the primary key , If you don't add a primary key ,mysql The default primary key will be added . Integer index comparison size ratio UUID More efficient and efficient .
Self increase is due to b+tree With bidirectional pointers between leaf nodes , Convenient range lookup to retrieve data .
hash Type index can't solve the problem of access and search . So it just doesn't work .