What data structure does mysql index generally use?

MyISAM is the default storage engine for versions before MySQL 5.5. After 5.5, InnoDB begins to become the default storage engine for MySQL.

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

The non-primary key index in InnoDB uses the B-Tree data structure, while the primary key index uses the B-Tree.

B-Tree

B-tree (multi-way search tree, not binary) is a common data structure. Using the B-tree structure can significantly reduce the intermediate process experienced when locating records, thereby speeding up access. According to translation, B is usually considered to be the abbreviation of Balance. This data structure is generally used for database indexing and has high overall efficiency.

Performance(Recommended learning: MySQL video tutorial)

B-tree has the following characteristics:

1. Keywords The collection is distributed throughout the tree;

2. Any keyword appears and only appears in one node;

3. The search may end at a non-leaf node;

4. Its search performance is equivalent to a binary search in the complete set of keywords;

5. Automatic hierarchical control;

B Tree

Different storage engines may use different data structures for storage. InnoDB uses B Tree;

So what is B Tree?
B Tree is a variant of B-Tree required by 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 B-tree. The difference is the keyword of each node and the number of child nodes it can have. For example, in an m-order B-tree, each node can have at most m child nodes. Non-root nodes have at least [m/2] child nodes, and the number of keywords is one more than B-tree, which is [m/2]~m.

The differences between these two data structures for processing indexes:

1. The same key value will not appear multiple times in the B-tree, and it may appear in leaf nodes or non-leaf nodes. The keys of the B-tree will definitely appear in leaf nodes, and may also appear repeatedly in non-leaf nodes to maintain the balance of the B-tree.

2. Because the B-tree key position is uncertain and only appears once in the entire tree structure, although it can save storage space, it significantly increases the complexity of insertion and deletion operations. B-trees are a better compromise in comparison.

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

For more MySQL related technical articles, please visit the MySQL database graphic tutorial column to learn!

The above is the detailed content of What data structure does mysql index generally use?. For more information, please follow other related articles on the PHP Chinese website!