Understanding Database Internals

Modern databases are complex systems that optimize for speed, efficiency, and reliability. To truly understand how they work and write better queries, you need to know how data is stored and accessed under the hood.

This article covers:

• How tables and indexes are physically stored on disk
• How data is read and written using fixed-size pages
• Why I/O operations are critical to query performance
• Key internal concepts like: row_id, Pages, Heaps, and Indexes
• The difference between row-based and column-based storage models

You’ll understand the physical structures behind your database engine and how to leverage them for better performance and system design.

How are Tables and Indexes stored?

When you run a query, you’re not just reading a few rows. The database interacts with the disk using fixed-size pages and relies on data structures like heaps and B-trees to locate and return the results.

At a high level, tables are collections of rows, but under the hood, it’s all just bytes. Although different databases manage this differently but the concept remains the same.

Whether you’re working with relational rows or JSON-like documents, the underlying storage engine simply sees data as structured bits and bytes. The abstraction of a “row” is logical — what actually matters is how it’s laid out in memory and on disk.

What is a Row ID?

Most modern databases assign an internal identifier to each row called a row ID (or tuple_id in PostgreSQL). This ID uniquely identifies a row within a table and is crucial for efficient lookups, especially for index management and joins.

• In PostgreSQL, this is a hidden system column.
• In MySQL with InnoDB, it might coincide with the primary key.

Table with internal row id column

These row IDs are often used internally in indexes and during query execution, but are abstracted away from end users.

Pages: The Unit of I/O in Databases

Databases don’t read or write data at the row level — instead, they operate on pages, which are fixed-size blocks of bytes (typically 8KB in PostgreSQL or 16KB in MySQL). A page is the smallest unit of I/O for the storage engine.

Each page can hold multiple rows, depending on how wide those rows are — that is, how many columns they have and the size of each column’s data type. These structured rows are stored as raw bytes on disk, and every page has a defined physical start and end boundary.

When a query runs, the database loads entire pages into memory, not just individual rows. So even if you request a single row, the system must fetch the full page that contains it, along with other rows on that page. This has important performance implications: the fewer pages you need to touch, the fewer I/O operations are required.

For example, if each page holds 3 rows, then a table with 1,001 rows would span approximately 334 pages.

I/O: The Hidden Cost of Every Query

An I/O (Input/Output) operation refers to reading from or writing to disk — a process that is often the slowest part of query execution. Since databases interact with disk in page-sized chunks, every I/O operation involves pulling in full pages, not individual rows.

This means when you query for a single row, you’re paying the cost of reading an entire page. Even though the row you need might be just a few bytes, you’re fetching several kilobytes from disk. That cost scales with the number of pages touched.

The fewer pages a query needs to access, the fewer I/O operations it triggers — and the faster it runs.

Not all I/O is equal. Some I/Os hit the operating system’s page cache (especially in databases like PostgreSQL), while others go all the way to disk. Factors influencing I/O performance include:

• Whether storage is SSD or HDD
• Disk partitioning and layout
• OS-level memory management and caching
• How efficiently the database buffer pool is used

Understanding I/O helps you think in terms of query cost, not just query logic. It’s the bridge between how you write a query and how the engine physically retrieves your data.

Heap: Where the Raw Table Data Lives

A heap is the fundamental data structure where a table’s actual data is stored on disk. Think of it as a sequential collection of pages — each one holding multiple rows of the table — stacked one after another without any inherent order.

This is where everything lives: all rows, all columns, across all pages. The heap doesn’t sort or organize your data in any optimized way. It just stores rows as they come in.

Querying directly from the heap is expensive. If you’re searching for a specific row, the database might have to scan many pages until it finds the one containing the row you want. Since it can’t jump straight to the row, it has to load full pages into memory and check each row within those pages.

This is why indexes exist — to avoid blindly scanning the heap.

An index helps the database locate exactly which page(s) to read from the heap. For example, you might be able to use an index to determine that a row is located on page 333. While you still have to read the full page (not just the row), at least you’re not scanning hundreds of pages to find it.

In short:

• The heap stores all your table’s raw data as pages.
• It’s unordered and unsorted by default.
• Without indexes, queries must traverse the heap, which is slow.
• Indexes act like a map, pointing to the exact pages in the heap where relevant data lives.

Indexes: Fast Paths to Data

An index is a separate data structure that helps the database locate rows in a table quickly, without scanning the entire heap. Instead of storing full rows, an index holds a subset of columns along with pointers to the corresponding rows in the heap.

You can create indexes on one or more columns. When a query uses an index, the database first searches the index for matching values and then uses the pointers to fetch the corresponding pages from the heap. This avoids the cost of scanning every page in the table.

Indexes are also stored as pages, so using them still incurs I/O. However, because indexes are often smaller than the full dataset, more of them can fit into memory, making lookups significantly faster.

The most common data structure for indexing is the B-tree, which allows for fast range queries and efficient lookups.

Assume each page holds 3 rows:

• Page 0: rows 1, 2, 3
• Page 1: rows 4, 5, 6
• Page 2: rows 7, 8, 9

Without an index, searching for emp_id = 3 would require scanning pages one by one until the row is found—an expensive I/O operation.

With an index on the emp_id column, the database searches the index pages for emp_id = 3. Once found, the index provides the exact page number in the heap where the row lives. The heap page is then loaded into memory, and the row is filtered out. This significantly reduces the amount of data read from disk, especially in large tables.

Notes on Index Internals

Some databases support clustered indexes (or index-organized tables) where the heap is physically ordered based on the index. The primary key is often used as the clustered index unless specified otherwise.

MySQL InnoDB always requires a primary key, and all other indexes point to the primary key’s value. If that value is something like a UUID, which is random, writes become inefficient because new rows are scattered across pages, causing frequent page splits and high I/O.

In contrast, PostgreSQL uses only secondary indexes, which point directly to the internal row_id (also called tuple_id). All updates to a row in PostgreSQL require updates to every index that includes that row, making index maintenance more costly.

Row-Based vs Column-Based Databases

Databases generally store data on disk in one of two formats: row-oriented or column-oriented. These formats impact how data is read and written, and each comes with its own strengths and trade-offs. Choosing between them depends on your use case — whether you’re optimizing for transactions or analytics. PostgreSQL, MySQL, and most traditional relational databases are row-based by default.

Both formats internally include a hidden row_id to uniquely identify each row.

Some systems support hybrid storage engines, allowing you to define the storage format at the table level. Mixing row and column stores in joins is technically possible in some databases — but best avoided for performance and complexity reasons.

Let’s explore the differences using three example queries:

• SELECT first_name FROM emp WHERE ssn = 666
• SELECT * FROM emp WHERE id = 1
• SELECT SUM(salary) FROM emp

Row-Oriented Databases (Row Store)

In a row-based system, data is stored one full row at a time. When a page is read from disk, it includes complete rows, even if you only need one column. This makes them ideal for transactional workloads, where reading or writing entire rows is common.

Example of row based table where rows are stored contiguously on disk

SELECT first_name FROM emp WHERE ssn = 666: Requires scanning blocks row-by-row until a match is found. Once the row is loaded, all columns—including first_name—are already in memory.

SELECT * FROM emp WHERE id = 1: Similar to the above, once the matching row is found, no extra I/O is needed to retrieve the rest of the columns.

SELECT SUM(salary) FROM emp: Without an index, every row (and its associated page) must be scanned, even though only one column is needed. This makes aggregations expensive.

Rows are stored contiguously on disk, which improves performance for operations that access full rows.

Strengths of Row Stores:

• Great for OLTP workloads (transactions)
• Efficient for point lookups and updates
• Easy to write and append rows
• WAL (write-ahead log) is efficiently generated

Weaknesses:

• Poor compression
• Expensive aggregations
• Less efficient when querying only a few columns across many rows

Column-Oriented Databases (Column Store)

In a column-based system, data is stored by columns instead of rows. This structure is well-suited for analytical queries that need to read the same column across many rows, such as aggregations and filters.

Column table example where `row_id` is stored with each column value

Each value is associated with its row_id. When a row is inserted or updated, every column structure must be updated separately.

SELECT first_name FROM emp WHERE ssn = 666: The database scans only the ssn column until it finds a match. Using the row_id, it can then directly fetch the corresponding first_name.

SELECT * FROM emp WHERE id = 1: Finds the matching row_id in the id column, but must fetch each column separately. This is inefficient and incurs significant I/O overhead.

Get AkashSDas’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

SELECT SUM(salary) FROM emp: Its fast. Only the salary column is scanned, and many column stores can compress repetitive values, reducing I/O.

Columnar storage makes aggregations fast and storage compact, but at the cost of more complex writes and slower full-row access.

Strengths of Column Stores:

• Ideal for OLAP workloads (analytics)
• Excellent compression
• Fast for filtering and aggregation on large datasets

Weaknesses:

• Slow row inserts and updates
• Inefficient for frequent SELECT * queries
• Harder to manage joins involving many columns

Column stores are often used for analytical workloads (e.g., data warehouses), while row stores power transactional systems (e.g., web apps).

Primary Key vs Secondary Key

When data is stored in the heap, it’s essentially in an unordered structure. New rows are simply appended as they come — whether their keys are 7, 2, 3, 8, or anything else. There’s no intrinsic ordering in the heap; it’s just a collection of pages filled with raw, unstructured data.

To optimize access patterns, especially for range-based lookups, databases use keys — most importantly, primary keys and secondary indexes. These offer different performance characteristics and serve different use cases.

Choosing the right key structure is crucial:

• Use clustered/primary keys when you frequently do range queries or sequential access.
• Use secondary indexes to accelerate searches on other columns, but be mindful of the write and maintenance overhead.

Tip: Avoid random primary keys unless absolutely necessary — doing so reduces the effectiveness of clustering and hurts performance.

Primary Key & Clustered Index

When you define a primary key on a table, you’re introducing clustering. Clustering means the table itself is physically organized around the key. The rows are no longer inserted in arbitrary order — they must follow the order of the primary key.

This has a few implications:

• The heap is now sorted based on the primary key.
• Inserting a row requires maintaining that order — meaning more complex inserts and potentially reserving space for future values to reduce fragmentation. For example, if you insert rows with PKs 1 and 2, and later insert 8, space might need to be managed for values between 3 and 7 to preserve ordering.
• This layout enables highly efficient range queries, since related rows are physically adjacent and can be fetched in fewer I/O operations.

Different databases use different terms:

• In PostgreSQL, this is referred to as a clustered index.
• In Oracle, it’s called an Index Organized Table (IOT).
• In MySQL (InnoDB), the primary key is always clustered, and all secondary indexes point to this primary key.

Clustering makes range queries fast:

SELECT * FROM emp WHERE id BETWEEN 5 AND 15;

This can often be resolved with a single page or a small set of sequential reads, thanks to the physical ordering.

Caveat: Using randomized primary keys like UUIDs can significantly hurt performance. Since the heap is organized by the PK, inserting random keys leads to page splits, fragmentation, and cache misses, as the data is scattered across multiple pages.

Secondary Key & Secondary Index

A secondary key (or secondary index) is a separate data structure — usually a B-Tree or another index format — that maintains order on a particular column independent of the heap.

Key characteristics:

• The heap remains unordered.
• The secondary index is stored as its own set of pages and points to rows in the heap via pointers like row_id or primary key references.
• A query using a secondary index first searches through the index, retrieves the page reference (e.g., heap page 133), and then fetches the actual data from the heap.

This introduces two I/O hits per lookup:

1. One to read the index.
2. Another to fetch the corresponding row from the heap.

Secondary indexes improve lookup performance on non-primary columns but add overhead during writes and updates, as both the heap and index must be maintained.

Database Pages

Databases are ultimately just sophisticated systems for organizing and managing bytes on disk. To do this efficiently, they rely on fixed-size units called pages. Whether you’re dealing with tables, indexes, sequences, or documents, they all eventually get stored as bytes inside these pages.

This design decouples the storage engine from the database’s frontend (SQL parser, APIs, etc.), allowing a consistent and optimized mechanism for reading, writing, and caching data.

Pages: A Shared Unit of Read and Write

Databases read and write in pages, not individual rows or bytes. When you query a row:

1. The DB engine determines the page containing the row.
2. It computes the file and offset on disk.
3. The OS checks its filesystem cache; if the page isn’t cached, it reads it from disk into memory.

Most databases maintain a buffer pool (or shared pool) in memory. Pages read from disk are cached here. This way, subsequent reads for rows on the same page avoid another disk I/O.

For writes:

1. When a user updates a row, the database pulls the entire page into the buffer pool.
2. The row is updated in memory.
3. A journal entry (called a WAL) is persisted for durability.
4. The page may remain in memory to accumulate more changes before being flushed back to disk.

Inserts and deletes follow similar principles, though the specifics vary by engine.

Efficiency tip: The smaller the rows, the more of them fit in a single page, which makes reads cheaper. This is especially beneficial for index range scans and bulk reads.

What Goes Into a Page?

The actual data stored in a page depends on the database model.

1. Row-Store Databases: It store rows sequentially and Optimized for OLTP workloads (frequent small writes). Examples: PostgreSQL, MySQL (InnoDB), Oracle.
2. Column-Store Databases: It stores data column by column, so a page is packed with values from a single column. It’s ideal for OLAP workloads — analytical queries over large data sets. Great for aggregate functions like SUM() and AVG().
3. Document and Graph Databases: They compress and store entire documents or graph structures inside pages. Page layout is tuned for graph traversal patterns (depth-first, breadth-first, etc.).

Regardless of the model, the goal remains the same: maximize the usefulness of each page read. If your workload triggers many page reads for small bits of data, you likely need to rethink your data modeling.

Small vs Large Pages

Small pages offer fast I/O performance, especially when their size aligns closely with the underlying media’s block size. However, they come with higher overhead due to the larger proportion of metadata relative to useful data, and managing a greater number of pages can increase complexity.

On the other hand, large pages reduce metadata overhead and minimize the frequency of page splits, but they can result in slower cold reads and are often inefficient when accessing small amounts of data.

Some default page sizes:

• PostgreSQL: 8KB
• MySQL (InnoDB): 16KB
• MongoDB (WiredTiger): 32KB
• SQL Server: 8KB
• Oracle: 8KB

These defaults generally work well, but tuning page size can be crucial for specific workloads.

Cutting-edge storage tech like NVMe’s Zoned Namespaces or key-value interfaces add even more depth to the page optimization game.

How Pages Are Stored on Disk

One common approach is to store a table or collection as a file that’s just an array of fixed-size pages.

Example: Page 0, followed by Page 1, followed by Page 2, etc. To read page X: File offset = X * PAGE_SIZE and Length = PAGE_SIZE.

Example: Reading pages 2 to 9 of the table test with an 8KB page size: Offset = 2 * 8192 = 16384 and Length = 8 * 8192 = 65536 bytes

This design makes the page reads simple and efficient — just a file name, offset, and length.

PostgreSQL Page Layout (8KB)

In PostgreSQL, each data page follows a well-defined internal structure, designed to balance performance, flexibility, and efficient use of space. At a high level, every page is 8KB in size and contains several key components that work together to store and manage data efficiently.

Page header (24 bytes): At the very beginning of each page is a fixed 24-byte header. This section stores critical metadata about the page itself, such as its status, how much free space remains, and pointers to other structures. It’s essential for the database engine to manage reads, writes, and page-level operations effectively.

ItemIds (4 bytes each): Following the page header is an array of ItemIds, which serve as pointers to the actual data tuples (rows) stored within the page. Each ItemId entry contains the offset and length of the corresponding tuple. One of the powerful optimizations this design enables is HOT (Heap-Only Tuple). When a row is updated and the new version still fits within the same page, the original ItemId can be redirected to point to the updated tuple. This avoids the need to update indexes, improving performance for frequent updates.

Criticism: Although efficient in function, each ItemId is 4 bytes. For a page containing 1,000 small rows, nearly half the page (4KB) could be consumed just by pointers, which is a significant overhead in space-constrained scenarios.

Items (Tuples): This is the section where the actual row data — the tuples — are stored. Tuples are packed sequentially within the page and contain all column data for a specific version of a row. Because PostgreSQL supports MVCC (Multi-Version Concurrency Control), it’s common for multiple versions (tuples) of a single logical row to exist simultaneously.

Special Space: At the end of the page is a special area, which is mainly used for index pages such as B+Tree leaf nodes. This space contains information like forward and backward links to other index pages, allowing for fast traversal and efficient tree operations.

Tuple vs Item vs Row — What’s the Difference?

• Row: The logical representation a user sees when querying the database (e.g., a row in a table).
• Tuple: The physical version of a row stored on disk. A single row may have multiple tuples if it has been updated multiple times.
• Item: The internal pointer (an ItemId) that references a tuple within the page.