• notice
  • Congratulations on the launch of the Sought Tech site

What is the difference between InnoDB's data storage file and MyISAM's?

Preface

The topic of this article is a real problem I encountered during the interview.An Internet crowdfunding company was investigating the interviewer’s first question about MySQL-related knowledge.I was still quite confused at the time.I didn’t expect this young man to not talk about it.Wu De, you don't follow the rules.When you ask about MySQL related knowledge, don't you always ask about index optimization and index failure? Why did it come out, the storage file is different? Even looking at an MVCC mechanism is fine. So this time I will summarize this part of knowledge.

Why do you need to build an index

First of all, we all know that the purpose of indexing is to improve query speed, so why can index improve query speed?
Let's take a look at a schematic diagram of an index.

If I have a SQL statement: select * from Table where id = 15Then in the absence of an index, a full table scan is actually performed, which is to search one by one until the record with id=15 is found, and the time complexity is O(n);

If there is an index, the query will be performed. First, according to id=15, binary search is performed in the index value.The efficiency of binary search is very high, and its time complexity is O(logn);

This is why the index can improve the query efficiency, but the amount of index data is relatively large, so it is generally not stored in the memory, but directly stored in the disk, so the file content in the disk is read.It is inevitable to perform disk IO.

Why MySQL index uses B+Tree

As we said above, index data is generally stored in disk, but calculation data must be carried out in memory.If the index file is very large, it cannot be loaded into memory all at once, so the index is used for data search At the time, multiple disk IO will be performed, and the index data will be loaded into the memory in batches.Therefore, a good index data structure must have the least number of disk IOs under the premise of getting the correct results.

Hash type

At present, MySQL actually has two types of index data to choose from, one is BTree (actually B+Tree) and the other is Hash.

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

Because if you use a Hash type index, MySQL will perform a Hash operation on the index data when creating the index, so that the disk pointer can be quickly located based on the Hash value.Even if the amount of data is large, it can quickly and accurately locate To the data.

  • But like select * from Table where id > 15this kind of range query, Hash type index can't handle.For this kind of range query, the whole table will be scanned directly.In addition, Hash type index can't handle sorting.

  • In addition, although MySQL has done a series of processing at the bottom, it still cannot guarantee that Hash collision will not occur.

Binary tree

Then why does MySQL not have a binary tree as its index data structure? We all know that binary trees use binary search to locate data, so the effect is good.The time complexity is O(logn);
Binary tree
but the binary tree has a problem, that is, under special circumstances, it will degenerate into a stick.It is a singly linked list. At this time, its time complexity will degenerate to O(n);
Binary tree degenerates into linked list
so when we want to query the record with id=50, it is actually the same as a full table scan. So because of this situation, the binary tree is not suitable as an index data structure.

Balanced binary tree

So since the binary tree will degenerate into a linked list under special circumstances, why can't a balanced binary tree be allowed?

The height difference of the child nodes of the balanced binary tree cannot exceed 1 , like the binary tree in the figure below, the node with the key of 15, its left child node height is 0, the right child node height is 1, and the height difference does not exceed 1, so the following A tree is a balanced binary tree.
Balanced binary tree
Because it can maintain balance, its query time complexity is O(logN).As for how to maintain balance, it is mainly to do some left-handed, right-handed, etc.The specific details of maintaining balance are not the main content of this article.If you want to know, you can search by yourself.

What are the problems with using this data structure for MySQL indexing?

  • Excessive disk IO : In MySQL, only one node is read in one IO operation.If a node has at most two child nodes, then there is only the query range of these two child nodes, so if you want to be accurate to the specific data, just Need to perform multiple reads, if the tree is very deep, then a lot of disk IO will be performed. The performance has naturally declined.

  • Low space utilization : For a balanced binary tree, each node value stores a key, a data area, and pointers to two child nodes. This has led to the fact that only such a bit of data is loaded in one hard IO operation, which is really a bit of a sledgehammer.

  • The query effect is unstable : if in a deep balanced binary tree, if the queried data happens to be the root node, then it will be quickly found, if the queried data happens to be a leaf node, then multiple disk IO will be performed The response time may not be the same order of magnitude as that of the root node.

Although the binary tree solves the problem of balance, it also brings new problems, that is, due to the depth of its own tree, it will cause a series of efficiency problems.

So in order to solve this kind of problem of balanced binary tree, balanced multi-tree (Balance Tree) has become a better choice.

Balance Tree--B-Tree

B-Tree means a balanced multi-branch tree.Generally, how many child nodes a node in a B-Tree has, we call it a B-Tree of how many levels. Usually m is used to represent the order.When m is 2, it is a balanced binary tree.

Each node of a B-Tree can have at most m-1 keywords, at least Math.ceil(m/2)-1one keyword must be stored , and all leaf nodes are on the same layer. The following figure shows a 4-level B-Tree.
Insert picture description here
Then let's take a look at how B-Tree finds data :

  • If it is to query the data with id=7, first load the node of keyword 20 into the memory, and judge that 7 is smaller than 20;

  • Then load the first child node, if the queried data is equal to 12 or 17, then return directly, if not, continue to look down, and find that 7 is less than 12;

  • Then continue to load the first child node, and after finding 7, directly return the data under 7.

In this way, the entire operation actually performed 3 IO operations, but in fact, the general B-Tree has many branches at each layer (usually greater than 100).

In order to make better use of disk IO capabilities, MySQL sets the size of the operation page to 16K, that is, the size of each node is 16K. If the keyword in each node is of type int, then it is 4 bytes.If the size of the data area is 8 bytes and the node pointer occupies 4 bytes, then each node of the B-Tree The number of keywords that can be stored is:, (16*1000) / (4+8+4)=1000each node can store up to 1000 keywords, and each node can have up to 1001 branch nodes.

In this way, when querying index data, one disk IO operation can read 1000 keywords into the memory for calculation.One disk IO operation of B-Tree, N disk IO operations for balancing binary data on top.

要注意的是In order to ensure the balance of data, B-Tree will do a series of operations.This process of maintaining balance is time-consuming, so when creating an index, you must select the appropriate field, and do not create too many indexes.If there are too many, when updating data, the process of updating the index is also more time-consuming.

Also, do not select low-discrimination field values as indexes.For example, gender fields have two values in total, which may cause the depth of the B-Tree to be too large and reduce the indexing efficiency.

B+Tree

B-Tree has solved the problem of balanced binary tree very well, and can also guarantee the query efficiency, so why is there a B+Tree?

Let's first come to what B+Tree looks like.

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

First of all, the number of child nodes of each node and the ratio of keywords that can be stored in each node is the 1:1second is that when querying data, the left closed interval is used for query, and there is no data in the branch node, only keywords and child nodes are saved Pointing, data are stored in leaf nodes.
Insert picture description here
So let's take a look at how to query data in B+Tree.

E.g:

  • Now to query the data with id=2, then the root node will be taken out first, loaded into the memory, and found to id=2exist in the root node, because the data is stored in the left closed interval, so id<=2all are on the first child node of the root node;

  • Then take out the first child node, load it into the memory, find id=2the keywords that exist in the current node , and have reached the leaf node, then directly take out the data in the leaf node and return it.

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

  • The B+Tree query uses the left closed interval, which can better support the query effect of the auto-increment index, so it is usually auto-increment when creating the primary key. This is different from B-Tree.

  • No data is stored on the root node and branch nodes in B+Tree.Keyword-related data is only stored on the leaf nodes.This ensures the stability of the query effect.Any query must go to the leaf node to get the data. The B-Tree saves data in the branch node, and returns the data directly if the keyword is hit.

  • The leaf nodes of B+Tree are arranged in order, and two adjacent leaf nodes have a sequential reference relationship, which can better support range queries. And B-Tree does not have this order relationship.

Why did MySQL index choose B+Tree

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

  1. First of all, compared with the balanced binary tree, B+Tree has a lower depth, more nodes store keywords, fewer disk IO times, and better query calculation efficiency.

  2. B+Tree has stronger global scanning capabilities.If you want to perform a global scan on the data table based on index data, B-Tree will scan the entire tree and then traverse layer by layer. For B+Tree, you only need to traverse the leaf nodes, because there is a sequential reference relationship between leaf nodes.

  3. B+Tree's disk IO read and write ability is stronger, because each branch node of B+Tree only saves keywords, so every time the disk IO is read and written, a page of 16K data can store more keys There are more keywords stored on each node than B-Tree. In this way, a disk IO load data of B+Tree is much more than that of B-Tree.

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

  5. The query effect of B+Tree is more stable, because all queries need to scan to leaf nodes before returning data. The effect is only stable and not necessarily optimal.If you directly query the root node data of the B-Tree, then the B-Tree only needs one disk IO to directly return the data, but the effect is optimal.

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

What is the difference between InnDB's data storage file and MyISAM's?

The above summarizes the data structure of the MySQL index.This time we can say the second problem, because this problem is actually related to the MySQL index.
Let's take a look.First, find the directory where MySQL stores data on the server:
log in to MySQL and open the MySQL command line interface: enter it 
show variables like '%datadir%';, and you can see the directory where data is stored.
The MySQL data storage directory in my server is in:

/var/lib/mysql/

After entering this directory, you can see the directories of all databases and create a study_testnew database.
Then enter

/var/lib/mysql/study_test

In this directory, there is currently only one file, and this file is used to record the content of the character set configured when the database is created.

-rw-r----- 1 mysql mysql     60 1月  31 10:28 db.opt

Now create two tables, the engine type of the first table is InnoDB, and the engine type of the second table is MyISAM.

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索引') ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='innodb引擎表';

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索引') ENGINE=MyISAM DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='myISAM引擎类型表';

After the two tables are created, we will enter to /var/lib/mysql/study_testtake a look:

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

Through the files in the directory, you can see that there are a few more files after the table is created.This also shows the file difference between the InnoDB engine type table and the MyISAM engine type table.

Each of these files has its own role:

  • There are two table files for the InnoDB engine:

    • *.frm This type of file is the definition file of the table.

    • *.ibd These files are data and index storage files. Table data and indexes are stored in clusters, and data can be directly queried through indexes.

  • There are three table files of MyIASM engine:

    • *.frm This type of file is the definition file of the table.

    • *.MYD This type of file is a table data file, and all the data in the table are saved in this file.

    • *.MYI This type of file is the index file of the table, and the index data of the MyISAM storage engine is stored separately.

MyISAM data storage engine, index and data storage structure

When the MyISAM storage engine stores the index, it stores the index data separately, and the B+Tree of the index ultimately points to the physical address where the data exists, rather than the specific data. Then go to the data file (*.MYD) to find the specific data according to the physical address.

As shown below:

MyISAM index storage structure
Then when there are multiple indexes, the multiple indexes all point to the same physical address.
As shown in the figure below:
Multiple indexes of MyISAM
Through this structure, we can see that the indexes of the MyISAM storage engine are all at the same level, and the primary key and non-primary key index structures and query methods are exactly the same.

InnoDB data storage engine, index and data storage structure

First of all, InnoDB indexes are divided into clustered indexes and non-clustered indexes.The clustered index stores keywords and data.The keywords are stored on each branch node of the B+Tree, and the data is stored on the leaf nodes.
Clustering " means that data rows are stored closely arranged one by one 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 a clustered index.If there is no primary key, InnoDB will generate a hidden column as the primary key by default.

As shown in the following figure:
InnoDB clustered index
non-clustered index, also known as secondary index, although the key is stored on each branch node of B+Tree, the leaf node is not the stored data, but the stored primary key value. To query the data through the secondary index, the primary key corresponding to the data will be queried first, and then the specific data row will be queried based on the primary key.

As shown in the figure below:
InnoDB non-clustered index
Due to the design structure of the non-clustered index, the non-clustered index needs to be indexed twice during the query.The advantage of this design can ensure that once the data migration occurs, only the update is required.The primary key index is sufficient, and the non-clustered index does not need to be moved, and it also avoids the problem of storing physical addresses like MyISAM indexes and re-maintaining all indexes during data migration.

Summarize

This time I summarized the MySQL index data structure and file storage structure clearly.Later in the actual work process, you can consider more fully when designing the index.By understanding the data structure of the index, you can also let yourself When actually writing SQL, you can consider which situations to use the index and which do not use the index.

  • MySQL uses B+Tree as the data structure of the index, because the depth of B+Tree is low, the nodes store more keywords, and the number of disk IOs is less, thus ensuring higher query efficiency.

  • B+Tree can ensure that the query effect of MySQL is stable whether it is a primary key index or a non-primary key index.The leaf node must be queried each time to return data.The depth of the leaf node of B+Tree is the same, and for better Supports self-incrementing primary keys, and the query node range of B+Tree is closed on the left and open on the right.

  • MySQL's MyISAM storage engine, table data and index data are stored in two files separately, because the disk address of the table data pointed to by the leaf node of the B+Tree of its own index, and the index has no primary key and non The primary key is divided, so it is stored separately, which can better manage the index;

  • MySQL's InnoDB storage engine, table data and index data are stored in one file, because the leaf nodes of InnoDB's clustered index point to specific data rows, and in order to ensure the stability of the query effect, there must be one in the InnoDB table Clustered index, when the secondary index performs index retrieval, the primary key value of the data will be retrieved through the secondary index first, and then specific data will be retrieved from the clustered index according to the primary key.


Tags

Technical otaku

Sought technology together

Related Topic

0 Comments

Leave a Reply

+