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

Today, I would like to talk to you about how to understand B+Tree. Many people may not know much about it. In order to make you understand better, the editor has summarized the following contents for you. I hope you can get something from this article.

Definition of B+Tree

B+Tree is a variant of B-tree and has higher query performance than B-tree. Let's take a look at the m-order B+Tree features:

A node with m subtrees contains m elements (mmur1 in B-Tree)

No data is stored in the root node and branch node, only for indexing, and all data is stored in the leaf node.

All branch nodes and root nodes exist in the child node at the same time, which is the largest or smallest element among the child node elements.

The leaf node contains all the keywords, as well as pointers to the data record, and the leaf node itself is linked sequentially according to the size of the keywords.

A more intuitive picture

1. The red dot refers to the pointer to the satellite data, which points to the disk page where the actual data is stored. The satellite data is a data record in the database.

2. There is also a next pointer to the next leaf node in the leaf node, so the leaf node forms an ordered linked list to facilitate traversing the B+ tree.

Advantages of B+ tree 1. More efficient single-element search

The process of finding element 3 of the B+ tree:

First disk IO

Second disk IO

Third disk IO

From the point of view of this process, it seems to be no different from the query process of B-tree. But there are actually two differences:

First of all, the intermediate nodes of the B+ tree do not store satellite data, so disk pages of the same size can hold more node elements, so that under the same amount of data, the B+ tree is relatively fatter and has fewer disk IO times.

B, because only the leaf node saves the satellite data, the B + tree has to go to the leaf node every time; while the B tree is different every time, the best case is the root node, and the worst case is the leaf node, which is not as stable as the B + tree.

2. Leaf nodes form a chain list, and the performance of range search is better.

The process of finding 3-8 in the B-tree range

A, look for 3 first

B, then find 4, 5, 6, 7, 8, omit the intermediate process, and go directly to 8.

The larger the scope of the lookup, the more times the disk IO is, and the worse the performance is.

The process of finding 3-11 in the B+ tree range

First find the lower bound element 3 from top to bottom, and then iterate through the linked list pointer to get the element 5, 6, 8, and 9, 11; in this way, you don't have to look up elements like the B-tree.

Summary

A single node can store more elements, resulting in fewer disk IO queries.

All queries should find the leaf node, and the query performance is stable.

All leaf nodes form an ordered linked list to facilitate range query.

PS: in the clustered index (Clustered Index) of the database, the leaf node directly contains satellite data. In nonclustered indexes (NonClustered Index), leaf nodes have pointers to satellite data.

After reading the above, do you have any further understanding of how to understand B+Tree? 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.