How does a multi-column index work in MySQL?

More specifically, what data structure does MYSQL use for multi-column indexing? I know MYSQL use Btree for indexing, which can only index one column. How does multi-column indexing work then?

Answer

Think of a MySQL “composite” index this way.

Concatenate all the columns in the index together, then build an BTree index on that ‘single’ string.

Some related comments:

Once you understand that analogy, you can see why the cardinality of the individual columns does not matter. That is, the order of the columns in a composite index does not matter for performance. The order does matter, depending on what the query asks for.

INDEX(a,b) is likely to be useful for these:

 WHERE a = 123
 WHERE b = 5 AND a = 678

But cannot be used for

 WHERE b = 5

(Note on my use of “concatenate”. Since it is not really practical to concatenate floats, dates, signed integers, strings with odd collations, etc as if they were just bytes, I do not mean that InnoDB literally concatenates the bytes together.)