Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 79 ยท Storage and Indexing

Disks, Pages and the Buffer Pool

Learn the storage hierarchy, HDD vs SSD costs, how rows are packed into pages, slotted-page layout and LRU or clock buffer replacement, with live demos.

Everything a database stores ends up on a physical device, and the way a DBMS organizes bytes on that device decides how fast every query will be. The core idea of the whole storage layer fits in one sentence: disk access is thousands of times slower than memory access, so the database reads and writes in big fixed-size blocks called pages, and keeps the useful ones in a cache called the buffer pool.

In this lesson you will see why that design exists, how rows are packed inside a page, how a buffer pool decides what to throw out, and how to inspect page-level numbers in SQLite.

The storage hierarchy

CPU cache Nanoseconds. Kilobytes to megabytes.
Main memory About 100 ns. Gigabytes. Volatile.
SSD or disk Microseconds to milliseconds. Terabytes.
Tape, cloud archive Seconds or more. Cheapest per byte.

Each step down is bigger, cheaper and much slower.

1 / 2

The storage hierarchy and its costs

A computer has several kinds of storage, arranged by speed. The numbers below are rough orders of magnitude, not measurements of any one machine, but the ratios are what matter:

Level Typical access time Typical size Survives power loss?
CPU cache about 1 to 10 ns KB to MB No
Main memory (RAM) about 100 ns GB No
SSD about 20 to 100 microseconds hundreds of GB to TB Yes
Hard disk (HDD) about 5 to 10 ms TB Yes

RAM is about 100,000 times faster than a spinning disk. That gap explains why databases measure the cost of a query mostly in number of page I/Os: CPU work on data that is already in memory is almost free by comparison.

HDD versus SSD

A hard disk has a head that must move over the platter to the right track (seek) and wait for the data to rotate under it (rotational delay). Together these take several milliseconds, no matter how little data you want. Once the head is in place, reading the following bytes is fast. So an HDD strongly rewards sequential access: reading 1,000 neighboring pages is far cheaper than reading 1,000 random ones.

An SSD has no moving parts, so random reads are fast. But flash memory is written in pages and erased in much larger blocks, and a page cannot be overwritten in place. The drive therefore remaps writes and cleans up in the background, which causes write amplification and wears the cells out. SSDs make random reads cheap, but sequential access is still usually faster and gentler on the drive, and database designs from the HDD era (log-structured writes, big pages) still pay off.

Either way the lesson is the same: do few I/Os, and prefer sequential ones.

Pages

A database file is divided into pages (also called blocks) of fixed size. A page is the unit that is read from and written to disk, and the unit that is cached in memory. Common sizes are 4 KB (SQLite's default), 8 KB (PostgreSQL) and 16 KB (MySQL InnoDB). Bigger pages mean fewer I/Os for scans but more wasted bytes when you only want one row.

Rows (records) are stored inside pages, and an index node is also a page. A row is identified by a record id (RID): the pair (page number, slot number). An index entry stores a RID, so one index lookup plus one page read finds the row. In SQLite the same role is played by the rowid.

Records are rarely the same size. A title TEXT column holds 3 characters in one row and 80 in another. Systems store variable-length fields either with a length prefix or with an array of field offsets at the start of the record, and use a small bitmap for NULL values so absent values take almost no space. A record that is bigger than a page is stored in overflow pages that are chained from the main page.

Spanned and unspanned records

When records are stored in fixed-size blocks, one question remains: may a record start in one block and continue in the next? In unspanned organization a record must fit entirely inside a block. The leftover bytes at the end of each block are wasted, but every record needs only one block read. In spanned organization a record may be split across two blocks, using every byte but needing pointers between the pieces and sometimes two reads for one record. Large objects (long text, images) are always spanned in practice.

For fixed-length records of R bytes in blocks of B bytes, the blocking factor is how many fit in one block: bfr = floor(B / R) unspanned (the wasted space is B - bfr x R). A file of r records then needs ceil(r / bfr) blocks. With 4,096-byte blocks and 300-byte records, bfr = floor(4096 / 300) = 13, wasting 196 bytes per block, and 10,000 records need ceil(10000 / 13) = 770 blocks. Spanned storage would need ceil(10000 x 300 / 4096) = 733 blocks.

The slotted-page layout

How should a page hold a changing set of variable-length records? Storing them back to back is easy, but deleting one leaves a hole, and moving records would break their RIDs. The standard answer is the slotted page:

TEXT
+--------+------------------+-------------- free space --------------+----------+----------+----------+
| header | slot 0 | slot 1 |                                          | record 2 | record 1 | record 0 |
+--------+------------------+-----------------------------------------+----------+----------+----------+
  grows ->                                                                         <- records grow backwards
  • The header holds the number of slots and where the free space ends.
  • The slot array grows from the front. Slot i stores the offset and length of record i.
  • The records themselves grow from the end of the page toward the front.
  • Free space is the gap in the middle. The page is full when the slot array and the record area meet.

Because outsiders refer to a record by its slot number, the system can move the record inside the page (for example to squeeze out the holes after a delete) just by updating the slot, and the RID stays valid. A deleted record's slot is marked empty and can be reused.

Python A slotted page in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the numbers. A 128-byte page with four short records has 58 free bytes. Deleting a record leaves an 11-byte hole inside the record area, so the usable gap stays at 58 and a 64-byte record does not fit (None). Only compact() slides the remaining records together and merges the hole into the gap, after which the same insert succeeds and reuses the empty slot. Notice that slot 3 keeps returning the same name after compaction: the record moved, its RID did not.

Checking real page numbers in SQLite

SQLite stores everything (tables, indexes) in pages of one size per database. A few PRAGMA functions report the numbers, so you can see how many pages your data really occupies. The first example creates a table with about 100 bytes of text per row and watches the file grow.

SQL Page size and page count in SQLite

Press Run (or Ctrl + Enter) to see the result here.

The file starts with 2 pages (page 1 holds the schema, page 2 is the table's root page) and ends with about 65. That is close to what you would expect: about 220 KB of row data divided into 4 KB pages, plus the B-tree interior pages. Every extra page is a potential disk read.

Indexes, deletes and cleanup also show up in the page counts. Pages freed by a DELETE do not shrink the file; they go onto a free list for later reuse until VACUUM rebuilds the file compactly.

SQL Indexes, free pages and VACUUM

Press Run (or Ctrl + Enter) to see the result here.

Compare the four rows: the index costs additional pages, the delete creates free pages without shrinking the file, and VACUUM repacks the file so the free list is empty. (SQLite's dbstat virtual table can show the pages of each table and index individually; it is not available in this in-browser build, so it is not shown.)

The buffer pool

When the query processor needs a page, it asks the buffer manager. The buffer manager keeps a fixed number of in-memory frames, each of which can hold one page:

  • If the page is already in a frame (a hit), it returns it without any I/O.
  • If not (a miss), it picks a frame, writes the old page back if it was modified (dirty), reads the requested page into the frame, and returns it.

Each frame also carries a pin count (the number of users currently using the page; pinned pages cannot be evicted), a dirty bit, and bookkeeping for the replacement policy. A hash table (the page table) maps page numbers to frames. The recovery manager constrains the buffer manager too: a dirty page may not be written until its log records are on disk.

Replacement policies

When all frames are full, which page should leave? The best choice is the one that will not be needed for the longest time, but nobody can see the future, so policies guess from the past.

  • LRU (least recently used) evicts the page whose last access is oldest. It works well when recently used pages are likely to be reused again.
  • Clock is a cheap approximation of LRU. Frames sit in a circle with a reference bit that is set whenever the page is used. A "hand" sweeps around: if the bit is 1, it clears it and moves on; if it is 0, that page is evicted. Used pages get a second chance without the cost of keeping an exact usage order.
  • MRU and scan-resistant variants matter because LRU has a weakness: a large sequential scan reads every page once, pushes out the hot pages, and gets no benefit from caching what it read. Real systems protect against this with a small ring buffer for scans or with variants such as LRU-K and 2Q.

The simulator below compares LRU and Clock on a workload where a small set of hot pages (1 to 3) is used constantly, while a one-time scan of pages 10 to 25 passes through a pool of 5 frames.

Python Buffer pool: LRU versus Clock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the mixed workload both policies keep most hot-page accesses as hits and only the scan pages miss. LRU is slightly ahead because it tracks exact recency, while Clock gets close with only one bit per frame, which is why many systems use it. In the pure repeated scan neither policy gets a single hit: the table is bigger than the pool, so each page is evicted before it comes around again. That is why the buffer pool size, and the size of your data compared with it, is one of the most important performance facts about a database.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the cost of a query usually measured in page I/Os?

    A disk access takes microseconds to milliseconds, while memory access takes about 100 nanoseconds, so the number of pages fetched usually dominates the running time.
  2. 2. In a slotted page, why does a record keep the same RID when the page is compacted?

    A RID is (page, slot). Records may be shifted inside the page, but the slot entry that points at them is updated, so references from indexes stay valid.
  3. 3. How does the clock replacement policy approximate LRU?

    A set reference bit means the page was used since the last sweep. The hand gives such a page a second chance by clearing the bit, and evicts a page that was not used.
  4. 4. In SQLite, what happens to the file size when you DELETE half of a table's rows?

    SQLite reuses free pages for later inserts but does not give them back to the operating system until the database is vacuumed.
  5. 5. Why can a large sequential scan hurt an LRU buffer pool?

    Each scanned page becomes 'most recently used' although it will probably never be read again, so useful hot pages are evicted. Scan-resistant policies and small scan buffers avoid this.

Summary

  • Disk is orders of magnitude slower than RAM, so databases count page I/Os and prefer sequential access, which matters most on HDDs.
  • Data lives in fixed-size pages (commonly 4, 8 or 16 KB); a record is addressed by a RID of page and slot.
  • A slotted page stores a slot array from the front and records from the back, so records can move without changing RIDs.
  • PRAGMA page_size, page_count and freelist_count expose page-level facts in SQLite; indexes add pages, deletes add free pages and VACUUM repacks the file.
  • The buffer pool caches pages in frames with pin counts and dirty bits; LRU and clock choose victims, and big scans are the classic enemy of plain LRU.

Next: File Organization: Heap, Sorted and Clustered.