An Introduction to Clustered Indexes

Abstract

[Reprinted] http://www.manongjc.com/detail/17-ssuthexbuzbjmlb.html

This article introduces MySQL clustered and non-clustered indexes, mainly covering usage examples, application tips, a summary of basic knowledge points, and things to watch out for. It has some reference value, so interested readers can take a look.

Basic Introduction

A clustered index is not a separate type of index, but rather a way of storing data, with the specific details depending on the implementation. InnoDB’s clustered index actually stores both the B+Tree index and the data rows in the same structure.

When a table has a clustered index, its data is actually stored in the leaf pages of the index (the leaf pages contain all of the row’s data). Without a clustered index, the B+Tree leaf pages store pointers to the data. (A page is the smallest storage unit of a MySQL storage engine; InnoDB’s default page size is 16K.) You can think of it this way: with a clustered index, the data and its corresponding leaf page are in the same page; without a clustered index, the leaf page and its corresponding data are not in the same page.

The InnoDB storage engine clusters data by primary key (the clustered index). If no primary key is defined, InnoDB chooses a unique non-null index instead. If there is no unique index, InnoDB implicitly defines a primary key to serve as the clustered index. InnoDB only clusters records within the same page. Pages containing adjacent key values may be far apart.

In MyISAM, both the primary key index and other indexes point to the physical row (non-clustered index).

The diagram below shows how a clustered index is stored (image from “High Performance MySQL, 3rd Edition”):

The difference between clustered and non-clustered indexes

With a clustered index, the order of the index is the order in which the data is stored (the physical order). As long as the indexes are adjacent, the corresponding data is certainly stored adjacently on disk too. A table can have only one clustered index. (Within a data page, the physical storage of data is ordered.)

A non-clustered index finds data in a data page through leaf-node pointers, so a non-clustered index follows logical order.

Advantages of the clustered index

• The order in which data is stored matches the index order, so related data can be kept together. For example, when implementing an email mailbox, you can cluster data by user ID, so that retrieving all of a user’s mail only requires reading a small number of data pages from disk. Without a clustered index, every email could cause a disk I/O.
• Data access is faster. A clustered index keeps the index and the data in the same B-Tree, so retrieving data from a clustered index is usually faster than a non-clustered index lookup.
• Queries using a covering-index scan can directly use the primary key values in the page nodes (the leaf nodes of a secondary index (non-clustered index) store not a pointer to the row’s physical location, but the row’s primary key value).

(PS: covering index — MySQL can use an index to directly obtain a column’s data, so it doesn’t need to look up the index and then read the data row via the leaf-node pointer (the table lookup). If the leaf nodes of the index already contain — that is, cover — all the field values needed by the query, then there’s no need to go back to the table. This is called a “covering index.”)

Disadvantages of the clustered index

• Clustered data improves I/O performance; if all the data fits in memory, then the order of access doesn’t matter as much.
• Insert speed depends heavily on insert order. Inserting in primary-key order is the fastest. But if data is not loaded in primary-key order, it’s best to use OPTIMIZE TABLE to reorganize the table after loading.
• Updating clustered index columns is expensive, because it forces InnoDB to move each updated row to a new location.
• Tables based on a clustered index may face page-split problems when inserting new rows, or when a primary key is updated in a way that requires moving rows. Page splits cause the table to take up more disk space.
• A clustered index may slow down full table scans, especially when rows are sparse, or when page splits cause data storage to be non-contiguous.
• Non-clustered indexes are larger than you might think, because a secondary index’s leaf nodes contain the primary key columns of the referenced row.
• Non-clustered index access requires two index lookups (the row pointer stored in the leaf node of the non-clustered index points to the row’s primary key value); for InnoDB, the adaptive hash index can reduce this kind of duplicate work.

For a clustered index, try to choose ordered columns (such as an AUTO_INCREMENT auto-increment column), so that data rows are written sequentially; this also yields better performance for join operations based on the primary key.

It’s best to avoid random (non-contiguous and very widely distributed) clustered indexes, especially for I/O-intensive applications.

From a performance standpoint, using UUIDs as a clustered index is terrible. It makes clustered-index inserts completely random — the worst case — so that the data has no clustering property whatsoever.

To summarize the drawbacks of using random clustered indexes like UUIDs:

• UUID fields are long, so the index takes up more space.
• Writes are out of order, forcing InnoDB to frequently perform page splits to allocate space for new rows. Page splits move large amounts of data, and a single insert requires modifying at least three pages instead of one.
• The target page being written to may have already been flushed to disk and evicted from the cache, or may not yet have been loaded into the cache. Before inserting, InnoDB has to first locate and read the target page from disk into memory, which causes large amounts of random I/O.
• Frequent page splits make pages sparse and irregularly filled, producing space fragmentation.

https://www.cnblogs.com/learn-ontheway/p/12150521.html

MySQL’s InnoDB index data structure is a B+Tree. The leaf nodes of the primary-key index store the MySQL data rows themselves, while the leaf nodes of an ordinary index store the primary key value. This is the prerequisite for understanding clustered and non-clustered indexes.

What is a clustered index?

Just remember one sentence: if finding the index means you’ve found the data you need, then that index is a clustered index. So the primary key is the clustered index, and modifying the clustered index actually means modifying the primary key.

What is a non-clustered index?

The storage of the index and the storage of the data are separated; that is, you’ve found the index but not the data, and you need to use the value on the index (the primary key) to do another table lookup. A non-clustered index is also called a secondary index.

clustered index (MySQL’s official explanation of clustered index)

The InnoDB term for a primary key index. InnoDB table storage is organized based on the values of the primary key columns, to speed up queries and sorts involving the primary key columns. For best performance, choose the primary key columns carefully based on the most performance-critical queries. Because modifying the columns of the clustered index is an expensive operation, choose primary columns that are rarely or never updated.

Note the highlighted passage: a clustered index is just a term for the primary key.

An example

Below we create a student table and run three queries to illustrate when an index is a clustered index and when it is not.

create table student (
    id bigint,
    no varchar(20) ,
    name varchar(20) ,
    address varchar(20) ,
    PRIMARY KEY (`branch_id`) USING BTREE,
    UNIQUE KEY `idx_no` (`no`) USING BTREE
)ENGINE=InnoDB DEFAULT CHARSET=utf8 ROW_FORMAT=DYNAMIC;

First, querying directly by primary key to get all field data: here the primary key is a clustered index, because the leaf node of the index corresponding to the primary key stores all the field values for id=1.

select * from student where id = 1

Second, querying the number and name by number. The number itself is a unique index, but the queried columns include both the student number and the student name. When the number index is hit, the data stored in that index’s node is the primary key ID, requiring another lookup by primary key ID. So in this query, no is not a clustered index.

select no,name from student where no = 'test'

Third, we query the number by number (someone might ask: if you already know the number, why query it? You do — you may need to verify whether the number exists in the database). When this query hits the number index, it directly returns the number, because the data needed is the index itself, with no table lookup required. In this scenario, no is a clustered index.

select no from student where no = 'test'

Summary

The primary key is always a clustered index. In MySQL’s InnoDB there is always a primary key: even if developers don’t set one manually, it uses a unique index; if there’s no unique index, it uses an internal row ID as the primary key index. Other ordinary indexes depend on the SQL scenario: when the columns queried by the SQL are exactly the index itself, we say that in this scenario the ordinary index can also be called a clustered index. The MyISAM engine has no clustered index.

Original link: https://blog.csdn.net/xingduan5153/article/details/106189340/

Recommended: https://www.cnblogs.com/jiangds/p/8276613.html

Index Optimization

1. By default, the index created is a non-clustered index, but sometimes that’s not optimal. With a non-clustered index, data is physically stored randomly on data pages. Reasonable index design must be based on the analysis and prediction of various queries. Generally speaking:
   a. For columns that have many duplicate values and frequently undergo range queries ( > , < , >= , <= ) as well as ORDER BY and GROUP BY, consider building a clustered index;
   b. For columns frequently accessed together where each contains duplicate values, consider building a composite index;
   c. A composite index should, as far as possible, make key queries form index coverage, and its leading column must be the most frequently used column. Although indexes help improve performance, more is not always better — quite the opposite, too many indexes lead to system inefficiency. Every time a user adds an index to a table, the index set must be updated accordingly.
2. ORDER BY and GROUP BY: when using ORDER BY and GROUP BY phrases, any kind of index helps improve SELECT performance.
3. For multi-table operations, before actually executing, the query optimizer lists several possible join schemes based on the join conditions and finds the one with the lowest system cost. Join conditions should fully consider tables with indexes and tables with many rows; the choice of inner and outer tables can be determined by the formula: number of matching rows in the outer table * number of lookups per search in the inner table — the smallest product is the best scheme.
4. Any operation on a column will cause a table scan, including database functions, computed expressions, and so on. When querying, move operations to the right-hand side of the equals sign whenever possible.
5. IN and OR clauses often use worktables, invalidating indexes. If they don’t produce many duplicate values, consider splitting the clauses apart. The split clauses should include indexes.