MySQL

The index

introduce

An index is a data structure used by a storage engine to quickly find records. Indexes are critical for good performance. An index acts as a directory.

The data structure

B-tree indexes

All values of the B tree are stored in order, and each leaf node has the same distance to the root. Search down from the root node to the lower leaf node.

B tree and B plus tree

B tree nodes store both keys and data, while B+ trees only store keys and data in leaf nodes, and other inner nodes only store keys.

The leaf nodes of B tree are independent; A leaf node of a B+ tree has a chain of references to neighboring leaf nodes.

The retrieval process of B-tree is equivalent to binary search for the keywords of each node in the range, and the retrieval may end before the leaf node is reached. However, the retrieval efficiency of B+ tree is very stable. Any search is a process from root node to leaf node, and the sequential retrieval of leaf nodes is obvious.

The hash index

Hash indexes are implemented based on hash tables. Only queries that accurately match all columns are valid, and the time complexity can reach O(1). In MySQL, only Memory supports hash indexes

Classification of indexes

The primary key index

The primary key column of the data table uses the primary key index.

The prefix index

Sometimes indexing long strings can be inefficient. You can use the index part of the string, which can greatly save the index time. Choose prefixes long enough for high selectivity, but not too long to save space. To determine the appropriate prefix length, you need to find a list of the most common values and match it to the list of the most common prefixes.

Clustering index

Clustered index is not a separate index type, but a way of storing data. Its data is actually stored in leaf pages, and a table can only have one clustered index.

Cover index

If an index contains the values of all the fields to be queried, it is called a covered index. Overwriting an index can greatly improve performance, eliminating the need for back operations to the table.

conclusion

It is important to understand how indexes work, and having the right indexes can greatly improve efficiency.