SQL 101 🛢️ Storage Engines Architecture and Page Layouts

The storage engine is the component of a database that decides how data is physically written to disk, how it is read back, and how concurrent access is managed. The query planner and the SQL parser sit above it; the operating system and the disk sit below it. When you run SELECT * FROM users WHERE id = 42, the storage engine is what translates that logical request into a seek on a B-tree, a read of a specific page, and a scan of a tuple header to find the column offsets. Different storage engines make different trade-offs—row-oriented versus column-oriented, B-tree versus heap, transactional versus non-transactional—and those trade-offs determine whether the database is fast for your workload or catastrophically slow.

The page is the fundamental unit of that physical I/O. Every major relational database reads and writes in fixed-size pages: 16 KB in InnoDB, 8 KB in SQL Server, 8 KB by default in PostgreSQL, and variable (512 bytes to 64 KB) in SQLite . The page layout is not an implementation detail. It determines how much overhead each row carries, how free space is managed, how updates are handled when a row grows, and how much of a page a single query must read. Understanding the page is understanding the physical cost of every query.

Key point: The storage engine manages how rows are stored in pages, and the page layout determines the overhead and the free-space behavior. InnoDB stores tables as B+trees with 16 KB pages; PostgreSQL uses 8 KB heap pages with item identifiers and tuple headers; SQL Server uses 8 KB pages with a 96-byte header and a row-offset table; SQLite uses variable-size pages managed by a free-list. The engine choice and the page layout are the two decisions that most affect read/write performance and update behavior.

---

Why the storage engine and page layout matter

The row-oriented versus column-oriented problem. The dominant storage engines in OLTP databases are row-oriented: a row’s columns are stored together, so reading a full row is a single page read. Column-oriented engines store each column separately, so an aggregate over one column reads only that column’s data and skips the rest. The trade-off is that row-oriented engines are fast for point lookups and transactional writes, while column-oriented engines are fast for analytical scans. The page layout in a row-oriented engine is designed around fitting as many complete rows as possible into a page, with the row header carrying the information needed to locate each column within the row.

The B-tree versus heap problem. InnoDB stores table data inside the primary key B+tree. The leaf pages of the B+tree contain the actual rows. There is no separate heap; the table is the index . PostgreSQL and SQL Server use a heap: rows are stored in pages in insertion order (with some caveats), and separate B-tree indexes point to the row’s location. The heap requires an indirection: an index entry points to a tuple identifier (PostgreSQL’s ctid, SQL Server’s row offset), and the page header or row-offset table resolves that identifier to the row’s physical position. The B-tree-as-table design avoids the indirection for primary-key lookups but makes secondary-index lookups more expensive because the secondary index must traverse back to the primary B-tree.

The update problem. When a row is updated and the new version is larger than the old one, it may no longer fit in the page. Oracle handles this with row migration: the row is moved to a new block, and the original row piece is replaced with a pointer . PostgreSQL handles it by writing a new tuple version, which may go to a different page, and the old version remains until vacuumed. InnoDB handles it within the B-tree: the updated row is placed in the appropriate leaf page, and if the page is full, the B-tree splits. The page’s free-space management—the PCTFREE in Oracle, the fillfactor in PostgreSQL, the free-space bitmap in InnoDB—determines how much room is reserved for updates and therefore how often a row must migrate or a page must split.

The overhead problem. Every page has a header, and every row has a header. PostgreSQL’s PageHeaderData is 24 bytes, and its HeapTupleHeaderData is 23 bytes on most machines, plus a null bitmap and alignment padding . SQL Server’s page header is 96 bytes, and its row-offset table consumes 2 bytes per row . Oracle’s block overhead averages 84 to 107 bytes . The overhead is the price of the metadata that makes the page self-describing, and it determines the maximum number of rows a page can hold and the cost of scanning a page.

---

a. InnoDB: the B+tree storage engine

InnoDB is the default storage engine in MySQL and the one that supports transactions, row-level locking, foreign keys, and crash recovery. Its architecture is built around the B+tree: the table’s data is stored in the leaf pages of the primary key B+tree, and every secondary index is a separate B+tree whose leaf entries point to the primary key value rather than to a physical row address .

The page size is 16 KB. The page contains a header, the row data, and a free-space area. The B+tree structure means that a primary-key lookup descends the tree from the root to the correct leaf and reads the row directly. A secondary-index lookup reads the secondary index to find the primary key value, then descends the primary B+tree to find the row. This is the cost of the clustered-index design: secondary lookups are more expensive, but primary lookups are direct.

The engine’s row-level locking and MVCC are what distinguish it from MyISAM. MyISAM uses table-level locking and has no transaction support; a single write locks the entire table, blocking every other read and write . InnoDB’s row-level locks and MVCC allow concurrent readers and writers to proceed without blocking each other, at the cost of the undo log and the purge thread that clean up old row versions.

The free-space management inside the page is handled by the page’s internal structures. When a row is updated and the new version does not fit, the B+tree handles the insertion by splitting the page if necessary. The innodb_file_per_table setting determines whether each table has its own .ibd file or shares the system tablespace; the per-table file is the modern default and the one that makes per-table backup and transport possible.

---

b. PostgreSQL: the heap page

PostgreSQL uses a heap for table storage. Rows are stored in pages, and the pages are managed as a flat array of 8 KB blocks. The page header (PageHeaderData) contains the LSN, checksum, flags, and the three offsets that define the free space: pd_lower, pd_upper, and pd_special . The item identifiers (ItemIdData) grow from pd_lower upward; each is 4 bytes and contains the offset and length of a tuple. The tuples themselves grow from pd_upper downward. The free space is the gap between the two.

The tuple header (HeapTupleHeaderData) is the MVCC control block. It contains t_xmin (the inserting transaction ID), t_xmax (the deleting transaction ID), t_ctid (the tuple ID of this or a newer version), and the t_infomask flags that record whether the tuple has nulls, has an OID, or is the root of a HOT chain . The tuple’s user data begins at t_hoff, which is aligned to the platform’s MAXALIGN. The null bitmap is only present if the tuple has nulls.

The heap-only tuple (HOT) optimization is the mechanism that reduces the cost of updates. When an update does not modify any indexed column and there is sufficient free space on the same page, PostgreSQL writes the new tuple version on the same page and links it from the old tuple via t_ctid. No new index entry is created, and the old tuple can be pruned during normal operation rather than requiring a vacuum . The fillfactor table option reserves space on each page for these updates; a lower fillfactor leaves more room for HOT updates and reduces the need to migrate to a new page.

The ctid is the physical pointer that indexes use. It consists of a page number and an item identifier index. Because the item identifier is never moved until it is freed, the ctid remains valid even when the tuple is moved around within the page to compact free space .

---

c. SQL Server, Oracle, and SQLite: different page architectures

SQL Server uses 8 KB pages and manages them in extents of eight contiguous pages (64 KB). The page header is 96 bytes and contains the page number, page type, free-space amount, and allocation unit ID. The row data is stored serially after the header, and a row-offset table at the end of the page records the offset of each row from the start of the page . The page types include data pages, index pages, text/image pages for large objects, and allocation maps (GAM, SGAM, PFS, IAM) that track which extents are allocated and how much free space each page has. Rows cannot span pages, but variable-length columns can be moved to ROW_OVERFLOW_DATA pages when the row exceeds 8,060 bytes, with a 24-byte pointer left on the original page .

Oracle uses data blocks whose size is set at tablespace creation (typically 8 KB). The block overhead includes the block header (with transaction entries), the table directory, and the row directory . Rows are stored as variable-length records with a row header and column data. The PCTFREE parameter reserves a percentage of each block for updates to existing rows; when a row grows beyond the available space, Oracle either migrates it to a new block (preserving the original row piece as a pointer) or chains it across multiple blocks if it is too large to fit in one block at insert time . The rowid is a stable identifier that points to the file, block, and row directory entry; the row directory entry points to the row’s physical location, so the rowid remains constant even if the row moves within the block .

SQLite uses variable-size pages, from 512 bytes to 65,536 bytes, with the page size stored in the first 2 bytes of the database header . The database file is an array of pages, and the B+tree is the structure that organizes them. Free pages are managed by a free-list; a page that is no longer needed is added to the list and reused for future allocations . The page size is a trade-off: larger pages reduce the depth of the B+tree and the number of I/O operations for large reads, but waste space for small rows and increase the cost of a single page write.

---

Complete Example Session

The following session traces a row through PostgreSQL’s heap page: the page header, the item identifier, the tuple header, and the user data.

// ============================================
// PART 1: THE PAGE HEADER
// ============================================
// PageHeaderData (24 bytes) 
// pd_lsn (8 bytes): LSN of the last WAL record
// pd_tli (2 bytes): timeline ID
// pd_flags (2 bytes): flag bits
// pd_lower (2 bytes): offset to the end of item identifiers
// pd_upper (2 bytes): offset to the start of tuple data
// pd_special (2 bytes): offset to special space
// pd_pagesize_version (2 bytes): page size and version
// pd_prune_xid (4 bytes): oldest unpruned XMAX

// ============================================
// PART 2: THE ITEM IDENTIFIER
// ============================================
// ItemIdData (4 bytes) 
// Each item identifier points to a tuple
// It contains the tuple's offset from the page start
// and its length in bytes
// The ctid of a tuple is (page_number, item_id_index)

// ============================================
// PART 3: THE TUPLE HEADER
// ============================================
// HeapTupleHeaderData (23 bytes) 
// t_xmin (4 bytes): inserting transaction ID
// t_xmax (4 bytes): deleting transaction ID (0 if not deleted)
// t_cid (4 bytes): command ID within the transaction
// t_ctid (6 bytes): tuple ID of this or a newer version
// t_infomask2 (2 bytes): number of attributes + flags
// t_infomask (2 bytes): null bitmap, OID, HOT flags
// t_hoff (1 byte): offset to user data

// ============================================
// PART 4: THE USER DATA
// ============================================
// If the tuple has nulls, a null bitmap follows the header
// The bitmap has one bit per column (1 = not null, 0 = null)
// Alignment padding follows the bitmap
// The user data begins at t_hoff
// Variable-length columns have a varlena header (length + flags)

// ============================================
// PART 5: THE HOT UPDATE
// ============================================
// An UPDATE that does not change indexed columns
// and fits on the same page:
// 1. A new tuple version is written on the same page
// 2. The old tuple's t_ctid points to the new tuple
// 3. No new index entry is created
// 4. The old tuple is pruned during normal operation
// 5. No vacuum is required to reclaim the space

// ============================================
// PART 6: THE PAGE AFTER MULTIPLE UPDATES
// ============================================
// Page 0:
// ┌─────────────────────────────────────────┐
// │ PageHeaderData                         │
// │ pd_lower → item identifiers            │
// │ [ItemId 1] → tuple version 1 (dead)    │
// │ [ItemId 2] → tuple version 2 (dead)    │
// │ [ItemId 3] → tuple version 3 (live)    │
// │ pd_upper → free space                  │
// │ ...                                     │
// │ tuple version 3                        │
// │ tuple version 2 (pruned or waiting)    │
// │ tuple version 1 (pruned or waiting)    │
// │ special space                          │
// └─────────────────────────────────────────┘
// The ctid chain: version 1 → version 2 → version 3
// Indexes point to version 1's item ID
// HOT chain follows t_ctid to the live version

The six parts cover the page header, the item identifier, the tuple header, the user data, the HOT update, and the page after multiple updates. What the session demonstrates is that the page is not a black box: it has a header that defines the free space, an array of item identifiers that point to tuples, and tuples with headers that carry the MVCC information. The HOT chain is the mechanism that makes updates cheap when the indexed columns are not changed.

---

Quick Reference

Page Sizes

Engine	Page Size	Extent
InnoDB	16 KB	1 MB (64 pages)
PostgreSQL	8 KB (default)	1 MB (128 pages)
SQL Server	8 KB	64 KB (8 pages)
Oracle	8 KB (typical)	Variable
SQLite	512 B – 64 KB	N/A

Storage Architecture

Engine	Table Storage	Secondary Index
InnoDB	Primary key B+tree	B+tree pointing to PK
PostgreSQL	Heap	B-tree pointing to ctid
SQL Server	Heap or clustered index	B-tree pointing to row
Oracle	Heap	B-tree pointing to rowid
SQLite	B+tree	B+tree

Key Page Header Fields (PostgreSQL)

Field	Purpose
pd_lsn	Last WAL record
pd_lower	End of item identifiers
pd_upper	Start of tuple data
pd_special	Start of special space
pd_prune_xid	Oldest unpruned XMAX

Key Tuple Header Fields (PostgreSQL)

Field	Purpose
t_xmin	Inserting transaction
t_xmax	Deleting transaction
t_ctid	Current or newer tuple version
t_infomask	Nulls, OID, HOT flags
t_hoff	Offset to user data

---

Best Practices

✅ Do This:

// Choose the engine for the workload
InnoDB: OLTP, transactions, row-level locking
MyISAM: read-only or insert-only, table-level locking
PostgreSQL: OLTP and analytics, MVCC, extensible
SQL Server: OLTP, columnstore for analytics
SQLite: embedded, single-file, low concurrency

// Tune free space for updates
PostgreSQL: lower fillfactor for update-heavy tables
Oracle: higher PCTFREE for tables with growing rows
InnoDB: monitor page splits and free space

❌ Don’t Do This:

// Use MyISAM for transactional workloads
// No crash recovery, table-level locking

// Ignore page overhead when sizing
// A 16 KB InnoDB page holds fewer rows than you think

// Assume the heap is a simple array
// PostgreSQL's MVCC means multiple versions per row

---

Common Pitfalls

Pitfall	Why It Happens	Fix
Table bloat in PostgreSQL	Dead tuples not vacuumed	Autovacuum or manual vacuum
Row migration in Oracle	PCTFREE too low	Increase PCTFREE
Page splits in InnoDB	Random primary key inserts	Use auto-increment or UUID v7
SQL Server row overflow	Row exceeds 8 KB	Move large columns to separate table
SQLite page size mismatch	Changed after creation	Set page size at database creation

---

Real-World Examples

1. InnoDB B+tree

Table data is in the primary key B+tree
Secondary index points to the primary key value

2. PostgreSQL heap

Rows are in heap pages
Indexes point to ctid (page, item_id)

3. SQL Server page header

96-byte header
Row-offset table at the end of the page

4. Oracle PCTFREE

CREATE TABLE t (n NUMBER) PCTFREE 20;

5. SQLite page size

Page size stored in the database header
2 bytes at offset 16

6. PostgreSQL HOT update

New tuple on same page
t_ctid links old to new
No new index entry

7. InnoDB page split

Insert into full leaf page
B+tree splits the page
Half the rows move to a new page

8. SQL Server extent

8 contiguous pages = 64 KB
Uniform or mixed extents

9. Oracle row migration

Row grows beyond block space
Moved to new block
Original row piece points to new block

10. PostgreSQL fillfactor

CREATE TABLE t (...) WITH (fillfactor = 70);

---

Visual

InnoDB B+tree

┌──────────────────────────────────────────────┐
│  Primary Key B+tree                          │
│         │                                    │
│         ▼                                    │
│  ┌────────────────────────────────────────┐  │
│  │ Root page                              │  │
│  │  ├── key < 50 → leaf page A            │  │
│  │  └── key ≥ 50 → leaf page B            │  │
│  └────────────────────────────────────────┘  │
│         │                                    │
│         ▼                                    │
│  ┌────────────────────────────────────────┐  │
│  │ Leaf page A (16 KB)                    │  │
│  │  row 1, row 2, row 3, ...              │  │
│  └────────────────────────────────────────┘  │
│                                              │
│  Secondary index: separate B+tree            │
│  Leaf entry: (secondary_key, primary_key)   │
└──────────────────────────────────────────────┘

PostgreSQL Heap Page

┌──────────────────────────────────────────────┐
│  PageHeaderData (24 bytes)                   │
│  pd_lower ─────────────────────┐             │
│  ┌──────┬──────┬──────┐        │             │
│  │ItemId│ItemId│ItemId│        │             │
│  │  1   │  2   │  3   │        │             │
│  └──┬───┴──┬───┴──┬───┘        │             │
│     │      │      │            │             │
│     ▼      ▼      ▼            ▼             │
│  ┌────────────────────────────────────────┐  │
│  │ tuple 3 (live)                         │  │
│  │ tuple 2 (dead)                         │  │
│  │ tuple 1 (dead)                         │  │
│  └────────────────────────────────────────┘  │
│  pd_upper ─────────────────────┘             │
│  free space                                  │
│  special space                               │
└──────────────────────────────────────────────┘

SQL Server Page

┌──────────────────────────────────────────────┐
│  Page header (96 bytes)                      │
│         │                                    │
│         ▼                                    │
│  Row data (serially after header)            │
│  ┌────────────────────────────────────────┐  │
│  │ row 1                                  │  │
│  │ row 2                                  │  │
│  │ row 3                                  │  │
│  └────────────────────────────────────────┘  │
│         │                                    │
│         ▼                                    │
│  Row-offset table (at the end of the page)   │
│  ┌──────┬──────┬──────┐                      │
│  │ off3 │ off2 │ off1 │                      │
│  └──────┴──────┴──────┘                      │
└──────────────────────────────────────────────┘

Oracle Block

┌──────────────────────────────────────────────┐
│  Block header (transaction entries)          │
│  Table directory                             │
│  Row directory                               │
│         │                                    │
│         ▼                                    │
│  ┌────────────────────────────────────────┐  │
│  │ free space (PCTFREE)                   │  │
│  ├────────────────────────────────────────┤  │
│  │ row data                               │  │
│  │ row 1, row 2, row 3, ...               │  │
│  └────────────────────────────────────────┘  │
└──────────────────────────────────────────────┘

---

Summary

Item	Value
InnoDB	B+tree storage, 16 KB pages, clustered index
PostgreSQL	Heap storage, 8 KB pages, ctid pointers, HOT
SQL Server	Heap or clustered, 8 KB pages, 96-byte header
Oracle	Heap, variable block size, PCTFREE, row migration
SQLite	B+tree, variable page size, free-list
Page header	Metadata for free space and checksums
Tuple header	MVCC control (xmin, xmax, ctid)
Free space	Reserved for updates (fillfactor, PCTFREE)

Key takeaways:

• The storage engine determines the physical layout. InnoDB stores table data in the primary key B+tree; PostgreSQL uses a heap with separate indexes; SQL Server uses a heap or a clustered index; Oracle uses a heap with PCTFREE-managed free space; SQLite uses a B+tree with variable-size pages .
• The page is the unit of I/O. Every read and write operates on a page. The page header contains the metadata that makes the page self-describing, and the tuple header contains the MVCC information that makes concurrent access possible.
• Free space management determines update behavior. A page with no free space forces a row to migrate (Oracle), a new tuple to go to a different page (PostgreSQL), or a B+tree page to split (InnoDB). The fillfactor and PCTFREE settings reserve space to avoid these costs.
• HOT updates are PostgreSQL’s optimization for non-indexed updates. When an update does not change an indexed column and fits on the same page, no new index entry is created, and the old tuple can be pruned without a vacuum .
• The clustered index avoids the indirection for primary-key lookups. InnoDB’s primary B+tree contains the rows, so a primary-key lookup goes directly to the row. A secondary-index lookup must traverse the secondary tree to find the primary key, then the primary tree to find the row.
• SQL Server’s row-offset table is the indirection for heap tables. The table at the end of the page records the offset of each row, and the index entry points to the row’s position in the table.

Remember: The storage engine is not a black box. It is a set of decisions about how rows are laid out in pages, how indexes point to rows, and how free space is managed. InnoDB puts the table in the primary B+tree. PostgreSQL puts it in a heap and uses ctid to point from indexes to tuples. SQL Server uses a 96-byte page header and a row-offset table. Oracle uses PCTFREE to reserve space for updates and migrates rows that outgrow their block. SQLite uses a B+tree with variable-size pages and a free-list. The page layout determines the overhead, the maximum row density, and the update behavior. The engine choice determines whether a query is a direct B+tree seek or an index-to-heap indirection, and whether a write locks a row or a table. Understanding both is understanding the physical cost of every query.

---

---

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!