0

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?

2

(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.)

  • can I get your help to understand this statement in your answer -----"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." – Dinesh Kumar Nov 22 '18 at 1:00
  • @DineshKumar - You said "whether the rows are arranged as per column a or by column b in the database page" -- I was saying that the "pages" (aka blocks??) are handled independently of "per column a or ..." – Rick James Nov 22 '18 at 1:17
  • I read that a row inside a single database page has pointer to other row which is next in the increasing order of pk. So how it will be in case of composite pk – Dinesh Kumar Nov 22 '18 at 1:26
  • @DineshKumar - Imagine concatenating the columns of a composite key together. In my example, 11->12->15->... – Rick James Nov 22 '18 at 2:55
  • 1
    @DineshKumar - Yes. And 3/page -- (1,1),(1,2),(1,5), then (1,7)(2,1),(2,2), then (2,3),(2,8),... would better exemplify that the values of a do not relate to the Block splits. – Rick James Nov 23 '18 at 16:51
0

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

  • That link is tagged multiple Database Engines other than MySQL. So, be cautious about any conclusions that you get from it. – Rick James Nov 21 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.