Shulou(Shulou.com)06/02 Report--

Today, I will talk to you about the underlying principle of B-tree index in MySQL, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

B-tree

B-tree, where B stands for balance (balance), B-tree is a kind of multi-path self-balanced search tree. It is similar to an ordinary balanced binary tree, except that the B-tree allows each node to have more children. The figure below is a simplified diagram of the B-tree.

Figure-B-tree diagram

B-tree has the following characteristics:

All the keys are distributed in the whole tree.

Any keyword appears and only appears in one node

The search may end at non-leaf nodes.

Do a search in the full set of keywords, and the performance is close to binary search.

In the search of B-tree, starting from the root node, a binary search is performed for the keyword (ordered) sequence in the node, and if it is hit, it ends, otherwise it enters the son node that the query keyword belongs to; repeat until the corresponding son pointer is empty, or it is already a leaf node; the pseudo code of the search algorithm on B-Tree is as follows:

BTree_Search (node, key) {if (node = = null) return null; foreach (node.key) {if (node.key [I] = = key) return node.data [I]; if (node.key [I] > key) return BTree_Search (point [I]-> node);} return BTree_Search (point [I + 1]-> node);} data = BTree_Search (root, my_key)

In addition, because inserting and deleting new data records will destroy the nature of B-Tree, it is necessary to split, merge, transfer and other operations on the tree in order to maintain the B-Tree property.

B + tree

B + tree is a variant of B-tree and a kind of multipath search tree. It differs from B-tree in:

All keywords are stored in the leaf node, and the internal node, that is, the non-leaf node, does not store the real data,B+ search, which is basically the same as the B-tree, except that the B + tree is hit only when it reaches the leaf node (the B-tree can be hit on the non-leaf node), and its performance is also equivalent to doing a binary search in the full set of keywords.

Features of B+:

All keywords appear in the linked list of leaf nodes (dense index), and the keywords in the linked list happen to be ordered

It is impossible to hit at a non-leaf node.

A non-leaf node is equivalent to an index (sparse index) of a leaf node, and a leaf node is a data layer that stores (keywords) data.

More suitable for file indexing system

The simplified B+ tree is shown below:

Figure-schematic diagram of B + tree

As shown above, it is a b + tree. For the definition of the b + tree, see the B + tree. Here we only talk about some key points. The light blue block is called a disk block. We can see that each disk block contains several data items (shown in dark blue) and pointers (shown in yellow). For example, disk block 1 contains data items 17 and 35, including pointers P1, P2, P3, P1 for blocks less than 17, and P2 for blocks between 17 and 35. P3 represents a block greater than 35. The real data exists in leaf nodes 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99. Non-leaf nodes only do not store real data, but only store data items that guide the search direction, such as 17 and 35 do not really exist in the data table.

The search process of b + tree

As shown in the figure above, if you want to find data item 29, then disk block 1 will first be loaded into memory from the disk. At this time, an IO occurs, and the binary search in memory determines that 29 is between 17 and 35. The P2 pointer of disk block 1 is locked, and the memory time is negligible because it is very short (compared to the disk's IO). Disk block 3 is loaded into memory from disk through the disk address of the P2 pointer of disk block 1. The second time IO,29 is between 26 and 30, lock the P2 pointer of disk block 3, load disk block 8 into memory through the pointer, and the third IO occurs. At the same time, do a binary search in memory to find 29, end the query, a total of three times IO. The truth is, the 3-tier b + tree can represent millions of data. If millions of data lookups only need three IO, the performance improvement will be huge. If there is no index, each data item will have to have one IO, then a total of millions of IO will be required, obviously the cost is very high.

The B+Tree structures commonly used in database systems or file systems are optimized on the basis of classical B+Tree, adding sequential access pointers.

Why use B-Tree (B+Tree)

Generally speaking, the index itself is too large to be stored in memory, so the index is often stored on disk in the form of an index file. In this way, the disk Imax O consumption will be generated in the index search process, which is several orders of magnitude higher than the memory access. Therefore, the most important index to evaluate the quality of a data structure as an index is the progressive complexity of the number of disk Imax O operations in the search process. In other words, the structure of the index should minimize the number of access to disk Imando O during the lookup process.

The locality principle is used to improve the efficiency of Ihammer O. Because of the gap between the access speed of the disk and the memory, in order to improve the efficiency, it is necessary to reduce the disk I / O as much as possible. The disk is often not strictly read on demand, but will be pre-read every time. After reading the required data, the disk will sequentially read back a certain length of data into memory. The theoretical basis for this is the famous locality principle in computer science: when a data is used, the data near it is usually used immediately; the data needed during the running of the program is usually concentrated. Because of the high efficiency of disk sequential reading (no seek time, only a little rotation time), pre-reading can improve the efficiency of Ibind O for programs with locality. The designers of the database system skillfully make use of the principle of disk pre-reading, setting the size of a node to equal to a page, so that each node can be fully loaded only once, so the retrieval efficiency of B-Tree will be relatively high; because the logically close nodes (father and son) may be physically far away, unable to take advantage of locality, the efficiency of the red-black tree will be less.

The query efficiency of B+ tree is more stable. Because the non-endpoint is not the node that ultimately points to the content of the file, but only the index of the keyword in the leaf node. Therefore, any keyword search must take a road from the root node to the leaf node. The path length of all keyword queries is the same, resulting in the same query efficiency for each data. Because the B-tree and the red-black tree may hit the query at any node, the query efficiency may be uneven.

The improved B + tree has sequential access pointers, which is helpful to improve the performance of interval query. Add a pointer to the adjacent leaf node in each leaf node of the B+Tree to form a B+Tree with sequential access pointers. The purpose of this optimization is to improve the performance of interval access. For example, in the following figure, if you want to query all data records whose key is from 18 to 49, when 18 is found, you can access all data nodes at once simply by traversing the node and pointer order, which greatly mentions the efficiency of interval query.

Figure-Sequential access pointer Diagram of B + Tree

MyISAM index underlying storage

The MyISAM engine uses B+Tree as the index structure, and the data field of the leaf node stores the address of the data record. The following is a schematic diagram of the MyISAM index:

Figure-MyISAM Index schematic Diagram

Here, the table has a total of three columns. Assuming that we have Col1 as the primary key, figure 8 shows the Primary key of a MyISAM table. You can see that MyISAM's index file only holds the address of the data record. In MyISAM, there is no structural difference between the primary index and the secondary index (Secondary key), except that the primary index requires that the key is unique, while the key of the secondary index can be repeated. If we build a secondary index on Col2, the structure of the index is shown in the following figure:

Figure-MyISAM Index schematic Diagram

It is also a B+Tree, the address where data records are stored in the data field. Therefore, the index retrieval algorithm in MyISAM is to first search the index according to the B+Tree search algorithm, take out the value of its data field if the specified Key exists, and then read the corresponding data record with the value of the data field as the address. The indexing method of MyISAM is also called "nonclustered", which is called to distinguish it from InnoDB's clustered index.

InnoDB index underlying storage

Although InnoDB also uses B+Tree as the index structure, the implementation is quite different from that of MyISAM.

The first major difference is that InnoDB's data file itself is an index file. As you know above, the MyISAM index file and the data file are separate (the index file holds only the address of the data record). In InnoDB, the table data file itself is an index structure organized by B+Tree, and the leaf node data field of this tree holds the complete data record. The key of this index is the primary key of the data table, so the InnoDB table data file itself is the primary index.

Figure-InnoDB Index schematic Diagram

The figure above is a schematic diagram of the InnoDB main index (which is also a data file), and you can see that the leaf node contains the complete data record. This kind of index is called clustered index. Because the data files of InnoDB are aggregated by the primary key, InnoDB requires that the table must have a primary key (MyISAM can not be explicitly specified). If it is not explicitly specified, the MySQL system will automatically select a column that can uniquely identify the data record as the primary key. If such a column does not exist, MySQL automatically generates an implied field for the InnoDB table as the primary key, which is 6 bytes in length and the type is long shaping.

The second difference from the MyISAM index is that the InnoDB secondary index data field stores the value of the corresponding record primary key instead of the address. In other words, all secondary indexes of InnoDB refer to the primary key as the data field. For example, the following figure shows a secondary index defined on Col3:

Figure-InnoDB Index schematic Diagram

Here, the ASCII code of English characters is used as the comparison criterion. The implementation of clustered index makes the search by primary key very efficient, but the secondary index search needs to retrieve the index twice: first retrieve the secondary index to obtain the primary key, and then use the primary key to retrieve the record in the primary index.

Understanding the index implementation of different storage engines is very helpful for the correct use and optimization of indexes. For example, after knowing the index implementation of InnoDB, it is easy to understand why it is not recommended to use overly long fields as primary keys, because all secondary indexes reference the primary index, and an overlong primary index will make the secondary index too large. For example, using non-monotonous fields as primary keys in InnoDB is not a good idea, because the InnoDB data file itself is a B+Tree, and non-monotonous primary keys will cause frequent splits and adjustments of data files in order to maintain the characteristics of B+Tree when inserting new records, which is very inefficient, while using self-increasing fields as primary keys is a good choice.

After reading the above, do you have any further understanding of the underlying principle of B-tree index in MySQL? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.