Disk Blocks and File Organization
Imagine a database table with ten million customer records. Each has a name, address, and account balance. The operating system does not let a database read "one record" from disk. It can only read and write in fixed-size chunks called blocks or pages. Every design decision above this line rests on this fact. This includes indexing and query optimization. It ultimately depends on how records get packed into these blocks. It also depends on how blocks get organized into files. This gap exists between "what the application wants" (a record) and "what the hardware gives" (a block). It is one of the oldest and most consequential problems in database systems. Get it wrong, and a query that should touch one page ends up touching a hundred. Get it right, and a database can scan millions of rows efficiently. It uses a fraction of the I/O a naive scheme would need. The central engineering challenge is that records vary in size and structure. Blocks, however, are rigid and fixed. Records must also be inserted, deleted, and updated. This must happen without the whole file becoming corrupted or wastefully fragmented. This article builds the vocabulary and mechanics for that translation layer. It explains how fixed-length and variable-length records are represented in memory and on disk. It explains why naive packing schemes break under deletion. It also shows how the slotted-page structure solves the problem elegantly. It does this by separating a page's physical layout from the logical addresses. Other parts of the system use these addresses to refer to records. This machinery sits directly beneath topics like Heap Files, Sorted Files, and Buffer Management. All of these assume records live inside blocks organized exactly as described here. By the end, you should be able to compute how many records fit in a block. You should be able to design a record and page layout from scratch. You should be able to trace an insert/delete sequence through a slotted page. Finally, you should be able to explain why database systems almost never store variable-length records by "just concatenating bytes" the way a naive programmer might.
- Disks transfer data in fixed-size blocks (typically 4–16 KB); records must be packed into blocks, since I/O is block-granular, not record-granular.
- Fixed-length records are simple: record `i` sits at a computable offset, enabling O(1) direct access — but deletions leave gaps that must be actively managed.
- Variable-length records (with strings, nulls, repeating fields) cannot use fixed offsets; they need explicit length/offset metadata inside the record itself.
- The slotted-page structure stores records from one end of the page and a slot array (record directory) from the other, letting the page compact and grow toward each other.
- Slotted pages give records a stable logical address (page ID, slot number) even as the physical byte offset changes — critical for indexes and pointers that reference records.
- These layout techniques are the foundation beneath Heap Files, Sorted Files, and Buffer Management, which organize collections of blocks into full files and manage them in memory.
A database page must separate where bytes physically sit from how records are logically addressed, so records can move within a page without invalidating every pointer to them.
The idea
A block (or page) is the unit of transfer between disk and memory — a fixed number of bytes, commonly 4 KB, 8 KB, or 16 KB, chosen to match the granularity at which the storage device and operating system operate efficiently. This follows directly from the physical realities described in The Storage Hierarchy for Databases: seeking to a location on disk is expensive, but once positioned, reading a contiguous chunk is comparatively cheap, so systems amortize seek cost by moving whole blocks rather than individual bytes. A record is a logical unit of data — one row of a table, one tuple. Records are described by a record format, a schema-level layout specifying the type, order, and (for fixed-length fields) byte offset of each attribute. Records are fixed-length if every instance of a record type occupies exactly the same number of bytes (all fields have fixed-size types and no field is ever null in a way that changes physical size), and variable-length otherwise — typically because of variable-length strings (`VARCHAR`), optional/null fields, or repeating groups.
File organization is the strategy for arranging a collection of blocks (holding many records of one or more types) into a file on disk, together with the access methods used to locate records within it. The choice of file organization — heap, sorted, hashed — is a separate concern layered on top of block/record layout, and is addressed in Heap Files and Sorted Files; this article focuses one level down, on how records are packed within a single block and how that block is structured so records can be found, inserted, deleted, and updated efficiently.
How it works
Fixed-length records: packing and the deletion problem
If every record has a fixed size `R` bytes, and a block has `B` usable bytes, the natural strategy is to pack records contiguously: ``` record i occupies bytes [i R, i R + R) within the block ``` This gives O(1) direct access: to find record `i`, compute `i R` and read `R` bytes — no scanning required. The number of records per block is simply `⌊B / R⌋`; leftover bytes (`B mod R`) are unused, or reserved for a small block header (free space count, block ID, pointer to next block in a chain). The trouble starts with deletion. Suppose record 3 is deleted from a block holding records 0..7. Two common strategies exist: 1. <strong>Shift records to fill the gap.</strong> Move record 7 into slot 3 (or shift 4..7 left by one slot). This preserves contiguity and a simple record count, but costs O(n) data movement per deletion, and worse, it silently changes the identity/location* of whatever was moved — any external pointer to "record 7" is now broken. 2. Leave a "tombstone" and track free slots. Mark the slot as deleted (e.g., with a special bit or by chaining it into a free list using its own space to store a pointer to the next free slot). Insertion then reuses a free slot in O(1) rather than always appending. Other records keep their positions, so external pointers remain valid. Real systems almost always choose strategy 2 for exactly the reason above: query processing frequently keeps pointers to records (from indexes, from sort intermediate structures) that must remain valid across ordinary deletions elsewhere in the file. ``` // Free-list managed fixed-length block struct Block { int freeListHead // index of first free slot, or -1 if none byte data[N][R] // N fixed-size slots of size R each } Insert(block, record): if block.freeListHead == -1: return FAIL // block full, caller must find/allocate another block slot = block.freeListHead block.freeListHead = ReadInt(block.data[slot]) // next pointer was stored in the free slot block.data[slot] = record return slot Delete(block, slot): WriteInt(block.data[slot], block.freeListHead) // store old head as "next" pointer block.freeListHead = slot ``` This reuses each deleted slot's own bytes to store a "next free slot" pointer — no extra space overhead, and both insert and delete run in O(1).
Variable-length records: why fixed offsets fail
When records vary in size, `i * R` is meaningless — there is no single `R`. Two classic sub-problems appear:
- Representing one variable-length record. A record with a `VARCHAR(50)` field cannot simply reserve 50 bytes for every row (wasteful, and still doesn't handle arbitrarily long strings). Instead, records commonly use one of:
- Fixed-length fields first, then variable-length fields, prefixed with an offset/length table. The record begins with fixed-size fields and a small array of `(offset, length)` pairs — one per variable field — followed by the variable field data itself, packed contiguously.
- Delimiters between variable fields (simple, but scanning to find field `k` costs O(k), and delimiter bytes must never appear inside data).
- Null bitmaps, a small bit-vector at the record's start marking which fields are null, so null fields consume zero data bytes while fixed offsets remain computable for non-null fixed fields.
- Packing many variable-length records into one block. Since records have different sizes, records cannot be found by arithmetic; the block needs an explicit directory.
The slotted-page structure
The slotted page is the standard solution, used (in some variant) by essentially every relational database engine. The key idea: split the block into two regions that grow toward each other from opposite ends.
- From the start of the block: a small header, then a slot array — one fixed-size entry per record, each holding `(offset, length)` of that record's bytes (or a "deleted" marker). The slot array grows downward as records are added.
- From the end of the block: the actual record bytes, packed contiguously with no gaps. Record data grows upward (toward lower addresses) as records are added.
- The header tracks: number of slots, offset to the start of free space (the boundary between the two growing regions).
Crucially, a record is addressed externally not by its byte offset but by a logical record ID `rid = (page_id, slot_number)`. Any code elsewhere in the system — an index entry, a foreign-key-style pointer — stores this `rid`, never a raw byte offset. This indirection is exactly what lets the page physically move a record's bytes (e.g., during compaction) without invalidating anything that points to it, since only the slot array entry changes, not the slot number. ``` PSEUDOCODE — Slotted Page struct Slot { int offset // byte offset of record data within the page, or SENTINEL if deleted int length // length of record data in bytes } struct SlottedPage { Header header { int numSlots int freeSpacePointer // offset where free space begins (grows downward from data end) } Slot slots[] // grows forward (upward in offset) from just after header byte recordData[] // grows backward from the end of the page } // Amount of contiguous free space between slot array and record data FreeSpace(page): slotArrayEnd = HEADER_SIZE + page.header.numSlots * SLOT_SIZE return page.header.freeSpacePointer - slotArrayEnd
Insert(page, record): len = length(record) if FreeSpace(page) < len + SLOT_SIZE and no reusable deleted slot exists: return FAIL // page is full; caller allocates a new page slotIdx = FindDeletedSlot(page) // reuse a tombstoned slot if one exists if slotIdx == NONE: slotIdx = page.header.numSlots page.header.numSlots += 1 newOffset = page.header.freeSpacePointer - len WriteBytes(page, newOffset, record) page.slots[slotIdx] = { offset: newOffset, length: len } page.header.freeSpacePointer = newOffset return (page.pageID, slotIdx) // this is the record's rid
Delete(page, slotIdx): page.slots[slotIdx].offset = DELETED // NOTE: record bytes are now "dead space" inside recordData; not yet reclaimed // slotIdx itself is retained so existing rids referencing it resolve to "deleted" // rather than accidentally referencing whatever record is later inserted
Compact(page): // Reclaims dead space left behind by deletions and updates, without changing // any slot's index — only its offset field is updated. liveSlots = [s for s in page.slots if s.offset != DELETED] sort liveSlots by current offset descending // process from the high-address end inward writePtr = END_OF_PAGE for slot in liveSlots (in that order): writePtr -= slot.length MoveBytes(page, from=slot.offset, to=writePtr, size=slot.length) slot.offset = writePtr page.header.freeSpacePointer = writePtr
Read(page, slotIdx): slot = page.slots[slotIdx] if slot.offset == DELETED: return NOT_FOUND return ReadBytes(page, slot.offset, slot.length)
Update(page, slotIdx, newRecord): oldLen = page.slots[slotIdx].length newLen = length(newRecord) if newLen <= oldLen: WriteBytes(page, page.slots[slotIdx].offset, newRecord) // shrink in place, wastes (oldLen-newLen) bytes page.slots[slotIdx].length = newLen else: Delete(page, slotIdx) if FreeSpace(page) >= newLen: (_, slotIdx) = InsertAtSlot(page, slotIdx, newRecord) // reuse same slot index, new offset else: signal "record must move to another page"; caller updates all external rids ```
Complexity & correctness
Fixed-length records with direct offsets. Access is `O(1)`: the address of record `i` is `base + i R`, a single multiplication and addition, no search. Space overhead is limited to at most `R − 1` wasted bytes per block (the remainder `B mod R`), plus header bytes. With a free list, insert and delete are also `O(1)`, since each only touches the header pointer and one slot's bytes — no shifting of other records is required. The correctness invariant is: the free-list head always points to a slot whose stored "next" value is either another free slot or the sentinel*, which is maintained by construction (`Delete` always overwrites the deleted slot with the current head, then advances the head to it), so the list can never point to garbage.
Slotted pages. Within a single page:
- `Read(slotIdx)` is `O(1)`: one array index into the slot array, then one bounded copy.
- `Insert` is `O(1)` amortized: computing free space and writing the record is constant work; finding a deleted slot to reuse can be done in `O(1)` if a free-slot list is maintained (mirroring the fixed-length case), or `O(numSlots)` with a naive linear scan — most real implementations use the `O(1)` variant.
- `Delete` is `O(1)`: only the slot's offset field is overwritten.
- `Compact` is `O(numSlots)` (equivalently `O(page size)`), since every live record's bytes are copied once. This is only invoked when free space fragmentation prevents an insert that would otherwise fit, not on every operation, so its cost is amortized across many inserts/deletes rather than paid per-operation.
Why slot indirection is correct. The essential invariant is: > A record's logical identity, `rid = (page_id, slot_number)`, never changes for the lifetime of the record, even though its physical byte offset within the page may change arbitrarily (via compaction) or its slot's content may temporarily represent "deleted." This invariant is what every higher layer (indexes, buffer manager, concurrency control) relies on. It holds because every mutation to physical position (`Compact`, `Update` with in-place move) is required to update only the `offset` field of the existing slot entry — the slot's position in the array, i.e., its number, is never reassigned to a different logical record while any live reference to it exists. Proof sketch by induction on operations: initially (empty page) the invariant holds vacuously; `Insert` establishes a new `rid` and never touches existing slots' indices; `Delete` marks a slot deleted but does not reassign its index to another record (it may only be reused after all external references are known to be gone — typically guaranteed at a higher layer, e.g., after the enclosing tuple is removed from all indexes); `Compact` only rewrites `offset` fields, preserving each slot's index. Hence the invariant is preserved by every operation, and by induction holds after any sequence of operations.
Tradeoffs. Slotted pages trade a small amount of space (the slot array, typically 4–8 bytes per record) and occasional compaction cost for: variable-length record support, stable logical addressing, and graceful handling of deletion/update without shifting unrelated records. Fixed-length direct addressing is strictly cheaper when it applies (no slot array, no compaction), but cannot support variable-length attributes without wasting space via worst-case-size padding.
Worked example
Consider an 8 KB page (8192 bytes), header = 8 bytes, slot entries = 4 bytes each (2-byte offset won't fit 8192 so assume 2 bytes offset + 2 bytes length = 4 bytes, using a page-relative 13-bit offset scheme for illustration; treat as 4 bytes for arithmetic clarity). Insert three variable-length customer records in order:
| Step | Action | Record bytes | Slot array (after) | Free-space pointer (after) | Notes |
|---|---|---|---|---|---|
| 0 | initial | — | `numSlots=0` | 8192 | empty page, header at bytes 0–7 |
| 1 | `Insert("Alice, 42 Elm St")` | 40 bytes | slot0 = (off=8152, len=40) | 8152 | data written at [8152,8192) |
| 2 | `Insert("Bob, 9 Oak Ave, Unit 4")` | 60 bytes | slot0; slot1=(off=8092,len=60) | 8092 | data at [8092,8152) |
| 3 | `Insert("Cy, 1 Pine Rd")` | 40 bytes | slot0; slot1; slot2=(off=8052,len=40) | 8052 | data at [8052,8092) |
At this point `FreeSpace = 8052 − (8 + 3×4) = 8052 − 20 = 8032` bytes remain — plenty of room. Now delete Bob (`slotIdx = 1`): ``` Delete(page, 1): page.slots[1].offset = DELETED ``` Slot 1's index is retained (any `rid = (page_id, 1)` now correctly resolves to "not found"), but its 60 bytes at `[8092, 8152)` are now dead space embedded between rec 0's and rec 2's data — `FreeSpace()` (which only measures the gap between the slot array and `freeSpacePointer`) does not yet reflect these 60 reclaimed bytes. Now insert a new record, "Dana, 5 Cedar Ln, Apt 2B" (55 bytes). Suppose contiguous free space (the gap, 8032 bytes) is more than enough — insertion proceeds normally at `freeSpacePointer − 55`, reusing slot index 1 (found via `FindDeletedSlot`) rather than allocating slot 3: ``` newOffset = 8052 - 55 = 7997 page.slots[1] = { offset: 7997, length: 55 } page.header.freeSpacePointer = 7997 ``` Note Bob's old 60 dead bytes at `[8092,8152)` are still never touched — they are simply orphaned until a `Compact()` call physically squeezes them out, at which point every live slot's `offset` (but never its index) is rewritten to remove the gap. This example demonstrates the two distinct notions of "free space" (contiguous gap vs. total reclaimable space) that make `Compact` necessary in real systems, and shows that a `rid` (here, slot 1) can be legitimately reused for an unrelated new record only after the old occupant's `rid` is known to be dead everywhere else in the system.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Using raw byte offsets as record pointers | Seems simpler than a slot indirection layer | Any compaction or in-place update silently invalidates every external pointer (index entries, cursors) |
| Shifting records to fill gaps on delete (fixed-length case) | Looks like the "obvious" way to keep a compact array | O(n) delete cost, and moved records change identity, breaking external references |
| Forgetting the slot array itself needs space accounting | Only tracking record-data free space | `Insert` can wrongly report success even when the slot array would overflow into the data region |
| Conflating "contiguous free space" with "total free space" | Assuming `FreeSpacePointer − slotArrayEnd` reflects all reclaimable bytes | Insert fails or triggers unnecessary page-splits when a `Compact()` would have made room |
| Reusing a deleted slot's index before all external `rid`s to it are known invalid | Trying to save space aggressively | Dangling references silently resolve to the wrong, unrelated new record instead of "not found" |
| Padding every variable field to its maximum declared size | Avoiding offset/length bookkeeping | Massive wasted space per record, fewer records per block, more I/O for the same data |
Pioneers & history
The slotted-page idea does not trace to a single named "inventor" the way an algorithm like Dijkstra's does; it emerged as engineering practice inside early relational and hierarchical database systems as they confronted the mismatch between fixed disk blocks and variable-length business records. It is nonetheless deeply tied to the broader architectural vision of separating logical data organization from physical storage, a principle most forcefully articulated by Edgar F. Codd's relational model, which insisted that applications should reason about data independent of its physical representation — precisely the property slotted pages deliver for records inside a page.
Origins · 1 minEdgar F. Codd and how this was discovered
Where this matters
Every mainstream relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements some variant of the slotted page for heap-organized tables, because virtually all real schemas mix fixed-length numeric columns with variable-length text. PostgreSQL's on-disk page format is a textbook slotted page: a page header, an `ItemIdData` array (the slot array, each entry holding offset and length flags), and tuple data packed from the end of the page, with `VACUUM` performing exactly the `Compact` operation described above. InnoDB pages similarly separate a directory of record pointers from the record heap. Beyond relational engines, the same idea recurs anywhere fixed-size storage units must hold variable-size logical items with stable external references: filesystem inode/extent structures, key-value store SSTable blocks (e.g., in LSM-tree engines like RocksDB and Cassandra), and even in-memory columnar formats that need compact variable-length string storage. Anywhere a system needs "records that vary in size, referenced by a stable handle, packed into a fixed-size container," this design pattern reappears. This layout machinery is the direct foundation for Heap Files (unordered collections of such pages, with free-space maps to find pages with room for a new record), Sorted Files (pages kept in key order, where insertion may require record migration across pages), and Buffer Management (which caches exactly these pages in memory and must know their format to pin, flush, and evict them correctly).
Ask the tutor: How does a heap file decide which page to insert a new record into when many pages might have free space?
What exactly is the difference between a "block" and a "page"?
The terms are used almost interchangeably in database contexts, though "block" more often refers to the physical unit the storage device or filesystem transfers, while "page" more often refers to the logical unit the database engine manages, which the engine typically sizes to be a multiple of the underlying block size. A database might use an 8 KB page built from two 4 KB filesystem blocks, for instance. Within this article, and in most database textbooks, the two terms describe the same fixed-size container and are used interchangeably; what matters is that it is the fixed-size granularity of I/O and of record packing.
Why not just always use variable-length record formats, even for tables with only fixed-length columns?
Fixed-length record layouts allow O(1) direct-offset addressing (`base + i * R`) with no directory lookup at all, and no risk of internal fragmentation from deletions leaving irregularly-sized gaps. When every column truly has a fixed size — integers, dates, fixed-length codes — this simplicity is pure upside: less metadata overhead, simpler free-space management, and slightly better CPU cache behavior since there is no slot-array indirection to chase. Variable-length (slotted) layouts are only necessary once at least one column can genuinely vary in size, such as a VARCHAR, an optional field, or a repeating group; using them unconditionally would add directory overhead with no benefit for genuinely fixed-size data.
How does a slotted page know how much free space is really available, given fragmentation?
A slotted page directly tracks only contiguous free space, the gap between the end of the slot array and the start of packed record data, via the free-space pointer. Deleted records leave dead bytes scattered inside the record-data region that are not reflected in this pointer until a `Compact()` operation runs. Real systems typically maintain an additional summary (sometimes an approximate "total free bytes including reclaimable dead space" counter at the page level, and a coarser free-space map across many pages) so the engine can decide whether compaction would free enough contiguous space to satisfy a pending insert before actually performing the O(page size) compaction work.
What happens when an updated record grows too large to fit back in its original page?
The engine has two broad options. One is a forwarding pointer: the original slot is rewritten to point to a new location (possibly on another page) where the enlarged record now lives, so the original `rid` still resolves correctly, at the cost of an extra indirection on future reads. The other is to physically relocate the record and update every external reference to it, which is far more expensive and generally avoided for tables with active indexes. Most production engines use some form of forwarding or "overflow" mechanism precisely to avoid the cost and fragility of rewriting external pointers throughout the system.
Does the slotted-page idea still matter given SSDs and huge RAM buffer pools?
Yes — the fundamental mismatch between variable-size logical records and fixed-size storage containers is independent of the storage medium's speed. SSDs still perform I/O in page/block-sized units (often larger, for erase-block reasons), and RAM-resident buffer pool pages still need some in-page structure to support variable-length records with stable addressability for indexes. What has changed is less the page format itself and more the tuning of page size and compaction frequency, since SSDs tolerate different access patterns than spinning disks; the slot/offset abstraction itself remains essentially unchanged across storage generations.
How do indexes actually use a record's rid?
An index (such as a B+-tree leaf entry) stores, for each key, the `rid = (page_id, slot_number)` of the corresponding record rather than a raw byte address. To fetch the full record, the engine reads the page identified by `page_id` (via the buffer manager, described in Buffer Management), then looks up `slot_number` in that page's slot array to get the current offset and length, and finally reads those bytes. Because the slot number is stable across compaction, the index entry never needs to be updated just because the page's internal layout was reorganized — only if the record moves to a different page entirely.
Is the free list for fixed-length records actually stored inside the deleted slots themselves?
Yes, this is the standard trick, and it is what makes the technique cost zero extra space: since a deleted slot's original data is no longer needed, its bytes can be reinterpreted to hold a pointer (an integer index) to the next free slot, forming a linked list threaded entirely through otherwise-unused space. The block header only needs a single extra integer, the index of the current list head, to make the entire free-slot chain traversable. This mirrors the classic technique of overlaying a linked list onto an otherwise-wasted memory region.