What is the principle of btree index

The btree index principle is that the binary tree results in a very high tree height. The nodes that are very close logically are very far away physically and cannot take advantage of locality. The number of IOs is high and the search efficiency is low; Btree is a balanced "m -way" search tree, which can use multiple branch nodes to reduce the number of nodes experienced when querying data.

BTree index principle

Binary tree results in very high tree height and logically close nodes. Physically very far away, locality cannot be exploited, IO times are high, and search efficiency is low

Btree is a balanced m-way search tree, which can use multiple branch nodes (subtree nodes) to reduce queries The number of nodes that data has experienced, thereby saving access time. m is called the degree of B-Tree.

The B tree can be seen as an extension of the 2-3 search tree, that is, it allows each node to have M-1 child nodes.

Features

• There is a root node, the root node has only one record and two children or the root node is empty;

• The key and pointer in each node record are spaced apart from each other, and the pointer points to the child node;

• d represents the width of the tree. Except for leaf nodes, other Each node has [d/2,d-1] records, and the keys in these records are arranged by size from left to right, and there are [d/2 1,d] children;

• In a node, all keys in the n-th subtree are less than the n-th key in this node and greater than the n-1th key;

• All leaf nodes must be at the same level, that is, they have the same depth;

• Due to the characteristics of B-Tree, the algorithm for retrieving data by key in B-Tree is very intuitive: First, a binary search is performed from the root node. If found, the data of the corresponding node is returned. Otherwise, the node pointed to by the pointer of the corresponding interval is searched recursively until the node is found or the null pointer is found. The former search is successful, and the latter search fails.

Recommended: "mysql tutorial"

The above is the detailed content of What is the principle of btree index. For more information, please follow other related articles on the PHP Chinese website!