Index and rows placement within database files

Question

Where are the indexes and data tables stored within a physical database file or a page of a physical file :

• Can there be different rows from different tables in the same physical page ?
• How does MySQL decide where to place a row in a certain page?
• What about indexes placement too ?

I know a little about that for Network Database (IDMSX database), with direct calculated placement on a physical page (and other records stored just near if possible).

Answer 1

The way MySQL stores data depends on storage engine. A concept of a page exists in InnoDB while in MyISAM there are blocks. In InnoDB a page is fixed 16k while a block in MyISAM is of fifferent size depending on type of the block and the size of the record in it.

InnoDB stores tables in B+ tree data structures that they call indexes. The table itself (records with all field values) are stored in index PRIMARY. Any secondary key is also stored in its B+tree index. All indexes of a table are stored in the respective .ibd file if innodb_file_per_table is ON or in ibdata1 if OFF.

MyISAM is different. Records of a table are stored in .MYD file in blocks. Any new record is appended to the end of the MYD file. The MYD file is not a tree - just a set of blocks. If the table has keys, either primary or secondary - they're kept in B+ tree indexes, which are stored in a .MYI file. (I don't remember if it's exactly B+ tree, but some B tree for sure).

Can there be different rows from different tables in the same physical page?

No. A page in InnoDB belongs to some index. Pages can't be shared between indexes. The same for MyISAM blocks.

How does MySQL decide where to place a row in a certain page?

For MyISAM it just adds the record to the end of MYD file. Indexes in MYI are rebuilt accordingly to the tree algorithm. For InnoDB the new record is inserted into B+ tree, so again, accordingly to B+ tree algorithm.

Answer 2

Technically speaking, there is no single answer for "MySQL" itself, because MySQL has a pluggable storage engine architecture and the server itself is essentially unconcerned with and unaware of how the physical storage of data is accomplished. Those details are handled by the storage engines.

The most relevant storage engine in MySQL is InnoDB.

Can there be different rows from different tables in the same physical page?

No, there can't. In fact, tables do not typically even store tables in the same file, if you use the recommended configuration, where each table has its own separate tablespace file; however, even if innodb_file_per_table isn't enabled, pages aren't shared among tables. By default the innodb_page_size is 16K bytes, although 8k and 4k sizes can be used, instead.

How does MySQL decide where to place a row in a certain page?

What about indexes placement too ?

There's only one place any particular row or index entry can go, because rows are stored sorted by the primary key columns and index entries are stored sorted by the indexed columns.

The pages that make up each table are arranged in a tree data structure called a B-tree index. Table data and secondary indexes both use this type of structure. The B-tree index that represents an entire table is known as the clustered index, which is organized according to the primary key columns. The nodes of the index data structure contain the values of all the columns in that row (for the clustered index) or the index columns and the primary key columns (for secondary indexes).

^{— http://dev.mysql.com/doc/refman/5.6/en/innodb-row-format-overview.html}

Row data that doesn't fit the page, int he case of BLOB AND sometimes VARCHAR columns are stored outside the b-tree page, in an overflow page, referenced by a pointer to the off-page location. The column may be stored fully off-page or partially (so that some number of prefix characters are available on-page to reduce the need for off-page accesses in some cases). This behavior varies by row format and whether you are using internal table compression. Table compression can improve performance when your system is I/O-bound but has available CPU cycles, since it reduces the overall disk I/O.

If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full. If the fill factor of an index page drops below 1/2, InnoDB tries to contract the index tree to free the page.

^{— http://dev.mysql.com/doc/refman/5.6/en/innodb-physical-structure.html}

Of course, when new data is inserted, the entire contents of the tablespace aren't "moved down" to make room for additional pages. The pages are linked, so how consecutive on disk the pages are stored relative to the internal ordering on each page depends on whether the data was inserted sequentially or randomly.

Significantly, the InnoDB buffer pool makes the underlying storage implementation less relevant -- as it should be, in an RDBMS -- less relevant, by providing an intermediate buffer between the physical storage and the higher layers. This buffer is a fixed amount of memory, allocated at server daemon startup, that makes the physical disk storage less significant.

InnoDB maintains a storage area called the buffer pool for caching data and indexes in memory. Knowing how the InnoDB buffer pool works, and taking advantage of it to keep frequently accessed data in memory, is an important aspect of MySQL tuning.

The larger the buffer pool, the more InnoDB acts like an in-memory database, reading data from disk once and then accessing the data from memory during subsequent reads. The buffer pool even caches data changed by insert and update operations, so that disk writes can be grouped together for better performance.

The pool insert/update operations are, of course, committed to disk immediately, but they are not written directly to their place on disk in the pages where they are stored. The changes to be written are logged (using a sequential disk write) and updated in-memory, on-page, in the InnoDB buffer pool, and then the pages that were changed in the buffer pool are flushed (written out) to their place in the tablespace file by a background thread.