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

This article mainly explains "what is Java multi-way lookup tree", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let Xiaobian take you to learn "What is Java multi-way lookup tree"!

Problem Analysis of Binary Tree

Binary tree operation efficiency is high, but there are also problems, please see the following binary tree

Binary tree needs to be loaded into memory, if the binary tree nodes are few, there is no problem, but if the binary tree nodes are many (such as 100 million), there are the following problems:

HarmonyOS Technology Community

When building a binary tree, I/O operations need to be performed many times (massive data exists in the database or file), and the number of nodes is massive. When building a tree, speed has an impact.

Node mass, will also cause binary tree height is very large, will reduce the speed of operation.

multi-branch tree

HarmonyOS Technology Community

In a binary tree, each node has data items and at most two child nodes. If each node is allowed to have more data items and more nodes, it is a multipath tree.

For example, 2-3 tree, 2-3-4 tree is a multi-fork tree, multi-fork tree by reorganizing nodes, reducing the height of the tree, can optimize the binary tree.

For example, the 2-3 tree below is a multitree.

Basic introduction to B-tree

B-Tree means B-Tree, B means Balanced. In mysql, it is said that a certain type of index is based on a B tree or B+ tree, as shown below:

B-Tree Description:

HarmonyOS Technology Community

B-tree order: the maximum number of child nodes of a node, such as 2-3 tree order 3, 2-3-4 tree order 4.

B-tree search: starting from the root node, binary search is performed on the keyword (ordered) sequence in the node, and if it hits, it ends, otherwise, it enters the child node of the query keyword range; repeat until the corresponding child pointer is empty or has been a leaf node.

Keyword sets are distributed throughout the tree, i.e. leaf nodes and non-leaf nodes store data.

Search may end at non-leaf nodes

Its search performance is equivalent to doing a binary search on the full set of keywords.

B-trees improve efficiency by reorganizing nodes, reducing tree height, and reducing I/O reads and writes.

HarmonyOS Technology Community

The tree in Figure B reduces the height of the tree by reorganizing the nodes.

The designers of file systems and database systems took advantage of the disk read-ahead principle, setting the size of a node equal to one page (page size is usually 4k), so that each node can be fully loaded with only one I/O.

Set the degree M of the tree (the number of child nodes contained in a parent node of the tree) to 1024. Out of 60 billion elements, it takes at most 4 I/O operations to read the desired element. B-trees are widely used in file storage systems and database systems.

B+ tree basic introduction

B+ tree is a variant of B tree and a multi-way search tree.

B+ Tree Description:

HarmonyOS Technology Community

B+ tree search is basically the same as B tree, the difference is that B+ tree can only hit the leaf node (B tree can hit the non-leaf node), and its performance is equivalent to doing a binary search in the keyword set.

All keywords appear in the linked list of leaf nodes (i.e. data can only be in leaf nodes [also called dense index]), and the keywords (data) in the linked list happen to be ordered.

It is impossible to hit on non-leaf nodes.

Non-leaf nodes correspond to the index of leaf nodes (sparse index), and leaf nodes correspond to the data layer that stores (keyword) data.

Better suited for file indexing systems.

B trees and B+ trees have their own scenarios, and it is not possible to say that B+ trees are completely better than B trees, and vice versa.

B* tree basic introduction

A B* tree is a variant of the B+ tree, adding pointers to siblings to non-root and non-leaf nodes of the B+ tree.

B-Tree Description: *

HarmonyOS Technology Community

B* tree defines that the number of non-leaf node keywords is at least (2/3)*M, that is, the minimum usage rate of blocks is 2/3, and the minimum usage rate of blocks in B+ tree is 1/2.

As can be seen from the first feature, B* trees have a lower probability of assigning new nodes than B+ trees and a higher space utilization.

2-3 Basic introduction to trees (simplest B-tree)

2-3 A tree is the simplest B-tree structure with the following characteristics:

HarmonyOS Technology Community

2-3 All leaf nodes of the tree are at the same level. (All B-trees satisfy this condition.)

A node with two children is called a two-node, and a two-node either has no children or two children.

A node with three children is called a three-node, and a three-node either has no children or three children.

2-3 A tree consists of two nodes and three nodes.

2-3 Tree insertion rules:

HarmonyOS Technology Community

2-3 All leaf nodes of the tree are at the same level. (All B-trees satisfy this condition.)

A node with two children is called a two-node, and a two-node either has no children or two children.

A node with three children is called a three-node, and a three-node either has no children or three children.

When inserting a number to a certain node according to the rules, if the above three requirements cannot be met, it needs to be disassembled, first up, if the upper layer is full, then the layer is disassembled, and the above three conditions still need to be met after disassembly.

For three-node subtrees the size of the values still satisfies the rule (BST binary sort tree).

At this point, I believe that we have a deeper understanding of "what is Java multi-way lookup tree," may wish to actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

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.