Shulou(Shulou.com)05/31 Report--

This article is about what is the multipath search tree B tree and B + tree, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article. Let's take a look at it with the editor.

Multipath search tree

Complete binary tree height: O (log2N), where 2 is logarithm

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

The M-way search tree is mainly used to solve the data storage in which the 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.

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.

B 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. The specific rules are as follows:

The number of son trees of root nodes is between 2 and M, and the number of son trees of other non-leaf nodes is between M and M. If the number of son trees exceeds M because the split exceeds M, the parent node needs to be split up recursively at this time, and when a parent node that no longer needs to be split is found, the splitting is stopped. The splitting process goes up to the root node, and if you need to split the root node, there will be two roots, so you need to create a new root to use the two roots as son nodes, and the height of the tree will increase by 1.

The value of the keyword for each non-leaf node increases from left to right, and the I keyword represents the smallest keyword in subtree itree 1; (where I is between 1 and (2 to M) for the root node, and 1 to (Mhand 2 to M) for other non-leaf nodes)

All the data items of the B-tree are stored in the leaf node, the non-leaf node does not store the data, and the non-leaf node only stores the keywords used to indicate the search direction, namely the index. This helps to load more non-leaf nodes into memory and facilitate data lookup.

All leaf nodes are at the same depth and each leaf node contains Lhand 2 to L item data.

Size selection of M and L

M is the order of the B tree or the number of paths.

L is the maximum number of data items stored per leaf node.

In the B-tree, each node is a disk block, so M and L need to be determined according to the size of the disk block.

Calculation of disk Block size and M

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 son tree, so the size of each keyword is 8 bytes (for example, the long type of Java is 8 bytes), and each pointer is 4 bytes. Then each non-one leaf node of the M-order B-tree needs: 8 * (Mmur1) + 4 * M = 12m-8 bytes.

If it is specified that each non-leaf node (disk block) occupies no more than 8K of memory, that is, 8192, then the maximum M is 683, that is, 683-8192.

Number of leaf node data items L

If each data item size is also 256bytes, then because the disk block size is 8K, that is, 8192 bytes, and each leaf node can store 2 to L data items, so each leaf node can store up to 32 data items, that is, the size of L is 32.

The structure of a fifth-order B-tree is as follows, that is, M and L are equal to 5: each non-leaf node contains a maximum of four keywords, M, that is, five pointers to the subtree. L equals 5, then each leaf node stores up to 5 data items.

B + tree

The structure of the B + tree is basically the same as that of the B tree, the only difference is that the leaf nodes of the B + tree are connected by pointers to form a linked list, so it is easy to traverse all the leaf nodes, that is, to get all or search all the data items in a certain range of keywords. MySQL's InnoDB storage engine uses the B+ tree as the index implementation.

The above is what is the multipath search tree B tree and B + tree, the editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please 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.