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

The following mainly brings you how to use the mysql index data structure. I hope these contents can bring you practical use, which is also the main purpose of this article when I edit the mysql index data structure. All right, don't talk too much nonsense, let's just read the following.

MyISAM uses B-Tree to implement primary, unique, and non-primary key indexes.

Non-primary key indexes in InnoDB use B-Tree data structures, while primary key indexes use B+Tree.

B-Tree

B-tree (multipath search tree, not binary) is a common data structure. The use of B-tree structure can significantly reduce the intermediate process of locating records, thus speeding up access speed. According to the translation, B is usually regarded as the abbreviation of Balance. This data structure is generally used for the index of the database, and the comprehensive efficiency is high.

Performance (recommended: MySQL video tutorial)

B-tree has the following features:

1. Keyword sets are distributed in the whole tree.

2. Any keyword appears and only appears in one node

3. The search may end at non-leaf nodes.

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

5. Automatic hierarchical control

B+Tree

Different storage engines may use different data structures to store, while InnoDB uses B+Tree

So what is B+Tree?

B+Tree is a variant tree of B-Tree to meet the needs of the file system. The difference between an m-order B + tree and an m-order B-tree is:

B+ and B-(that is, B) are because the keywords on each node are different. One more, one less.

For B + tree, its node structure is the same as that of B-tree, but the difference is the keywords of each node and the number of child nodes that can be owned. For example, in the m-order B + tree, each node can have at most m sub-nodes. The non-root node has at least [m _ B-tree 2] sub-nodes, and the number of keywords is one more than that of the non-root node, which is [m _ big 2] ~ m.

The differences between the two data structures that deal with indexes:

one. The same key value does not appear many times in the B tree, and it may appear in the leaf node or in the non-leaf node. The keys of the B + tree must appear in the leaf nodes, and may also be repeated in the non-leaf nodes in order to maintain the balance of the B + tree.

two. Because the location of the B-tree key is uncertain and appears only once in the whole tree structure, although it can save storage space, it obviously increases the complexity of inserting and deleting operations. Compared with B + tree, it is a good compromise.

three. The query efficiency of B-tree is related to the position of keys in the tree. The maximum time complexity of B-tree is the same as that of B + tree (at the leaf node), and the minimum time complexity is 1 (at the root node). The time complexity of the B+ tree is fixed for a built tree.

For the above about the general use of mysql index data structure, we do not think it is very helpful. If you need to know more, please continue to follow our industry information. I'm sure you'll like it.

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.