preface

The title of this article is a real question I met in the interview process. An Internet crowd-funding company asked the interviewer the first question about MySQL related knowledge. I was quite confused at that time. Aren’t they all about index optimization and index failure? How is it still out, the storage file is different? Even if it’s an MVCC mechanic. So I’m going to summarize this part of the knowledge.

Why do you need an index

First of all, we all know that the purpose of indexing is to speed up queries, so why does having an index speed up queries? Let’s look at a schematic of an index.If I have an SQL statement that says:select * from Table where id = 15If there is no index, the whole table scan will be performed, that is, one by one, until it finds the record with id=15, and the time complexity is O(n);

What if you were to query with an index. Firstly, binary search is performed in the index value according to id=15. The efficiency of binary search is very high, and its time complexity is O(logn).

This is why indexes can improve query efficiency, but the amount of index data is also relatively large, so it is not stored in memory, is directly stored in disk, so to read the file content in disk, it is inevitable to perform disk I/O.

MySQL > select * from B+Tree

We also said the above, the index data is stored in the disk is commonly, but the calculated data are in memory, if index file is very big, and not once loaded into memory, so in the use of index data is when searching multiple disk IO, the partial load index data into memory, so a good index of data structure, If the correct result is obtained, the number of DISK I/OS must be the lowest.

Hash type

MySQL currently has two index data types to choose from, one is BTree (actually B+Tree), and one is Hash.

But why do most of them choose BTree in actual use?

If a Hash index is used, the MySQL system performs a Hash operation on the index data when creating the index. In this way, the disk pointer can be quickly located based on the Hash value. Even if a large amount of data is used, the data can be quickly and accurately located.

  • But likeselect * from Table where id > 15The Hash index can’t be sorted by a range query that scans the entire table.
  • In addition, although MySQL does a series of low-level processing, it is not completely guaranteed that Hash collisions will not occur.

Binary tree

So why doesn’t MySQL have binary trees as its index data structure? As we all know, binary trees locate data by binary search, so the effect is not bad, the time complexity is O(logn);But the problem with binary trees is that in special cases, they degenerate into a stick, which is a one-way linked list. At this point, its time complexity is reduced to O(n);So when we want to query the record with ID =50, it is the same as a full table scan. So because of this, binary trees are not suitable data structures for indexing.

Balanced binary trees

So if binomial trees degenerate into linked lists in special cases, why not balanced binomial trees?

The height difference between the children of a balanced binary tree cannot exceed 1, like the binary tree in the figure below, the node with keyword 15 has left child node height of 0 and right child node height of 1, and the height difference is no more than 1. Therefore, the tree below is a balanced binary tree.Because it can keep balance, so its query time complexity is O(logN), as for how to keep balance, mainly do some left rotation, right rotation, etc., the details of keeping balance are not the main content of this article, want to know can search by yourself.

What’s wrong with indexing MySQL with this data structure?

  • Disk IO too much: in MySQL, an IO operation read only one node, then, if a node is at most two child nodes, then only the two child nodes of the query range, so be accurate to a specific data, you need to read many times, if the tree is very deep, so will be a large number of disk I/o. Performance naturally degrades.
  • Low space utilization: For balanced binary trees, each node value holds one key, one data area, and two Pointers to child nodes. As a result, loading only so much data in a single hard IO operation is a bit of an overkill.
  • Query effect is not stable, if in a highly balanced binary tree, deep if the query data was the root node, you will soon find, if the query data was the leaf nodes, so will to return after multiple disk IO, response time and likely the root node is not an order of magnitude.

Although binary trees solve the problem of balance, they also introduce a new problem, that is, due to the depth of the tree itself, it can cause a series of efficiency problems.

In order to solve the problem of balancing binary trees, the balanced multi-fork Tree becomes a better choice.

Balance Tree– B-tree

B-tree means balanced multi-fork Tree. In general, the number of children of a node in a B-tree is called a B-tree of order. The order is usually denoted by m, and when m is 2, it’s a balanced binary tree.

Each node of a B-tree can contain a maximum of M-1 keywords and must be stored at leastMath.ceil(m/2)-1All the leaf nodes are in the same layer. The following figure shows a level 4 B-tree. So how does b-tree look up data:

  • To query the data whose ID is 7, load the node whose keyword is 20 into the memory first and find that 7 is smaller than 20.
  • So load the first child node, if the query data is equal to 12 or 17, it will directly return, not equal to continue to look down, find 7 is less than 12;
  • So continue to load the first child node, after finding 7, directly return the data below 7.

This operation actually performed three I/OS, but in reality, a typical B-tree has many branches per level (usually greater than 100).

To make better use of disk I/O capability, MySQL sets the operation page size to 16K, that is, the size of each node is 16K. If all the keywords in each node are of type int, the value is 4 bytes. If the size of the data area is 8 bytes, and the node pointer is 4 bytes, then the number of keywords that can be stored in each node of the B-tree is: (16 x 1000)/(4+8+4)=1000. Each node can store a maximum of 1000 keywords, and each node can have a maximum of 1001 branch nodes.

In this way, when querying index data, a disk I/O operation can read 1000 keywords into memory for calculation. A disk I/O operation of b-tree balances N disk I/O operations of binary data on top.

Note: B – Tree in order to ensure that the data of balance, to do a series of operations, the balancing process is time-consuming, so when creating an index to select the appropriate field, and don’t create indexes too much, create indexes too much, at the time of updating data, update the index of the process is time-consuming.

In addition, do not select low-distinction field values as the index, such as gender field, a total of two values, so that the depth of the B-tree may be too large, reducing the index efficiency.

B+Tree

B+Tree is used to balance binary trees and ensure query efficiency, so why there is B+Tree?

So let’s start with what B plus Tree looks like.

B+Tree is a variant of B-Tree. The relationship between the keywords of each node of B+Tree and the formula of order M is different from that of B-tree.

Firstly, the number of child nodes of each node and the proportion of keywords that can be stored in each node are1:1Second, the left closed interval is used to query data. In addition, there is no data in the branch node, only the key word and the child node point are saved, and the data are stored in the leaf node.So let’s see how data query is done in B+Tree.

Such as:

  • Now if you want to query the data with id=2, the root node will be removed first, loaded into memory, and foundid=2Exists in the root node, because it is a left closed interval to store data, soid<=2Are on the first child of the root node;
  • Take out the first child node, load it into memory, and find the current node existsid=2, and has reached the leaf node, then directly retrieve the data in the leaf node to return.

Now let’s look at the difference between b-tree and B+Tree

  • B+Tree uses the left closed range to better support the query effect of the auto-increment index. Therefore, primary keys are usually auto-increment. This is different from the B-tree.
  • In B+Tree, no data is stored on the root node and branch node, and the data related to the keyword is only stored on the leaf node, which ensures the stability of the query effect. Any query must go to the leaf node to obtain data. B-tree stores data in the branch node and returns data if a keyword is matched.
  • The leaf nodes of B+Tree are arranged sequentially, and there is a sequential reference relationship between the two adjacent leaf nodes, which can better support the range query. B-tree does not have this order relationship.

MySQL > select * from B+Tree

After the above analysis, we can now summarize why MySQL chose B+Tree as its index data structure.

  1. First, compared with balanced binary Tree, B+Tree has lower depth, more nodes save keywords, less disk I/O times, and better query calculation efficiency.

  2. The GLOBAL scanning capability of B+Tree is stronger. If you want to perform global scanning for data tables based on index data, the B-tree scans the entire Tree and traverses the table layer by layer. B+Tree, on the other hand, just walks through the leaf nodes, because there is a sequential reference relationship between the leaf nodes.

  3. The DISK I/O capability of B+Tree is higher because only keywords are stored on each branch node of B+Tree. In this way, more keywords can be stored on each node than on the NODE of B+Tree. In this way, the disk I/O load of B+Tree is much more than that of B-Tree.

  4. B+Tree data structure has the natural sorting ability, which is stronger than other data structures. Moreover, sorting is carried out through branch nodes. If branch nodes need to be loaded into memory for sorting, more data can be loaded at one time.

  5. B+Tree is more stable because all queries need to scan the leaf node before returning the data. The result is stable but not optimal. If the root node data of a B-tree is queried directly, the B-tree only needs one disk I/O to directly return the data, and the result is optimal.

After the above analysis, MySQL finally chose B+Tree as the data structure of its index.

What is the difference between InnDB’s data store file and MyISAM’s?

MySQL index data structure: MySQL index data structure: MySQL index MySQL > create MySQL variables like ‘%datadir%’; , you can see the directory where the data is stored. The directory where MySQL stores data on my server is:

/var/lib/mysql/
Copy the code

After entering this directory, you can see the directories of all the databases. Create a new database study_test. And then you go into

/var/lib/mysql/study_test
Copy the code

There is currently only one file in this directory, which is used to record the contents of the character set configured when the database is created.

-rw-r----- 1 mysql mysql     60 1month31 10:28 db.opt
Copy the code

Now create two new tables. Select InnoDB as the engine type for the first table and MyISAM as the engine type for the second table.

Student_innodb:

CREATE TABLE `student_innodb` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL.PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name index'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='InnoDB engine table';
Copy the code

Student_myisam:

CREATE TABLE `student_myisam` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL.PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name index'
) ENGINE=MyISAM DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='myISAM Engine Type Table ';
Copy the code

Will create after the completion of the two tables, we again into the/var/lib/mysql/study_test look at:

-rw-r----- 1 mysql mysql     60 1month31 10:28 db.opt
-rw-r----- 1 mysql mysql   8650 1month31 10:41 student_innodb.frm
-rw-r----- 1 mysql mysql 114688 1month31 10:41 student_innodb.ibd
-rw-r----- 1 mysql mysql   8650 1month31 10:58 student_myisam.frm
-rw-r----- 1 mysql mysql      0 1month31 10:58 student_myisam.MYD
-rw-r----- 1 mysql mysql   1024 1month31 10:58 student_myisam.MYI
Copy the code

By looking at the files in the directory, you can see how many more files were created after the table was created. This also shows the difference between InnoDB engine type tables and MyISAM engine type tables.

Each of these files has its own purpose:

  • InnoDB engine table files, a total of two:
    • Files such as *.frm are table definition files.
    • *.ibd files are data and index storage files. Table data and index are stored together, and the data can be queried directly through the index.
  • MyIASM engine table files, a total of three:
    • Files such as *.frm are table definition files.
    • A file such as *.myd is a table data file in which all data in a table is stored.
    • *.myi files are table index files, MyISAM storage engine index data stored separately.

MyISAM data storage engine, index and data storage structure

The MyISAM storage engine stores the index data separately, and the index B+Tree ends up pointing to the physical address of the data, not the specific data. Then go to the data file (*.myd) based on the physical address to find the specific data.

As shown below:So when there are multiple indexes, they all point to the same physical address. As shown below:From this structure, we can see that MyISAM storage engine index is peer, primary key and non-primary key index structure and query mode is exactly the same.

InnoDB data storage engine, index and data storage structure

First of all, InnoDB indexes are divided into clustered index and non-clustered index. Clustered index stores both key words and data, key words are stored on each branch node of B+Tree, and data is stored on leaf node. Clustering means that rows of data are stored close together in a certain order. A table can only have one clustered index, because there is only one way to store data in a table. Generally, the primary key is used as the clustered index. If there is no primary key, InnoDB will generate a hidden column as the primary key by default.

As shown below:A non-clustered index, also known as a secondary index, stores the key on each branch node of a B+Tree, but the leaf node is not the saved data, but the saved primary key value. When querying data through secondary indexes, the primary key corresponding to the data is first queried, and then the specific data row is queried according to the primary key.

As shown below:As the design of the clustering index structure, as a result, the clustering index at the time of the query to be two index retrieval, the benefits of this design, can ensure that the event of data migration, you just need to update the primary key index, the clustering index is not moved, but also avoid the storage physical address like MyISAM index, The need to re-maintain all indexes during data migration.

conclusion

This time the MySQL index data structure and file storage structure, summarize clearly, behind in the actual work process, design index to consider more fully, by understanding the index data structure, also can let oneself in the actual writing SQL, to consider what index which don’t walk the index.

  • MySQL uses B+Tree as its index data structure. Because B+Tree has a low depth, nodes save a large number of keywords, and disk I/O times are low, which ensures higher query efficiency.
  • The depth of leaf nodes of B+Tree is the same. In order to better support auto-increment of primary keys, the query nodes of B+Tree are closed on the left and open on the right.
  • MySQL MyISAM storage engine stores table data and index data separately in two files. Because the leaf node of the index B+Tree points to the disk address of the table data, and there is no primary key and non-primary key, the index is stored separately, which can better manage the unified index.
  • In MySQL’s InnoDB storage engine, table data and index data are stored in the same file, because InnoDB’s clustered index leaves point to specific data rows, and in order to ensure stable query results, InnoDB tables must have a clustered index. The primary key value of the data is first retrieved through the secondary index, and then the specific data is retrieved from the clustered index based on the primary key.

Please scan the QR code to follow the public account: Jimoer

Articles will be synchronized to the public account above, we grow together, improve technical ability together.