Differences and application scenarios between MySQL index clock B-tree, b+tree and hash indexes

As mentioned earlier , A good index can speed up mysql Retrieval speed of , But in fact, there are different types of indexes , For example, different tools can also play a suitable effect in different application scenarios
mysql The current indexes mainly include B-TREE ,B+TREE ,HASH

1.HASH Indexes

Hash indexed key,value The format of is very suitable for indexing , For each row of data , The storage engine will calculate one hashcode,, Hash index will all hashcode Store in index , Save the pointer of each row of data at the same time
The disadvantage of hash index ：
1. Hash index only contains hash value and row pointer , Do not store field values , Therefore, you cannot use the values in the index to read rows , To adopt hashcode
2.hash The index is suitable for comparing equivalent queries , For some range queries, they are not stored in the order of index values , Therefore, it is not suitable for sorting
3. A lot of hash Conflict between , The cost of maintenance operations can be high

2.B-Tree Indexes

B Tree is a balanced multi-path search tree , We call the maximum number of subtrees of nodes in the tree B The steps of the tree . It's usually written as m.
B Tree lookup operation ：
B The search of a tree is actually very similar to a binary sort tree , It can be understood as m Sort tree by fork
① Let the keywords to be found first key Compare with the keywords in the node , If it is equal to a keyword , Then the search is successful .
② If it is not equal to all keywords , Then look at key In which range , Then go to the subtree pointed to by the corresponding pointer to find .
example : If Key Than the first keyword K1 Still small , Then go P0 Look in the subtree pointed to by the pointer , If it's better than the last keyword KN Also big , Then go PN Look in the subtree pointed to by the pointer .
First step ： Heel node 10 Compare , Not equal but better 10 Big , Go to the subtree on the right to find ;
The second step : And keywords in the right subtree 14 Compare , Not equal but better 14 Small , So go to the left sub tree to find ;
The third step ： And keywords in the left subtree 11 Compare , equal , Get its data, return .
B Operations such as inserting and deleting trees are not described in detail , You can read this post if you need it https://www.cnblogs.com/xiaofengshan/p/15443140.html
advantage ：
B Trees can store keys and values at the same time in internal nodes , therefore , Putting frequently accessed data close to the root node will greatly improve the query efficiency of hot data . This characteristic makes B Trees in It is more efficient in the scenario of repeated query of specific data .

3.B+ Tree index

B+ Trees are B- A variation of a tree , It's also a multi-channel search tree . A tree m Step B+ Trees mainly have these characteristics ：
Each node has at most m Little girl ;
The range of the number of non root node key values ：⌈m/2⌉ - 1 <= k <= m-1
Adjacent leaf nodes are connected by pointers , And it is sorted by keyword size .

advantage ：
When a full data traversal is needed ,B+ Trees only need to use O(logN) Time to find the smallest node , And then through the chain O(N) The order of traversal can be . and B Trees need to traverse every layer of the tree , This will require more memory replacements , So it takes more time
B+ Trees and B- The main differences between trees are as follows ：
B- The nodes inside the tree hold the data ; and B+ The nodes inside the tree do not store data , Index only , Only its leaf node stores data .
B+ The adjacent leaf nodes of the tree are connected by linked list pointers ,B- Trees are not .
During the search ,B- The tree ends when it finds the value , and B+ The tree needs to find the data in the leaf node through the index to finish
B- Any keyword in the tree appears in only one node , and B+ Trees can appear many times .