How databases store data
Underneath every table is a careful arrangement of bytes on disk and in memory. Understanding storage explains why some queries are fast and others crawl.
The storage hierarchy
Databases juggle memory and persistent storage. RAM is fast but volatile and limited; SSDs and hard disks are persistent and large but far slower, with a random hard-disk read taking around 10 milliseconds compared with about 100 nanoseconds for RAM. Database design aims to minimise slow storage accesses, especially random ones.
Pages
Databases read and write storage in fixed-size pages or blocks, commonly 4, 8, or 16 kilobytes; PostgreSQL uses 8 KB and MySQL's InnoDB 16 KB by default. A page holds many rows plus a header. The cost of a query is often estimated by how many pages it must read, so packing related rows into the same pages matters.
Row layout
Within a page, a slotted-page design keeps a directory of pointers to rows, so rows of varying length can move within the page without changing their external identifiers. Each row stores a header, null flags, and column values; fixed-length values are easy to locate, while variable-length strings need offsets. Very large values may be stored separately, such as PostgreSQL's TOAST mechanism.
Heap files and clustered storage
The simplest organisation is a heap file: rows are stored in no particular order, wherever there is space. Insertion is fast, but finding specific rows without an index requires a full scan. Some systems cluster rows physically by key: InnoDB stores each table's rows inside its primary-key B+ tree, so range scans by primary key read neighbouring pages.
The buffer pool
A database keeps recently used pages in a memory area called the buffer pool. When a query needs a page, the buffer manager checks the pool first, avoiding disk if possible. When the pool is full, a replacement policy, often a variant of least recently used (LRU) or the clock algorithm, chooses pages to evict, writing modified (dirty) pages back to storage first.
Row stores and column stores
Row-oriented storage keeps each row's values together, ideal for transactional workloads that read or write whole records, such as fetching one customer. Column-oriented storage keeps each column's values together, ideal for analytics that scan a few columns across millions of rows, such as averaging sales by region. Columns of similar values also compress extremely well.
Compression and partitioning
Column stores use encodings such as run-length encoding, storing 'France x 10,000' instead of 10,000 copies, and dictionary encoding, replacing strings with small integer codes. Partitioning splits a large table into pieces by range, list, or hash of a column, such as one partition per month, so queries for one month touch only one partition and old data can be dropped quickly.
Worked example
A table of 10,000,000 rows, each 200 bytes, in 8 KB pages holds about 40 rows per page, roughly 250,000 pages, about 2 gigabytes. A full scan reads all 250,000 pages. If the query needs only one row and an index leads directly to its page in 3 or 4 page reads, the index makes the query tens of thousands of times cheaper in page reads.
Key takeaways
Databases minimise slow, especially random, storage access. Data is read and written in pages, such as 8 KB in PostgreSQL and 16 KB in InnoDB. Slotted pages store variable-length rows flexibly. Heap files store rows unordered; clustered storage orders them by key. The buffer pool caches pages in memory, evicting with LRU-like policies and writing dirty pages back. Row stores suit transactions; column stores suit analytics and compress well with run-length and dictionary encoding. Partitioning splits big tables so queries touch less data.
Flashcard
Fixed-size unit of storage I/O
Check your understanding
An analytics query averages one column over 500 million rows. Why might a column store beat a row store?