多列B-Tree索引的使用、复合索引排序规则及优化问题

Great question! Composite indexes are a total workhorse in databases, but their inner workings can feel opaque at first. Let’s break this down clearly, using your examples as a starting point.

How Composite Indexes Are Sorted #

Composite B-tree indexes follow a left-prefix, hierarchical sorting rule—it’s not a "combined comparison" of both columns at once. Here’s the exact logic:

1. First, the index sorts all entries by the first column in your index definition (like column1 in your example).
2. For entries where the first column has identical values, the index then sorts those subsets by the second column (like column2), and this pattern continues for any additional columns in the index.

Let’s make this tangible with your sample data, plus one extra row to show the grouping behavior. Suppose we have these rows:
(2, name2), (3, name3), (1, name4), (2, name1)

A composite index on (column1, column2) would be ordered like this:

1 | name4
2 | name1
2 | name2
3 | name3

Notice how all entries with column1=2 are grouped together first, then sorted by column2 within that group. This left-priority rule is critical—it’s why queries that don’t use the leftmost column(s) of the index often can’t leverage it efficiently.

Additional Database Optimizations for Indexes #

Databases don’t just stick to basic B-tree structure—they layer on several smart optimizations to make indexes faster and more space-efficient:

• Prefix Compression: For repeated values in the leftmost index columns (like multiple entries with column1=2), engines like InnoDB compress duplicate prefixes. This cuts down the index’s disk footprint and speeds up I/O, since fewer bytes need to be read from disk.
• Covering Indexes: If your query only needs columns that are already in the composite index, the database can return results directly from the index without accessing the main table (a "table lookup"). This eliminates the overhead of fetching full rows—for example, SELECT column2 FROM your_table WHERE column1 = 2 would use the (column1, column2) index as a covering index, skipping the main table entirely.
• Index Condition Pushdown (ICP): Instead of fetching all rows that match the leftmost index condition and then filtering on other columns, ICP pushes secondary column conditions down to the storage engine. The engine filters out non-matching entries at the index level before sending rows to the database server, reducing the number of costly table lookups.
• Adaptive Hash Indexes: Engines like InnoDB automatically build hash indexes for frequently accessed index pages. This combines the B-tree’s strength in range queries with the hash index’s lightning-fast O(1) lookup speed for exact matches, giving a performance boost for hot, frequently queried data.
• Partitioned Indexes: If your table is partitioned (e.g., by date), the composite index splits into partitions matching the table’s structure. Queries only need to scan the relevant index partitions instead of the entire index, drastically cutting down scan time.

内容的提问来源于stack exchange，提问作者lapots