Database Management Systems (DBMS) Module 8 – Storage and file organisation
Pages, records and the slotted-page layout
How rows become records in fixed-size pages, why the slotted-page layout keeps record ids stable, and how to count blocks for spanned and unspanned files.
What you will learn
- Describe fixed- and variable-length record formats and how NULLs are marked
- Explain the slotted page and why record ids survive compaction within a page
- Compute blocking factors and block counts for spanned and unspanned organisations
- Decode the header, cell pointers and records of a real SQLite page
- Estimate how many rows fit in a PostgreSQL page from header, slot and alignment sizes
Before you start
What you’ll learn · Before you start
What you will learn
- Describe fixed- and variable-length record formats and how NULLs are marked
- Explain the slotted page and why record ids survive compaction within a page
- Compute blocking factors and block counts for spanned and unspanned organisations
- Decode the header, cell pointers and records of a real SQLite page
- Estimate how many rows fit in a PostgreSQL page from header, slot and alignment sizes
Before you start
On this page
Databases move data between storage and memory in pages: fixed-size blocks, usually 8 kB in PostgreSQL and 4,096 bytes by default in SQLite. Each page holds many records, the rows of a table encoded as bytes. Fixed-length records could sit at fixed offsets, but real rows carry text of any length and NULLs, so engines such as PostgreSQL and SQLite use the slotted-page layout: a header, then an array of slots that grows forward, while the records are stored backward from the end of the page. A record is found by its record id, the pair (page number, slot number). Because only the slot knows where its record sits, the engine can move records inside the page to close gaps without breaking a single id. This lesson builds such a page, then counts how many records fit in a block.
Records as bytes
A record is a row’s values laid out one after another. When every field has a fixed length, as integers and dates do, the record has a fixed length too, and each field starts at the same offset in every record. Variable-length fields such as names and comments break that, so engines store each value’s length, or an array of offsets at the start of the record, letting a reader jump to the field it wants. NULLs need marking as well, preferably without spending the bytes of a value on them.
Both engines of this track do exactly that. A PostgreSQL row starts with a fixed header of 23 bytes on most machines and, only when the row holds a NULL, a null bitmap with one bit per column; a NULL value then takes no space at all. An SQLite record starts with a header of serial types, one per column, that give each value’s type and length; serial type 0 means NULL and takes no space either.
The slotted-page layout
The slotted-page layout handles variable-length records with one level of indirection.
The slotted-page layout
Text description of the diagram
The page is drawn as one strip of bytes, from left to right.
1. It starts with a header. 2. Next come three slots, numbered 0, 1 and 2. The slot array grows to the right as slots are added. 3. Then comes free space. 4. At the right end sit three rows. The first row inserted, row 0, is at the very end of the page; row 1 comes before it and row 2 before that. Rows are added towards the left, into the free space.
An arrow runs from each slot to its row: slot 0 to row 0, slot 1 to row 1 and slot 2 to row 2. Each slot holds the offset and the length of its row. A record id is the pair (page number, slot number), so a row can move inside the page, for example when the page is compacted, and its id stays the same because only the slot's offset changes.
The header says how many slots the page has and where its free space starts and ends. Each slot holds the offset and the length of one record. New slots go after the last slot, new records in front of the first record, and the page is full when the two meet. The program builds a 96-byte page that you can watch byte by byte: it inserts four records, deletes one, then inserts a record that does not fit in the free gap.
"""A slotted page you can watch: records move, record ids do not.
The page is only 96 bytes, so every byte fits on the screen. It starts with a
4-byte header, then an array of 4-byte slots (offset and length of a record)
that grows forward, while records are written backward from the end of the
page. Free space is the gap in between. In the maps, h is the header, s a slot,
a letter the record of one slot, x the bytes of a deleted record and . free space.
"""
PAGE_SIZE, HEADER, SLOT = 96, 4, 4
class SlottedPage:
def __init__(self):
self.data = bytearray(PAGE_SIZE)
self.slots = [] # slot number -> [offset, length]; length 0 means the slot is free
self.free_end = PAGE_SIZE # records occupy data[free_end:]
self.dead = set() # byte positions of deleted records, until compaction
def gap(self):
return self.free_end - (HEADER + SLOT * len(self.slots))
def insert(self, text):
record = text.encode()
free_slot = next((i for i, (_, n) in enumerate(self.slots) if n == 0), None)
need = len(record) + (SLOT if free_slot is None else 0)
if need > self.gap():
print(f" {len(record)} bytes do not fit in the gap of {self.gap()}: compact the page first")
self.compact()
if need > self.gap():
raise ValueError("the page is full")
self.free_end -= len(record)
self.data[self.free_end:self.free_end + len(record)] = record
if free_slot is None:
self.slots.append([self.free_end, len(record)])
return len(self.slots) - 1
self.slots[free_slot] = [self.free_end, len(record)]
return free_slot
def delete(self, slot):
offset, length = self.slots[slot]
self.dead.update(range(offset, offset + length))
self.slots[slot] = [0, 0] # the slot stays; only its record is gone
def compact(self):
end = PAGE_SIZE
for slot in sorted(range(len(self.slots)), key=lambda s: -self.slots[s][0]):
offset, length = self.slots[slot]
if length:
end -= length
self.data[end:end + length] = bytes(self.data[offset:offset + length])
self.slots[slot][0] = end
self.free_end, self.dead = end, set()
def read(self, slot):
offset, length = self.slots[slot]
return self.data[offset:offset + length].decode()
def show(self, title):
owner = {}
for slot, (offset, length) in enumerate(self.slots):
owner.update({i: "ABCDEFGH"[slot] for i in range(offset, offset + length)})
cells = []
for i in range(PAGE_SIZE):
if i < HEADER:
cells.append("h")
elif i < HEADER + SLOT * len(self.slots):
cells.append("s")
else:
cells.append(owner.get(i, "x" if i in self.dead else "."))
print(f"{title} (gap of {self.gap()} free bytes)")
print(" ", "".join(cells[:48]))
print(" ", "".join(cells[48:]))
for slot, (offset, length) in enumerate(self.slots):
where = f"bytes {offset}-{offset + length - 1}" if length else "free"
text = self.read(slot) if length else ""
print(f" slot {slot}: {where:<12} {text}".rstrip())
page = SlottedPage()
for name in ["Asha,CSE,2023", "Rohan,Mechanical,2022", "Meera,ECE,2024", "Vikram,Civil,2021"]:
page.insert(name)
page.show("After four inserts")
page.delete(1)
page.show("After deleting slot 1")
slot = page.insert("Kavya,Chemical,2025")
page.show(f"After inserting Kavya into slot {slot}")Output
After four inserts (gap of 11 free bytes) hhhhssssssssssssssss...........DDDDDDDDDDDDDDDDD CCCCCCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBAAAAAAAAAAAAA slot 0: bytes 83-95 Asha,CSE,2023 slot 1: bytes 62-82 Rohan,Mechanical,2022 slot 2: bytes 48-61 Meera,ECE,2024 slot 3: bytes 31-47 Vikram,Civil,2021 After deleting slot 1 (gap of 11 free bytes) hhhhssssssssssssssss...........DDDDDDDDDDDDDDDDD CCCCCCCCCCCCCCxxxxxxxxxxxxxxxxxxxxxAAAAAAAAAAAAA slot 0: bytes 83-95 Asha,CSE,2023 slot 1: free slot 2: bytes 48-61 Meera,ECE,2024 slot 3: bytes 31-47 Vikram,Civil,2021 19 bytes do not fit in the gap of 11: compact the page first After inserting Kavya into slot 1 (gap of 13 free bytes) hhhhssssssssssssssss.............BBBBBBBBBBBBBBB BBBBDDDDDDDDDDDDDDDDDCCCCCCCCCCCCCCAAAAAAAAAAAAA slot 0: bytes 83-95 Asha,CSE,2023 slot 1: bytes 33-51 Kavya,Chemical,2025 slot 2: bytes 69-82 Meera,ECE,2024 slot 3: bytes 52-68 Vikram,Civil,2021
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 slotted_page.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Deleting slot 1 only marks the slot free; the record’s bytes (the x’s) stay until the page is compacted. Kavya’s 19
bytes do not fit in the 11-byte gap, so the page is compacted: Meera and Vikram slide towards the end, their slots
get new offsets, and Kavya takes the freed slot 1. Every slot number still finds the record it found before.
PostgreSQL’s manual explains that it never moves an item identifier until the item is freed, which is what lets the
identifier’s number serve as a lasting reference while the item itself moves to compact the page. PostgreSQL calls
the pair of page and item number a ctid, such as (0,3).
How many records fit in a block
Capacity plans and exam questions start from the blocking factor: how many records of R bytes fit in a block of B bytes. Textbooks call pages blocks, and count them the same way. When records may not cross a block boundary (an unspanned file), bfr = ⌊B ÷ R⌋, a file of r records needs b = ⌈r ÷ bfr⌉ blocks, and B − bfr × R bytes at the end of each block are wasted. When records may continue in the next block (a spanned file), nothing is wasted and b = ⌈r × R ÷ B⌉, but a record that crosses a boundary costs two block reads.
"""Blocking factor: how many records fit in one block, and how many blocks a file needs.
Unspanned: a record never crosses a block boundary, so the end of each block may
be wasted. Spanned: records are packed end to end, so nothing is wasted, but a
record that crosses a boundary needs two blocks to read.
"""
from math import ceil
B = 4096 # bytes in a block
for name, r, R in [("enrolments", 1_000_000, 100), ("scanned forms", 1_000_000, 1_500)]:
bfr = B // R # whole records per block
unspanned = ceil(r / bfr)
wasted = B - bfr * R # bytes left over in every full block
spanned = ceil(r * R / B)
# A block boundary splits a record unless it falls exactly between two records.
boundaries = (r * R - 1) // B
split = sum(1 for k in range(1, boundaries + 1) if (k * B) % R)
print(f"{name}: r = {r:,} records of R = {R:,} bytes, B = {B:,} bytes")
print(f" blocking factor bfr = floor(B / R) = {bfr}")
print(f" unspanned: {unspanned:,} blocks, {wasted:,} bytes wasted per block ({wasted / B:.1%})")
print(f" spanned: {spanned:,} blocks, {split:,} records split across two blocks ({split / r:.1%})")Output
enrolments: r = 1,000,000 records of R = 100 bytes, B = 4,096 bytes blocking factor bfr = floor(B / R) = 40 unspanned: 25,000 blocks, 96 bytes wasted per block (2.3%) spanned: 24,415 blocks, 23,438 records split across two blocks (2.3%) scanned forms: r = 1,000,000 records of R = 1,500 bytes, B = 4,096 bytes blocking factor bfr = floor(B / R) = 2 unspanned: 500,000 blocks, 1,096 bytes wasted per block (26.8%) spanned: 366,211 blocks, 365,234 records split across two blocks (36.5%)
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 blocking_factor.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
For 100-byte records the choice hardly matters. For 1,500-byte records an unspanned block holds only two records and wastes 27 % of its bytes, so the spanned file needs 366,211 blocks instead of 500,000, at the price of 36.5 % of its records being split across two blocks. Real engines also spend bytes on page headers and slots, which these formulas leave out.
Check yourself
4 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Inside a real SQLite page, byte by byte Pro: opens with a Pro, Premium or Ultimate pass
SQLite documents its file format down to the byte, and every table is a B-tree of slotted pages. This part opens page 2 of a real database file with Python, decodes its header, cell pointers and records, and follows what a delete, an insert and an oversized row do to it.
In this part:
- Decoding the header, the cell pointers and the cells
- What a delete and an insert leave behind
- Rows too big for a page: overflow chains, predicted and counted
- Exercise: predict a record’s size
- Predict the size of an SQLite record
2 runnable examples (Python) · 1 exercise with sample tests · about 6 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Sizing rows and pages with numbers Pro: opens with a Pro, Premium or Ultimate pass
Textbook formulas divide the block size by the record size, while a real engine also spends bytes on headers, slots and alignment padding. This part works out how many rows fit in an 8 kB PostgreSQL page from its documented sizes, shows what column order and NULLs change, and works exam-style blocking items in full.
In this part:
- Rows per 8 kB PostgreSQL page, worked from the documented sizes
- Column order, NULLs and fillfactor: the trade-offs in numbers
- Exam-style blocking items, worked in full
- When a value leaves the page: TOAST and overflow pages
1 runnable example (Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher · Warm-up
What is a slotted page, and why does a record id name a slot instead of a byte offset?
A slotted page starts with a header, then an array of slots that grows forward, while records are stored backward from the end of the page, with the free space between them. Each slot holds the offset and the length of one record, and a record id is the pair (page number, slot number). Naming the slot instead of the byte offset adds one level of indirection: when records are deleted or change size, the engine can compact the page by moving records and rewriting the offsets in their slots, and every id that points into the page still finds its record, so indexes need no change. PostgreSQL calls the pair a ctid, such as (0,3); SQLite keeps its cell pointers in key order instead and finds each row by its rowid.
-
Mid to senior
Estimate how many 8 kB PostgreSQL pages a table of 50 million rows needs, with columns id bigint, customer_id integer, quantity smallint, paid boolean and a 10-character note. What changes if paid is declared first, or if note is usually NULL?
-
Mid to senior
To skip index lookups, a team caches the ctid of each hot row. After a VACUUM FULL, and sometimes after ordinary updates, cached ctids return the wrong rows or none. Explain what happened and what you would store instead.
-
Mid to senior
Each row of a table carries a 6 KB JSON document beside a few small columns, and a report that reads only the small columns has become slow. Explain what happens to such rows in SQLite and in PostgreSQL, and what you would change.
Key takeaways
- A page is the unit of I/O. A record encodes a row’s values, with lengths or offsets for variable-length fields and a null bitmap or serial types for NULLs.
- The slotted-page layout keeps slots at the start of the page and records at the end; a record id (page, slot) survives compaction because only the slot’s offset changes.
- Unspanned: bfr = ⌊B ÷ R⌋ and b = ⌈r ÷ bfr⌉. Spanned: b = ⌈r × R ÷ B⌉, with no waste but split records.
References
- PostgreSQL 18 Documentation: Database Page Layout (The PostgreSQL Global Development Group)
- PostgreSQL 18 Documentation: TOAST (The PostgreSQL Global Development Group)
- PostgreSQL 18 Documentation: System Columns (ctid) (The PostgreSQL Global Development Group)
- PostgreSQL 18 Documentation: pg_type (typlen and typalign) (The PostgreSQL Global Development Group)
- PostgreSQL 18 Documentation: CREATE TABLE (fillfactor) (The PostgreSQL Global Development Group)
- PostgreSQL source: htup_details.h (MaxHeapTuplesPerPage) (The PostgreSQL Global Development Group)
- PostgreSQL source: bufpage.c (PageAddItemExtended) (The PostgreSQL Global Development Group)
- Database File Format (SQLite)
- SQLite: PRAGMA statements (page_size, secure_delete) (SQLite)
- The DBSTAT Virtual Table (SQLite)
- sqlite3: DB-API 2.0 interface for SQLite databases (Python Software Foundation)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress