Scan the qr code below or search the wechat public account, you can follow the wechat public account, read more Spring source analysis, Java concurrent programming and Netty source code series articles.


MySQL uses B+Tree as an index, not a B-tree, but an array, hash table, binary search Tree, red black Tree, etc.

As a data storage component, MySQL’s main operation is to add, delete, change and check data, among which the query operation is the most important. Most of what we call database optimization is query-related operations. Therefore, the main consideration for a database to choose a data structure as an index is the efficiency of this data structure for add, delete, change and search operations, especially query operations (usually query operations include equivalent query, range query, etc.). Next, this paper will analyze why MySQL finally chooses B+Tree as the data structure of the index from the perspective of adding, deleting, modifying and checking.

Since the default storage engine of MySQL is InnoDB after version 5.5, all the content discussed in this article is based on the premise that the storage engine is InnoDB.

An array of

Arrays are probably the first data structures we’re going to encounter when we start programming. Array is a contiguous memory space in memory, define an array object, the object pointer to the starting address of the memory, if you know the array subscript elements, you can calculate the memory address of the corresponding element subscript, so you can within the time complexity of O (1) to get to the elements, very fast.

For an ordered array, the binary search method can be used in the search process, the time complexity is O(logn), and the efficiency is very high. Because it’s an ordered array, it’s also very range-friendly, finding only the starting element. Updates are also fast if we know the subscripts of elements, and deletes are fast if we ignore voids (if we simply null the element at the corresponding subscript, we have a void in the contiguous memory block).

Given that arrays are efficient for query, delete, and update operations, the choice of array as a data structure for MySQL indexes seems to be a good one. We ignore and insert operation, however, if we want to insert a data array, we need to put in the array to be inserted after the target location of all the elements to move back one location, and then insert the new data, also is the copy operation, involves an array of data to insert the front, so we need the more data it can copy, This not only requires extra memory, but also takes a long time to copy the data. In normal development, the size of a table in the production environment is often more than 1GB, so if you want to insert a piece of data in the middle, how much data must be copied!

Therefore, arrays are not suitable as data structures for MySQL indexes from the point of view of inserting data.

Hash table

Hash table is a key-value form of data structure, which is realized by array + linked list structure at the bottom. It calculates a number through a hash function for key, and then takes the number as the subscript of the array, and stores the value in the array with the corresponding subscript. For different keys, the same value may occur after calculation by hash function, which is called hash conflict. In this case, it means that two elements need to be stored at the subscript of the same array. Therefore, at this time, the elements in the array are changed into a linked list, and the two elements are connected through the linked list.

According to the characteristics of the above hash table, hash table for delete, search, update, insert operations, first calculate a value according to the key, can locate the target location of the data, time complexity is O(1), very fast. But when we use MySQL, we often encounter to find a certain range of data, such as between… And, >=, <=, etc. What’s the hash table going to do at this point?

Because all key hash table after a hash function calculation, and then to store data, could have been ordered the key, but after a hash function calculated values, it is not in order, so this time, if you want to range in the hash table lookup, can only to traverse the whole hash table, only qualified range of data only. As our database grows into millions or even tens of millions of entries, it becomes time consuming to traverse the entire table.

Therefore, in the context of range queries, hash tables are also not suitable as data structures for MySQL indexes. What are the scenarios for hash tables? Suitable for equivalent query scenarios, the most classic scenario is NOSQL database, such as the most commonly used redis, redis is not all key-value?

In fact, there are places in MySQL where hashes are used as indexes. Navicat is a visual MySQL client remote connection tool. In this tool, we can perform database related operations in the visual interface, such as add, delete, change, query, modify table structure, create index, etc. When creating an index, we can actually choose the data structure of the index. It has two options: B+Tree and HASH. If you don’t check it, the default is B+Tree. As shown in the figure below.

Generally, it is not recommended to set the index structure to HASH unless the service scenario complies with the key-value scenario, such as the table and data dictionary of some key-value configuration items of the service system.

Binary tree

A tree with at most two children in each node is called a binary tree. Special and commonly used binary trees include binary search tree, AVL tree (balance tree), red-black tree and so on.

For a binary search tree, the time complexity of the search operation is the height of the tree, and the optimal case, that is, the full binary tree, is O(logn). In extreme cases, the binary search tree may degenerate into a linked list, and its search time complexity becomes O(N), so its performance is not stable.

Balanced tree is based on the binary search tree, add a restriction, the height difference between the left and right subtrees can not exceed 1, the left and right sides are relatively balanced, so it is called balanced tree. In the process of dynamic data deletion and insertion, in order to maintain balance and avoid tree degradation into linked list, additional rotation operations are required after deletion or insertion of data, which will lose certain performance. However, overall, the complexity of its search, deletion, insertion and update is O(logn). Its middle-order traversal, the data is ordered, so it is also suitable for range lookup. However, its disadvantage is that the rotation operation is too complicated to maintain balance.

On the basis of balanced binary trees, red black trees appear, about the properties of red black trees will not be detailed here, too much content, later will be a separate blog introduction. On the whole, red-black tree is a kind of approximately balanced (incomplete balanced) tree with either black or red nodes. Its tree height is no more than 2logn, so the time complexity of search is O(logn). Its performance is very stable whether it is adding, deleting, changing or searching. In engineering, red-black tree data structure is used in many places, such as HashMap and TreeMap in Java.

At first glance, the AVL tree and red black tree add, delete, change and check performance are very stable, although the middle involves a lot of rotation operations, implementation is too complex, but can still be implemented in code, as long as it can be implemented, it is not a matter of ah, good performance, enough stability. Why not use AVL and red black trees as MySQL index data structures?

This is because whether it is binary search tree, AVL tree, or red-black tree, they are all a type of binary tree, and each node has at most two children. If a large amount of data is stored, the height of the tree will be very high. And MySQL to store data in the end is to be born to disk, MySQL application reads the data, the need to the data from disk loaded into memory before they can continue to operate, so the middle disk IO will happen, but if the tree is too high, each layer node traversal, requires a data read from the disk, namely one IO, If the data is at 20 tree height, it will take 20 IO to find the data, which is disastrous for the application and takes too long. Therefore, binary tree is not suitable as an index data structure in the context of MySQL, which needs to store a large amount of data. Because the tree is too high, multiple DISK I/OS will occur during data operation, resulting in poor performance.

B-tree and B + Tree

Given binary tree each node has at most two child nodes, in a large amount of data storage eventually lead to tree height is too high, so there is no fit as MySQL index, then let the tree of each nodes have more child as much as possible, also is many forks tree, that such in a large number of stored data, tree job is much lower, that this should be ok! Typical examples of multi-fork trees are B-tree and B+Tree.

B-tree has index values and data regardless of leaf nodes and non-leaf nodes. B+Tree: only leaf nodes store index values and data. Non-leaf nodes only store index values. Therefore, for non-leaf nodes, the number of index values stored by B+Tree in one node will be much larger than that by B-tree (because the space of a node is limited, B-tree needs to store index + data, while B+Tree only needs to store index), so that in each node, B+Tree has more branches down, more subnodes.

Therefore, if B+Tree is used to store data files of the same size, the height of the Tree will be much smaller than that of b-tree. Therefore, if B+Tree is used as the data structure of MySQL index, disk I/O times will be fewer and the performance will be better when data is read in the future. So the final MySQL index data structure uses B+Tree.

If you want to know more about B+Tree and B-tree, you can read the following two articles: B-tree and B+Tree (part 1) and B-tree and B+Tree (Part 2).

The second part of the article “Index data structure b-tree and B+Tree (Part 2)” spends a long time explaining why MySQL uses B+Tree instead of B-tree as the index data structure.


This article analyzes in detail why MySQL finally chose B+Tree as the index structure from the characteristics of each data structure, but by now, I believe you should have a certain understanding of MySQL index. In the process of contact with MySQL, you must have heard a lot of index terms, such as: primary key index, clustered index, non-clustered index, secondary index, unique index, overwrite index, full text index, union index, etc., do you know what they mean respectively? In the next article.

The resources

  1. Geek time Lin Xiaobin “MySQL Combat 45 talk”.

Related to recommend

  • Redo log — How MySQL data does not lose when it is down
  • Index Data Structure of B-tree and B+Tree
  • Index Data Structure of B-Tree and B+Tree