MySQL Indexes

🌐 中文

English

This article aims to provide a systematic discussion on MySQL indexes.

What is an Index

An index is a data structure used to improve the efficiency of database queries. It can speed up SELECT query operations by being built on columns of a table.

Categories of Indexes

1. Clustered Index: A clustered index stores data within the index itself, where the index and data are integrated. It is used in the B+ tree index structure of MySQL’s InnoDB storage engine.
2. Non-clustered Index: Any index where data and index are stored separately is a non-clustered index, such as secondary indexes, non-clustered composite indexes, etc. For example, the MyISAM storage engine uses separate MYD and MYI files to store data and indexes, employing a B+ tree index structure that does not store data but uses pointers to jump to the data.

Indexes in Different Storage Engines

Here are the common storage engines:

• InnoDB: Must have one clustered index and can have multiple secondary indexes.
• MyISAM: Has multiple non-clustered indexes that use pointers to jump to data.
• Memory: Uses Hash indexes, with data stored in memory.
• Archive: Only has a single non-clustered index and does not support secondary indexes.
• CSV: Does not support any indexes.

B+ Tree Index

The most commonly used storage engine in MySQL is InnoDB, which employs the B+ tree index structure.

A B+ tree is a multi-way balanced search tree, representing an optimization from binary search tree -> AVL tree -> B tree -> B+ tree.

• The drawback of a binary search tree is that uneven node distribution can cause the tree to become skewed, leading to query efficiency approaching O(n) like a linked list, hence the emergence of AVL trees (balanced binary search trees).
• The drawback of AVL trees is that they are not “short and stout” enough, with insufficient branches, resulting in excessive height and still poor query efficiency.
• A B tree is a special M-ary tree where each node can store multiple data entries and have multiple child nodes. However, using in-order traversal requires repeated node jumps to access data, and each node contains data occupying space. This reduces the number of child nodes that can be pointed to when the data page size is 16KB, leading to increased tree height.
• A B+ tree is a special type of B tree where each node only stores indexes via hashing, with data stored in leaf nodes (data pages). Leaf nodes are connected by a doubly linked list, and internal data is connected by a singly linked list. The height difference between leaf nodes does not exceed 1, and since only the bottom nodes contain data occupying space, the upper data pages can point to more child nodes when the page size is 16KB, resulting in a lower tree height.

Moreover, with a data page size of 16KB, a B+ tree can theoretically handle 1 billion data entries in 4 layers, with a time complexity of O(logN). The root node is kept in memory, while the rest are stored on disk. Each query requires at most 3 disk I/O operations, and the height of a B+ tree is very stable, making it an excellent index structure.

Hash Index

A Hash index is more efficient than a B+ tree index for equality queries, but it has significant drawbacks:

• Inefficient for range queries, degrading to O(n).
• The hash calculation method can cause hash collisions in columns with many duplicates, reducing query efficiency to nearly O(n) like a linked list.
• Hash combines and sums the keys of composite indexes for calculation, so it cannot utilize the leftmost prefix principle like B+ trees.
• Data stored via hashing is unordered, requiring re-sorting for ORDER BY, so it cannot be used for sorting.

It is used in storage engines like Memory.

Summary

The above is a systematic discussion on MySQL indexes.