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

This article mainly explains the "MySQL index bottom is how to achieve", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in-depth, together to study and learn "MySQL index bottom is how to achieve" it!

What is the index?

Index is a data structure that helps MySQL to obtain data efficiently.

What can an index do?

Improve the efficiency of data query.

Index: a sorted quick search data structure! The index affects the lookup after where and the sorting after order by.

I. Classification of indexes

1 ️indexes are divided in terms of storage structure: BTree index (B-Tree or B+Tree index), Hash index, full-index full-text index, R-Tree index.

2 ️indexes are divided in terms of application level: general index, unique index, composite index

3 ️indexes according to the relationship between the physical order of the data in and the logical (index) order of key values: clustered index, nonclustered index.

1 ️stores describes the form that is saved when the index is stored

2 ️categories are classified in the process of using the index, and the two are divided on different levels. However, the index type usually refers to the division at the application level.

Just like the classification of mobile phones: Android phones, IOS phones and Huawei phones, Apple phones, OPPO phones.

General index: that is, an index contains only a single column, and a table can have multiple single-column indexes

Unique index: the value of the index column must be unique, but null values are allowed

Composite index: that is, an index contains multiple columns

Clustered index (clustered index): it is not a separate type of index, but a way to store data. The details depend on the implementation, and InnoDB's clustered index actually holds the B-Tree index (technically B+Tree) and data rows in the same structure.

Non-clustered index: either clustered index or non-clustered index (serious face).

Second, the underlying implementation of the index

Mysql default storage engine innodb only explicitly supports B-Tree (technically B+Tree) index. for frequently accessed tables, innodb will transparently establish adaptive hash indexes, that is, hash indexes based on B-tree indexes, which can significantly improve search efficiency, which is transparent, uncontrollable and implicit for clients.

Don't talk about the storage engine, just talk about implementation (abstraction)

Hash index

Based on the hash table implementation, only queries that exactly match all columns of the index are valid. For each row of data, the storage engine calculates a hash code (hash code) for all index columns, and the Hash index stores all hash codes in the index, while storing pointers to each data row in the index table.

B-Tree indexing (MySQL uses B+Tree) B-Tree can speed up data access because the storage engine no longer needs a full table scan to get the data, and the data is distributed among the nodes.

B+Tree index

Is an improved version of B-Tree, as well as the storage structure used by database indexes.

The data is on the leaf node, and a sequential access pointer is added, and each leaf node points to the address of the adjacent leaf node.

Compared to B-Tree, scope lookup only needs to find two nodes and traverse it. While B-Tree needs to acquire all nodes, B+Tree is more efficient.

Discussed in conjunction with the storage engine (B+Tree is generally used by default)

Example: suppose you have a student table with id as the primary key

Implementation in the MyISAM engine (secondary index is also implemented in this way)

Implementation in InnoDB

III. Problems

Q: why does the index structure use B-Tree by default instead of hash, binary tree, red-black tree?

Hash: although it can be located quickly, there is no order, and the complexity of IO is high.

Binary tree: the height of the tree is uneven, it cannot be self-balanced, the search efficiency is related to the data (the height of the tree), and the IO cost is high.

Red-black tree: the height of the tree increases with the increase of the amount of data, and the IO cost is high.

Q: why do officials recommend using a self-growing primary key as an index?

Combined with the characteristics of B+Tree, the self-increasing primary key is continuous, and the page split is minimized in the insertion process, even if the page split is carried out, only a small part of it will be split. And can reduce the movement of data, each insert is inserted to the end. In short, it is to reduce the frequency of division and movement.

Insert continuous data:

Insert discontiguous data

Thank you for reading, the above is the content of "how is the bottom layer of MySQL index realized". After the study of this article, I believe you have a deeper understanding of how the bottom layer of MySQL index is realized, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.