How to understand Composite Primary Key when it comes to storage (in Mysql)?

Question

I can image how rows will be arranged in a single database page as primary key order (example an auto-increment key) after reading this post. But I wonder how it will in the case of composite primary keys. For example consider a pk(a integer, b integer), whether the rows are arranged as per column a or by column b in the database page?

Answer 1

(This answer is focused on MySQL; in particular, the InnoDB Engine. JCole's blog (which you linked to) is valid for InnoDB, but might be overly technical. I'll try to give a lighter answer.)

Think of a composite key this way... Concatenate the keys together, then the BTree structure is just as if it had a single-column (though larger) key.

The order of the columns specified in any composite index matters. For PRIMARY KEY(a,b), the rows will be in this order:

a b
- -
1 1
1 2
1 5
1 7
2 1
2 2
2 3
2 8
3 2
...

This means, for example, that WHERE a=2 will find all the rows "clustered" together. But WHERE b=2 will find them scattered.

"Clustering" is also used here to say that the data is right next to the PK in the same BTree.

The block structure (16KB blocks in InnoDB) is controlled by whatever happens. That is, there is no obvious place in the pair (a,b) where one block ends and the next starts.

In InnoDB, the PRIMARY KEY is always clustered with the data. As a side effect, there is virtually zero overhead for that one KEY. All "secondary keys" are separate BTrees that have the PK in their leaf nodes.

In the above example, let's say (for conciseness) that there were only 3 rows per Block:

Block 0:  (1,1),(1,2),(1,5)
Block 1:  (1,7),(2,1),(2,2)
Block 2:  (2,3),(2,8),(3,2)

Note that the breaks in a are unrelated to the Block splits. (Also, this example may be misleading -- Blocks rarely have as few as 3 rows; Blocks do not necessarily have the same number of rows each.)

Answer 2

MySQL doesnt (to my knowledge) deviate from standards here. Explained wellin the answer to this post: https://stackoverflow.com/questions/1648217/what-does-a-b-tree-index-on-more-than-1-column-look-like