How Tables and Indexes Are Stored on Disk and How They Are Queried
Storage Concepts
Table
Row ID
Page
IO
Heap data structure
Index data structure (B-tree)
Example of a query
Row ID
The Row ID is an internal and system-maintained identifier.
In some databases like MySQL (InnoDB), it is the same as the primary key.
In other databases like PostgreSQL, there is no row_id; the system column is ctid (the tuple ID: (page number, item index) of the row version in the heap). It changes when the row is updated or the table is rewritten, so it is not a stable identifier.
Page
Depending on the storage model (row store vs. column store), rows are stored and read in logical pages.
A database does not read a single row; it reads a page or more in a single IO operation.
Each page has a fixed size:
PostgreSQL: 8 KB
MySQL: 16 KB
For example, if each page holds 3 rows and you have 1001 rows, you’ll need approximately 1001 / 3 = 334 pages.
IO (Input/Output)
An IO operation is a read request to the disk.
IOs are expensive, so we try to minimize them.
An IO typically fetches an entire page (or more), not just a single row.
You get all the rows in the page “for free” once the page is loaded.
Some IOs can be served from the OS cache instead of accessing the physical disk.
Heap
A heap is a data structure where a table is stored with all its pages laid out sequentially.
This is where the actual data is stored — including all columns and rows.
Heap scans are expensive because you must read many pages to find what you need.
This is why indexes are used — they help pinpoint the exact page(s) you need to access in the heap.
Index
An index is a separate data structure from the heap and contains pointers to data in the heap.
It contains part of the data and is used to quickly locate rows.
You can index on one or more columns.
After locating a match in the index, the database follows a pointer to the heap to retrieve the full row.
An index helps avoid scanning the entire heap by telling you exactly which page to fetch.
Indexes are also stored in pages and thus require IO to access.
The smaller the index, the more likely it fits in memory, which results in faster searches.
A common data structure for indexes is the B-tree.
Additional Notes
Sometimes the heap can be organized around a single index. This is called a clustered index or an Index Organized Table.
Whether the primary key is a clustered index depends on the engine: yes in InnoDB (and the SQL Server default); in PostgreSQL a PK is just a unique B-tree pointing into the unordered heap.
In MySQL (InnoDB):
There is always a primary key (clustered index).
Other indexes point to the primary key value.
In PostgreSQL:
All indexes are secondary indexes.
Indexes point directly to the row ID (ctid), which is located in the heap.