Course contents
On this page
Physical representation — extended reference
Original detailed coverage and citations accompanying the focused physical representation lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 2: Representing and locating data
Prerequisites: Lesson 07 and the preceding foundations.
Learning outcomes
- Lay out records and slot directories on a fixed-size page and compute usable capacity.
- Trace record insertion, movement, deletion, and fragmentation without breaking logical identity.
- Compare row and column layouts through the bytes and operations a workload actually needs.
Stable identity over moving bytes
A record’s display name grows from eight bytes to eighty. Its current page has enough total free space, but no contiguous region large enough for the enlarged record. Moving bytes within the page could create room. However, an index or another structure may already refer to the record’s location. A storage engine needs a way to reorganize physical bytes without casually invalidating every reference.
Physical representation turns logical values into a durable, versioned format. It defines records, pages, identifiers, free space, and the rules for interpreting bytes after a restart or software upgrade. A format that is convenient for a single process can become unsafe when input is corrupted, partially written, or produced by an older version.
Records need more than field payloads
A record may contain a header, null bitmap, fixed-width fields, offsets to variable-width fields, and transaction metadata. Alignment can introduce padding. Variable-length strings need lengths or offsets so the reader can find the next value. A null value must be distinguishable from an empty string or zero.
Suppose a logical record has an 8-byte identifier, an 8-byte owner, a 4-byte kind code, and a name averaging 20 bytes. The logical payload is 40 bytes. If the format adds 12 bytes of header and offsets and rounds the result to a convenient alignment, actual storage can exceed 52 bytes. The exact layout is an engine choice; the calculation illustrates why multiplying logical field widths alone underestimates memory and disk needs.
Serialization must also define byte order and compatibility. A native in-memory structure may contain pointers, padding, and platform-specific sizes that cannot be written directly as a portable record. Persistent references need stable identifiers or offsets with validated bounds, not process addresses that become meaningless after restart.
Slotted pages separate references from placement
A slotted page usually contains a page header, an array of slot entries, free space, and record bodies. A slot identifies a record’s current offset and length. A reference can use page identity plus slot identity, allowing the engine to move the record body within the page while retaining the slot.
+-------------------+
| page header |
| slot 0 -> offset |
| slot 1 -> offset |
| ... |
| contiguous free |
| ... |
| record bodies |
+-------------------+The schematic shows the separation of indirection from payload. It does not prescribe one actual engine’s byte layout. PostgreSQL and SQLite publish concrete page and file formats that make useful implementation references.
For an illustrative 8,192-byte page, a 24-byte header leaves 8,168 bytes. If every row plus slot consumes 104 bytes, floor(8168/104) = 78 rows fit. They consume 8,112 bytes, leaving 56 bytes. This calculation assumes fixed row size, no other metadata, and no reserved free space. A production estimate must include actual alignment, versioning, and occupancy policy.
A slot’s reuse also needs rules. If a deleted record’s slot is reused, an old external reference must not silently identify an unrelated new record. Some designs avoid exposing such references beyond controlled contexts; others include generations or validate identity. Stable addressing is a lifetime and correctness problem, not just an offset calculation.
Heap files and clustered organization
A heap stores records without a global key order in its primary placement. Inserts find suitable free space, often using metadata about page availability. A secondary index maps search keys to record locations or logical identifiers. The heap can make insertion flexible while a lookup may require an index traversal followed by a separate page access.
A clustered organization places records according to a key order or makes the primary search structure carry records. This can benefit range access and nearby-key reads. Updating the clustering key or inserting into a crowded range may require more structural work. Secondary indexes may store the clustering key rather than a fixed physical pointer, changing their size and lookup path.
Neither organization eliminates fragmentation. Deletes create holes, updates change sizes, and versions retain old data. Reorganization can reclaim space but consumes I/O and must coordinate with readers. An engine must define whether free space is available immediately, only after old snapshots finish, or after a maintenance pass.
Large values and overflow storage
A value larger than the convenient inline size may be stored outside the main record. The record then contains a reference to overflow pages or another object. This preserves useful density for common small fields but makes fetching the large value a separate access path.
Projection matters here. A query asking only for an identifier should ideally avoid loading a large document body. Physical separation can make that possible. A query that always needs the full object may instead pay pointer chasing and additional I/O. Compression can alter the threshold, but decompression and update costs remain.
Ownership of overflow data is especially important during updates and crashes. The engine cannot free old overflow pages while a visible version still references them. It also must not expose a committed record whose new overflow object was never made recoverable. Allocation metadata, logging, and version visibility must agree on the object’s lifetime.
Row and column layouts
A row-oriented layout groups fields from the same record. It often benefits operations that fetch or update several attributes of one entity. A column-oriented layout groups values of the same attribute across many records. It can benefit scans that touch a subset of columns and exploit similar values for compression and vectorized processing.
With 100 equally sized columns, a query using three columns needs 3% of the uncompressed column payload if it can avoid reading the other 97. This is an illustrative upper-level byte comparison, not a prediction of exact speedup. Metadata, filtering, compression, storage granularity, and CPU work affect actual execution.
Updates introduce a different cost. Changing a few fields may touch separate column structures or create new versions that later merge. Reconstructing a full row may combine values from several locations. Hybrid layouts and late materialization attempt to balance these costs. They are most effective when their physical assumptions match the query mix.
Encoding and compression
Encoding changes representation using properties of the data. Dictionary encoding replaces repeated values with identifiers. Run-length encoding represents repeated sequences compactly. Delta encoding stores differences between related values. Bit packing uses only the necessary bits for a bounded range. General-purpose compression finds repeated patterns without the same semantic understanding.
An encoding should account for access behavior. A compact compressed block can reduce I/O but require decompression before a single value is available. An indexed dictionary can make filtering cheap, while maintaining dictionaries under concurrent updates adds work. A smaller representation may improve CPU cache use enough to offset decoding cost, or decoding may dominate a tiny hot lookup.
Format boundaries must remain explicit. A block header can identify encoding, value count, uncompressed size, and checksum. Decoders validate these before trusting offsets or allocating output. Corruption must produce a controlled error rather than an out-of-bounds read. Compression efficiency never justifies removing bounds checks at an untrusted storage boundary.
Fragmentation and free-space accounting
Internal fragmentation is unused space inside an allocated unit. External fragmentation occurs when free regions exist but do not form a suitable contiguous allocation. A page can have enough total free bytes yet require compaction to fit a new record. A file can contain reusable pages while still occupying its previous filesystem size.
A free-space map summarizes where inserts may fit. The summary can be approximate if the insert path rechecks the actual page under appropriate protection. Exact global free-space tracking can become a synchronization hotspot. An approximate hint with safe validation often gives a better balance of concurrency and correctness.
Reserved free space can reduce future splits or row movement. Lower occupancy consumes more pages now but may save update work later. A nearly static analytical dataset and a frequently updated variable-length transactional dataset should not automatically use the same occupancy policy. The choice trades space for future mutation cost.
Format evolution and durability
A persistent format needs a version and a strategy for compatible changes. Adding a field to a logical schema does not necessarily require rewriting every record immediately if the reader can interpret an older representation with a default. But such flexibility requires explicit interpretation rules and must remain compatible with indexes, logs, and replication.
A checksum can detect some corruption but cannot reconstruct lost bytes on its own. A page identifier and version can help detect misdirected writes or stale data. Recovery mechanisms need enough information to determine whether a page is complete and whether logged changes have already been applied. The physical format and the log protocol must be designed together.
A partially written page is a crash-recovery concern even when individual application fields are small. Storage atomicity assumptions depend on devices and filesystems. An engine may use page images, doublewrite-like protection, or other techniques to make recovery possible. Lesson 24 develops the failure sequence; here the important point is that a record layout cannot assume every page write is indivisible without evidence.
Walk through a variable-length update
Consider a constructed page holding three records. Slot 0 points to a 40-byte record near the page end, slot 1 to a 60-byte record, and slot 2 to a 50-byte record. A name update grows slot 1’s body to 110 bytes. The engine cannot simply overwrite the extra fifty bytes if they belong to another record. It first determines whether the update policy permits in-place replacement, relocation within the page, or creation of a new record version.
If relocation is permitted and sufficient space exists, the engine can allocate a new 110-byte region, write the new body, and publish the slot’s new offset under structural protection. Readers must not observe a new length with an old offset or a half-written body. The update’s transactional visibility and crash recoverability require additional mechanisms developed later. Page latching protects the physical structure; it does not independently provide an application transaction.
If the page lacks space, the engine may place the new version elsewhere and update an appropriate reference chain. This creates another access and leaves the old version until no required reader can see it. The logical row remains one entity while several physical representations coexist. Consequently, “update one row” is not a reliable statement of bytes written or space retained.
A checked record decoder
Persistent files should be treated as input that can be incomplete or corrupted. A conceptual decoder can validate structure before constructing field references:
decode_record(page, slot):
require slot_id_is_in_range(slot)
offset, length = read_slot(slot)
require offset <= page.size
require length <= page.size - offset
require length >= minimum_record_header
record = page[offset : offset + length]
header = validate_supported_format(record)
require header.field_count <= format_limit
validate_monotone_offsets_within_record(header)
return checked_field_views(record, header)The subtraction check avoids an overflow-prone assumption that offset + length fits the integer type. An offset table must not point backward into a header or past the record. A field decoder must also validate its own representation, such as an encoded string length or dictionary identifier. Returning views into page memory introduces a lifetime requirement: the page cannot be evicted or rewritten incompatibly while a consumer retains the view.
Format checks do not establish that the data is semantically current. A structurally valid page can belong to an older generation, a different file, or an uncommitted update. Page identifiers, checksums, log positions, and visibility metadata address different questions. A safe engine layers these checks rather than assuming one checksum proves every property.
Page occupancy has a measurable cost
Using the earlier 8,192-byte page and 104-byte row-plus-slot assumption, a maximally filled page holds 78 rows. If a policy aims for 80% of the 8,168-byte usable area, the initial row target becomes floor(0.8 × 8168 / 104) = 62. For one million rows, the ideal initial page counts are approximately 12,821 and 16,130 respectively, ignoring uneven placement and extra structures.
The lower-fill layout uses about 26% more pages initially: 16130 / 12821 - 1. In exchange, each page has more room for growth or nearby inserts before another allocation or split becomes necessary. Whether that pays off depends on mutation size and distribution. A static archive gains little from reserving space that will never be used. A frequently growing record can benefit substantially.
The page size itself trades concerns. Larger pages can increase index fanout and improve large sequential transfers, while small random requests may fetch more unused bytes. Smaller pages can reduce that overfetch but increase metadata and tree levels. Compression blocks, filesystem allocation units, device behavior, and cache policies influence the result. There is no page size that follows automatically from “low latency.”
Encodings change both bytes and operations
Suppose a status column contains one million values drawn from eight states. A fixed 32-bit representation occupies 4,000,000 bytes. Three bits per value theoretically encode eight possibilities in 375,000 bytes, before dictionary and block metadata. This is a constructed payload comparison, not a claim about a particular engine’s exact representation. Decoding packed values adds bit operations but can reduce memory and I/O enough to improve the total path.
Now suppose the same values arrive in long repeated runs. Run-length encoding stores a value and a run length instead of each occurrence. It can be extremely compact for sorted or naturally clustered data and poor when every neighboring value differs. Sorting to improve compression costs work and can conflict with insertion order or another important key order. Compression design therefore connects directly to clustering and query execution.
A dictionary can map strings to compact codes. Filtering equality on a known code may avoid reconstructing each string. However, codes in independently encoded blocks need not have global ordering or identity. Code 7 in one block can mean a different string from code 7 in another. Joins and comparisons must respect dictionary scope or translate values. Treating local codes as globally meaningful is a correctness error disguised as an optimization.
Column boundaries and late materialization
Imagine a table containing a small identifier, region code, amount, and a large description. A report filters by region and sums amount. In a columnar layout, execution can inspect region and amount without fetching description. If only 1% of rows qualify and descriptions are needed later, it can first produce matching row positions and fetch descriptions only for those positions. This is a form of late materialization: delay reconstructing full records until needed.
The optimization introduces a positional contract. Column fragments must agree on row identity despite deletion, compaction, and versioning. A selection vector identifying row 37 in one batch must not accidentally retrieve another entity’s description after reorganization. Stable row identifiers, consistent snapshots, and coordinated segment metadata provide possible solutions. The exact mechanism varies by engine.
Row-oriented layouts can achieve some similar savings through secondary indexes and out-of-line large fields. A covering index can answer selected columns without fetching the full row, subject to visibility checks. Conversely, a columnar engine receiving many tiny updates may buffer them in a row-oriented delta structure and merge later. Practical engines often combine layouts because workloads contain several access patterns.
Persistent references and reclaiming old space
A physical address is safe only within its stated lifetime. A page number plus slot number may identify a tuple version, not the application’s enduring row identity. After deletion and slot reuse, an old address might point to unrelated data. An index using that address must be maintained consistently, and long-lived external clients should usually use logical identifiers instead.
Allocation metadata needs crash-safe ordering too. If a page is marked reusable before every durable reference to it is removed, recovery can expose a reference to repurposed bytes. If it is never marked reusable after deletion, the engine leaks space. Logging and reclamation protocols must establish when a reference can no longer be observed by any allowed reader or recovery path.
A useful case connection is the limited role of slotted indirection in PostgreSQL’s documented format: an item identifier can remain in place while its tuple bytes move within a page. This supports local compaction but should not be interpreted as an immutable business identifier across all updates. PostgreSQL page layout
The constructed examples in this lesson show why physical storage is part of concurrency and recovery design. Every compact representation needs safe interpretation, every movable object needs a reference rule, and every reusable byte needs a lifetime boundary. The buffer management chapter adds the memory-residency boundary, where a correct address still cannot be used after its containing buffer frame has been recycled.
Deletion leaves several kinds of free space
Suppose the earlier page with 78 fixed-size rows deletes ten rows. At the logical level, those rows are gone for new reads. Under versioning, old snapshots may still need their bodies, so all 1,040 bytes of row-plus-slot space are not necessarily reusable yet. Once reclamation is permitted, the bodies can become holes. Compaction can combine holes into contiguous free space while preserving valid slot references.
The slot array has a separate policy. A freed slot might be reusable by a later insertion, remain as a redirect, or retain metadata until references are safe. The file may still occupy exactly the same number of pages after all ten deletions. Reusing free space for future rows and returning disk capacity to the filesystem are different operations with different costs.
A page-level free-space hint can advertise that an insertion might fit. The insertion must verify current space under appropriate protection because another writer may have consumed it. Keeping the hint approximate can reduce global synchronization. Incorrect optimism should cause a retry on another page, not an out-of-bounds write; incorrect pessimism should waste some opportunity, not hide committed data.
The same distinction matters in capacity reporting. Logical live bytes, allocated page bytes, reusable internal space, and filesystem size answer different questions. A database with 500 GB of live values in a 1 TB file may have valuable reusable space rather than an unexplained leak. Conversely, old versions retained by a stalled reader can keep that space unavailable. Interpreting growth requires following visibility and allocation lifetimes instead of comparing only one live-row count with one disk-size number.
A physical format should also state whether integers and offsets are unsigned, their maximum values, and which reserved values indicate absence. A negative length accidentally converted to a large unsigned allocation can turn corruption into resource exhaustion. Checks should occur before pointer construction or memory allocation. These details are part of a durable interface because a future reader must distinguish an unsupported format from damaged bytes without guessing. Format simplicity can reduce both decoding cost and the number of failure cases, provided it still represents required values and evolution rules explicitly.
Case connection and design conclusion
PostgreSQL’s published page layout and SQLite’s published file format show that mature engines make physical structure an explicit compatibility boundary. Their concrete formats differ. The general lesson is that offsets, slots, headers, and metadata are not incidental implementation details: they determine how records can move, how corruption is detected, and how old data remains readable.
A good physical design states what each identifier means, who owns each byte range, which updates can move data, and how readers validate a representation. The buffer management chapter introduces the buffer manager, which decides when these pages reside in memory and how they can be reused without violating their lifetimes or durability requirements.