What is the concept of mysql B+Tree index

Concept

1. B Tree is an optimization based on B-Tree, making it more suitable for implementing external storage index structures.In B Tree, all data record nodes are stored on leaf nodes of the same layer in order of key value. Only key value information is stored on non-leaf nodes. This can greatly increase the number of keys stored in each node. The number of values reduces the height of B Tree.

Differences from B-Tree

The search of B is basically the same as that of B-tree. The difference is that B-tree only hits the leaf node when it reaches the leaf node (B-tree can Hits on non-leaf nodes)

(1) All keywords appear in the linked list of leaf nodes (dense index), and the keywords in the linked list happen to be ordered; (only the root node is stored Keywords have values only at the end of the tree)

(2) Non-leaf nodes are equivalent to the index of leaf nodes (sparse index), and leaf nodes are equivalent to the data layer that stores (keyword) data. (Non-root nodes actually store the index pointing to the root node)

(3) Because of the first two points, it is impossible to store data in non-leaf nodes. (The third difference between B-)

(4) The root node also has a chain pointer horizontally (it’s convenient to follow the clues quickly. Without this pointer, even if the next value is an adjacent neighbor, you still have to run Circle to get it)

Instructions for use

2. B Tree index is the default index type of most MySQL storage engines.

Because there is no longer a need to perform a full table scan, only the tree needs to be searched, so the search speed is much faster.

Because of the orderliness of B Tree, in addition to being used for search, it can also be used for sorting and grouping.

You can specify multiple columns as index columns, and multiple index columns together form the key.

Applicable to full key value, key value range and key prefix search, where key prefix search is only applicable to leftmost prefix search. The index cannot be used if the search is not in the order of the indexed columns.

The above is the detailed content of What is the concept of mysql B+Tree index. For more information, please follow other related articles on the PHP Chinese website!