MySQL index (easy to handle in one article)

Catalog

Index advantages and disadvantages

Index structure

B-Tree

B+Tree

Hash

Interview questions

---

Index is help MySQL Efficient access to data Of data structure （ Orderly ）. Out of data , The database system also maintains a data structure that satisfies a specific search algorithm , These data structures are referenced in some way （ Point to ） data , In this way, advanced query algorithms can be implemented on these data structures , This data structure is the index .

Index advantages and disadvantages

advantage ：

• Improve the efficiency of data retrieval , Reduce the IO cost

• Sort data through index columns , Reduce the cost of sorting data , Reduce CPU Consumption of

shortcoming ：

• Index columns also take up space

• Indexing greatly improves query efficiency , But it reduces the speed of update , such as INSERT、UPDATE、DELETE

Index structure

B-Tree

The disadvantage of binary tree can be solved by red black tree ：

Red and black trees also have a large amount of data , Deeper levels , The problem of slow retrieval speed .

In order to solve the above problems , have access to B-Tree structure .
B-Tree ( Multiway balanced search tree ) At a maximum degree （max-degree, Refers to the number of child nodes of a node ） by 5（5 rank ） Of b-tree For example （ Each node can store up to 4 individual key,5 A pointer to the ）

Demo address ：B-Tree Visualization https://www.cs.usfca.edu/~galles/visualization/BTree.html

B+Tree

chart ：

Demo address ：B+ Tree Visualization https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

And B-Tree The difference between ：

• All the data will appear in the leaf node

• Leaf nodes form a one-way linked list

MySQL Index data structure for classic B+Tree optimized . In the original B+Tree On the basis of , Add a pointer to the linked list of adjacent leaf nodes , So we have a sequence pointer B+Tree, Improve the performance of interval access .

Hash

Hash index is to use a certain hash Algorithm , Convert key values to new hash value , Map to the corresponding slot , Then stored in hash In the table .
If two （ Or more ） Key value , Map to the same slot , They produced hash Conflict （ Also known as hash Collision ）, It can be solved by linked list .

characteristic ：

• Hash Indexes can only be used for peer-to-peer comparisons （=、in）, Range query is not supported （betwwn、>、<、...）

• Cannot complete sort operation with index

• High query efficiency , Usually only one search is needed , Efficiency is usually higher than B+Tree Indexes

Storage engine support ：

• Memory

• InnoDB: It has adaptive function hash function ,hash The index is the storage engine B+Tree The index is automatically built under specified conditions

Interview questions

1. Why? InnoDB The storage engine chooses to use B+Tree Index structure ？

• Relative to a binary tree , Fewer levels , High search efficiency
• about B-Tree, Whether leaf nodes or non leaf nodes , Data will be saved , This results in fewer key values stored in a page , The pointer decreases as well , Save a lot of data as well , Can only increase the height of the tree , Resulting in reduced performance

• be relative to Hash Indexes ,B+Tree Support range matching and sorting operations