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?
Advertisement
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.)