Physical Layer
The way data is organized at the physical layer shapes the entire database workflow.
Page
A page is a fixed-size container (typically a few kilobytes; for example, PostgreSQL uses 8kB pages by default) that holds multiple data entries, which may be either rows or index records.
A page generally consists of three parts: the Header, Tuples, and a Line Pointer Array (LPA).
Header
The header primarily stores metadata used for data integrity, recovery, and other management purposes. For now, we don’t need to worry about its details.
Tuple
The actual data resides in the Tuples section as sequentially packed records.
We call them tuples rather than records because tuples are immutable. To update a tuple, the database creates a new version that effectively supersedes the previous one.
For example, the third tuple is an updated version of the first.
There are two main reasons for this immutability:
A new tuple may be larger or smaller than the existing one (for example, because of a resizable TEXT field). If we updated it in place, subsequent tuples might need to shift to accommodate the size change, similar to inserting or deleting an element in an array, which can be costly.
It supports Multi-version Concurrency Control (MVCC), which allows transactions to access different versions of the same data concurrently. We’ll explore this in more detail in the Concurrency Control topic.
Line Pointer Array (LPA)
Between the header and the tuple data lies the Line Pointer Array (LPA), which contains fixed-size pointers to the actual tuples on the page. Each pointer can also track the state of its tuple, such as Updated or Deleted.
Because tuple sizes can vary, primarily due to fields such as text, using fixed-size pointers in the Line Pointer Array (LPA) enables fast, random access to any specific tuple.
Retrieving a pointer in this way is similar to accessing an element in an array:
pointer[i] = page_address + pointer_size * (i - 1)The primary purpose of the LPA is to keep tuple references stable. Even if a row is relocated among the tuples within a page, its corresponding line pointer remains unchanged, ensuring consistent references.
Heap
A heap is simply a collection of pages representing a table. The term heap essentially means no particular structure.
When inserting a record into a heap, the database looks for an available slot in an available page.
For example:
Tuple ID (TID)
External elements, such as other tables or indexes, reference tuples using a Tuple ID (TID). A TID is a composite identifier consisting of (page number, LPA index).
Because pages have a fixed size, they support efficient random access.
For example, to retrieve the tuple at TID (page = 2, index = 1),
the database can jump directly to it:
Heap.Pages[2].LPA[1] -> Tuple.
Heap Search
However, a heap isn’t particularly useful for searching. There are two practical ways to access a tuple in a heap:
- Using its TID.
- Scanning the entire heap, also known as a full table scan. 🥲
Index
Unstructured heaps aren’t ideal for fast tuple lookups. This is where an Index comes to the rescue.
In short, an index is an auxiliary data structure built alongside a table to enable efficient data retrieval.
Unlike tables, indexes are organized using specific data structures designed for fast lookups. In this section, we’ll focus on the most commonly used type: the B-Tree Index.
B-Tree Index
A B-Tree is an advanced form of a Binary Search Tree. Instead of storing a single key per node like a binary tree, it stores multiple keys in each node, increasing the branching factor and reducing the overall height of the tree.
For example, a B-Tree might store up to five elements per node. Each node can contain either actual values or pointers to child nodes.
In SQL , an index page corresponds to a B-Tree node. Each page can point either to child index pages or to actual table records through their TIDs.
A lookup traverses this structure starting from the root page, moving down through child pages until it locates the desired tuple.
Notably, indexes introduce a trade-off between read and write performance.
To maintain a B-Tree’s self-balancing structure, operations such as inserts, deletes, and updates may trigger node splits or merges. This maintenance overhead enables efficient reads but comes at the cost of slower writes, especially for tables with multiple indexes, where each change may require corresponding updates to several index structures.
HOT Update
Because tuples are immutable, an update creates a new tuple. However, we don’t necessarily need to update every associated index for every change.
An update can be treated as a HOT (Heap-Only Tuple) update and avoid index manipulation if:
- The update doesn’t modify indexed columns.
- The new tuple remains on the same page as the original tuple.
Tuple Chaining
When multiple versions of a tuple reside on the same page, they can be chained together. Each tuple carries metadata, such as its transaction state and a pointer to the next version. This chain allows queries to resolve the correct visible version of a tuple.
For example, an obsolete tuple may contain a pointer to the next valid tuple, allowing the database to traverse the chain and retrieve the latest applicable version. As a result, external index entries that hold the original TID don’t need to be updated.
Vacuum Process
As old tuple versions become obsolete, meaning they are no longer visible to any active transaction, their space can be reclaimed. The remaining tuples may also be rearranged during this process. This is called the Vacuum Process.
To perform vacuuming, the database needs to track two things: active transactions and the oldest transaction associated with each tuple.
For example, suppose the database determines that the first two tuples are no longer associated with any active transaction. Their space can then be reclaimed, and the line pointer can be updated to reference the latest valid tuple.
Vacuuming is critical to database maintenance because long-running transactions can keep old tuple versions visible, preventing their space from being reclaimed.
Secondary vs Clustered Index
So far, we’ve assumed that records are stored in an unordered heap and that indexes exist separately from the table data. These are known as Secondary Indexes.
However, in some database engines, such as MySQL InnoDB, table data is physically organized according to the primary key. This structure is known as a Clustered Index.
Queries using the primary key can therefore access the table data directly, without requiring a separate secondary index for those lookups.