Shulou(Shulou.com)05/31 Report--

This article mainly explains the "detailed introduction of MySQL database index", the content of the article 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 "detailed introduction of MySQL database index"!

01, preface

Read a lot of blogs about the index, the story is more or less the same. But it never made me understand some concepts about indexes, such as B-Tree index, Hash index, unique index.

Maybe there are a lot of people like me who began to study the structures such as BmurTreeMagneBathTree without understanding the concept, which led to the wrong answer during the interview!

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.

02. Classification of index

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

From the storage structure to divide: BTree index (B-Tree or B+Tree index), Hash index, full-index full-text index, R-Tree index.

Divided from the application level: general index, unique index, composite index

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

The * point describes the form in which the index is stored, and the second point is the classification during the use of the index, which is divided at 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).

03. 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 the hash codes in the index, while storing pointers to each data row in the index table.

B-Tree index (MySQL uses B+Tree)

B-Tree can speed up data access, because the storage engine no longer needs to perform full table scans to obtain data, and the data is distributed among 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.

Discuss the case with the storage engine (B+Tree is generally used by default): suppose there is a student table with id as the primary key

Implementation of idnamebirthday001Tom1996-01-01002Jann1996-01-04003Ray1996-01-08004Michael1996-01-10005Jack1996-01-13006Steven1996-01-23007Lily1996-01-25 in MyISAM engine (secondary index is also implemented in the same way)

Implementation in InnoDB

04. Question

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 into the *. In short, it is to reduce the frequency of division and movement.

Insert continuous data:

Insert discontiguous data

Thank you for your reading, the above is the content of "detailed introduction of MySQL database index". After the study of this article, I believe you have a deeper understanding of the detailed introduction of MySQL database index, 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.