Because the PK is the clustered index, inserts are fastest in primary key order. But how bad is the penalty of inserting in random order? How much data needs to be moved in the worst case, the entire table?
Because in an MVCC environment all updates can be considered as inserts, this really keeps me puzzled.
Another question, which is highly related, is how tables are stored in the tablespace. If I first create table1, add some rows, then create table2, add some rows, and then again add some rows to table1 but with smaller PK-value than the rows I inserted before. Then do the rows I inserted before in table1 have to be copied to the end of the tablespace after table2, or does table2 get moved?
There is very little information available about this in the literature, and maybe you would like to clear things up (in a blogpost?).
I can’t quite think clearly about the math right now, but in the worst case I think something like one page split per every log(n) inserts might occur. I’ll have to think more about that.
An update isn’t quite an insert. Old row versions are maintained in the undo log, which is in a system area of the tablespace.
Rows are not always stored in strict order physically. They are only clustered together by page. Suppose page1 contains rows 1-100, and page2 contains rows 101-200. These pages can be anywhere on disk. So within the tablespace, data from different tables can be mixed freely.
About the math, I think the page splitting frequency has to be proportional to the average row size (which has to be much smaller than the page size). For a large table, we can forget about the endpoint, so only page splits can make the table size grow. The argument follows from the observation that the table size also grows proportionally with average row size.