The MySQL InnoDB storage engine lives off primary keys: Records are stored physically in a B+-Tree, a balanced tree where the data pages are the leaves of the primary key B-Tree.
That implies that the data is stored physically in primary key order – records with similar primary keys are usually physically closer together than records with larger differences in primary key value. In literature, such physically ordered indexes are often called clustered indexes.
InnoDB depends on primary keys
Secondary indexes in databases need to store the indexed data together with a row address, a pointer to the full row (in InnoDB, into the primary key).
If that row address was a physical address (a disk block number or a similar pointer tied to the position of the data), growing data pages and moving them around would …
[Read more]