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

What is the difference between B-tree index and B + tree index in MySQL? the content is detailed, the steps are clear, and the details are handled properly. I hope that this article "what is the difference between B-tree index and B +-tree index in MySQL" can help you solve your doubts.

If the tree is used as the data structure of the index, one node of the tree, that is, one page, is read from the disk every time the data is looked up, while each node of the binary tree stores only one piece of data and cannot fill the storage space of one page. isn't the extra storage space going to be wasted? In order to solve this disadvantage of binary balanced search tree, we should look for a data structure in which a single node can store more data, that is, multi-path search tree.

1. Multipath search tree

1. The height of the complete binary tree: O (log2N), where 2 is the logarithm and the number of nodes in each layer of the tree

2. The height of the complete M-path search tree: O (logmN), where M is the logarithm and the number of nodes in each layer of the tree.

3. M-way search tree is mainly used to solve the data storage in which a large amount of data can not be loaded into memory. By increasing the number of nodes in each layer and storing more data in each node to store more data in the first layer, so as to reduce the height of the tree and reduce the number of disk visits when looking up data.

4. So the more nodes per layer and the more keywords each node contains, the shorter the height of the tree. But the slower it is to determine the data at each node, but the B-tree focuses on disk performance bottlenecks, so the overhead of searching for data on a single node can be ignored.

2. B-tree-multipath balanced search tree

B-tree is a kind of M-path search tree. B-tree is mainly used to solve the imbalance of M-path search tree, which leads to the height of the tree becoming taller, just like the performance problem caused by the degradation of binary tree to linked list. The B-tree ensures the balance of the M-path search tree by controlling and adjusting the nodes of each layer, such as node separation, node merging, splitting the parent node upward when the first layer is full, adding new layers and so on.

M is the order or number of paths of the B-tree. In the B-tree, each node is a disk block (page). Each non-leaf node stores keywords and pointers to the son tree, the specific number is: M-order B-tree, each non-leaf node stores a keyword and M pointers to the subtree. The figure is a schematic diagram of the fifth-order B-tree structure:

3. B-tree index

First create a user table:

Create table user (id int, name varchar, primary key (id)) ROW_FORMAT=COMPACT

If we use the B-tree to index the user records in the table:

Each node of the B-tree occupies a disk block, and the disk block is the page. As can be seen from the above figure, compared with the balanced binary tree, each node stores more primary key key and data data, and each node has more child nodes, the number of child nodes is generally called order, the B-tree in the above figure is a third-order B-tree, the height will also be reduced. If we want to find the user information of id=28, the search process is as follows:

1. Find page 1 according to the root node and read it into memory. [disk Icano operation for the first time]

2. Compare the key value 28 in the interval (170.35) and find the pointer p2 of page 1.

3. Find page 3 according to the p2 pointer and read it into memory. [disk Icano operation second time]

4. Compare the key value 28 in the interval (26j 35) and find the pointer p2 of page 3.

5. Find page 8 according to the p2 pointer and read it into memory. [disk Icano operation for the third time]

6. Find the key value 28 in the list of key values on page 8, and the user information corresponding to the key value is (28pi po).

Compared with AVLTree, B-Tree reduces the number of nodes, which makes the data fetched from memory by disk IBG O play a role every time, thus improving the query efficiency.

4. B+ tree index

B+Tree is an optimization based on B-Tree to make it more suitable for the implementation of external storage index structure, the nature of B+ tree:

1. The number of subtree pointers and keywords of non-leaf nodes is the same.

2. Add a chain pointer to all leaf nodes

3. All keywords appear in the leaf node, and the keywords in the linked list happen to be ordered.

4. The non-leaf node is equivalent to the index of the leaf node, and the leaf node is the data layer that stores (keywords) data.

The InnoDB storage engine uses B+Tree to implement its index structure.

You can see from the B-Tree structure diagram in the previous section that each node contains not only the key value of the data, but also the data value. However, the storage space of each page is limited, if the data data is large, it will lead to a small number of key that each node (that is, a page) can store, and when the amount of data stored is very large, it will also lead to a large depth of B-Tree, which will increase the number of disk B-Tree O when querying, and then affect the query efficiency. In B+Tree, all data recording nodes are stored on the leaf nodes of the same layer according to the order of key values, while only key value information is stored on non-leaf nodes, which can greatly increase the number of key values stored in each node and reduce the height of B+Tree.

B+Tree differs from B-Tree in several ways:

1. Non-leaf nodes only store key value information and pointers to the page number of child nodes.

2. There is a chain pointer between all leaf nodes

3. The data records are stored in the leaf node.

Based on the picture above, let's take a look at the difference between a B + tree and a B tree:

The main results are as follows: (1) the data is not stored on the non-leaf node of the B + tree, only the key value is stored, while not only the key value but also the data is stored in the B tree node.

The size of the page is fixed, and the default size of the page in InnoDB is 16KB. If the data is not stored, more keys will be stored, the corresponding tree will have a larger order, and the tree will be shorter and fatter, so the number of IO we need to find data to disk will be reduced again, and the efficiency of data query will be faster.

In addition, if our B+ tree can store 1000 keys per node, then the 3-tier B+ tree can store 1000 × 1000 × 100 billion data. Generally, the root node is resident in memory (you don't need to read the disk the first time to retrieve the root node), so generally we need to find 1 billion data and only need 2 disk IO.

(2) all the data of the B+ tree index is stored in the leaf node, and the data is arranged in order.

The pages in the B+ tree are connected by a two-way linked list, and the data in the leaf node is connected by an one-way linked list. In this way, all the data in the table can be found. The B + tree makes range lookup, sorted lookup, grouping lookup, and de-relookup extremely easy. And B-tree because the data is scattered in each node, it is not easy to achieve this.

Read here, this article "what is the difference between B-tree index and B + tree index in MySQL" has been introduced. If you want to master the knowledge of this article, you still need to practice and use it to understand it. If you want to know more about related articles, welcome to follow the industry information channel.

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.