DBMS

Storage And Indexing

How a Database Stores Data

SSD random read ~100 microseconds (1,000x RAM)

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Module 4, Chapter 5: When to Denormalise Time to complete: ~20 minutes

Table of Contents

  1. The Cost That Shapes Everything
  2. The Page
  3. Slotted Page Layout
  4. Heap Files and the Full Scan
  5. Row IDs
  6. Row vs Column Storage
  7. Summary & Next Steps

1. The Cost That Shapes Everything

The Numbers
─────────────────────────────────────────
  CPU comparison        ~1 nanosecond
  RAM access            ~100 nanoseconds
  SSD random read       ~100 microseconds   (1,000x RAM)
  HDD random seek       ~10 milliseconds  (100,000x RAM)

  A single disk read costs more than a hundred
  thousand comparisons.
─────────────────────────────────────────

The Consequence for Algorithms
─────────────────────────────────────────
  The DSA Notes counted COMPARISONS. A database
  counts DISK PAGE READS.

  This inverts several familiar answers:

    - a binary search tree is a bad disk structure,
      despite being an excellent memory one
      (Chapter 2)
    - reading 200 sequential rows can be cheaper
      than reading 20 scattered ones
    - an algorithm doing more CPU work to do less
      I/O wins

  Every design in this module is an answer to "how
  do I touch fewer pages?"
─────────────────────────────────────────

2. The Page

The Unit of I/O
─────────────────────────────────────────
  Databases never read one row from disk. They read
  a fixed-size PAGE (or block) — typically 4KB,
  8KB, or 16KB.

    PostgreSQL   8 KB
    MySQL/InnoDB 16 KB
    SQLite       4 KB (default)

  Reading one 80-byte row costs the same as reading
  the whole 8KB page containing it.
─────────────────────────────────────────

Two Consequences You Can Act On
─────────────────────────────────────────
  NARROWER ROWS ARE FASTER. If a row is 80 bytes,
  ~100 fit per 8KB page. At 800 bytes, 10 fit. The
  same scan touches TEN TIMES the pages.

  This is why SELECT * is a performance decision
  and not only a style one — and why moving a large
  rarely-read column into a separate table
  (Module 4, Chapter 2) genuinely helps.

  LOCALITY IS FREE. Rows that are read together
  should live together. If a page is already being
  read, everything on it is effectively free.
─────────────────────────────────────────

3. Slotted Page Layout

How variable-length rows fit into a fixed-size page.

The Structure
─────────────────────────────────────────
  ┌─────────────────────────────────────────┐
  │ HEADER  page id, free space, checksum   │
  ├─────────────────────────────────────────┤
  │ SLOT ARRAY  [ptr0][ptr1][ptr2][ptr3]... │ ← grows RIGHT
  ├──────────────┬──────────────────────────┤
  │              │                          │
  │  FREE SPACE  │                          │
  │              │                          │
  ├──────────────┴──────────────────────────┤
  │            ...row 3...                  │
  │        ...row 2...                      │ ← grows LEFT
  │     ...row 1...                         │
  │  ...row 0...                            │
  └─────────────────────────────────────────┘

  Slots grow from the front, rows from the back.
  The page is full when they meet.
─────────────────────────────────────────

Why Indirection Through a Slot Array
─────────────────────────────────────────
  A row is addressed as (page number, SLOT number),
  never as a byte offset.

  So the row can MOVE within its page — during
  compaction, or when an update makes it longer —
  and every index pointing at it stays valid,
  because only the slot entry changes.

  Without this, every update that changed a row's
  size would require updating every index. That one
  design choice is what makes variable-length rows
  practical.
─────────────────────────────────────────

What Happens When a Row Grows Too Big
─────────────────────────────────────────
  UPDATE makes a row longer than the free space on
  its page.

  The row moves to another page, leaving a
  FORWARDING POINTER behind. Reads now cost TWO
  page fetches instead of one.

  Enough of these and the table is fragmented —
  which is what VACUUM (PostgreSQL) or OPTIMIZE
  TABLE (MySQL) repairs.

  Practical tip: a column that grows from empty to
  large on update causes this. Give it a sensible
  default, or store it elsewhere.
─────────────────────────────────────────

4. Heap Files and the Full Scan

The Heap
─────────────────────────────────────────
  The default table storage: pages in NO particular
  order. New rows go wherever there is free space.

  Insert  ──► O(1). Find a page with room, write.
  Search  ──► O(n). Read EVERY page.

  Reading every page is a FULL TABLE SCAN, or
  SEQUENTIAL SCAN.
─────────────────────────────────────────

# The cost, made concrete.
ROWS      = 10_000_000
ROW_BYTES = 100
PAGE      = 8192
 
rows_per_page = PAGE // ROW_BYTES                 # 81
pages         = ROWS // rows_per_page             # ~123,457
seconds       = pages * 100e-6                    # sequential-ish, ~100µs/page
 
print(f"{pages:,} pages, ~{seconds:.1f}s for one full scan")
# 123,456 pages, ~12.3s
 
# Now the same table with 800-byte rows:
print(f"{ROWS // (PAGE // 800):,} pages")         # 1,000,000 pages — 8x the work
When a Full Scan Is the RIGHT Plan
─────────────────────────────────────────
  Full scans are not automatically bad.

  Reading a large FRACTION of the table (roughly
  >5-20%, depending on the database) is FASTER as a
  sequential scan than as index lookups — because
  sequential reads are much cheaper per page than
  random ones, and an index would visit the same
  pages in random order.

  This is why the optimiser sometimes ignores your
  index, and why that is often correct (Module 6).
─────────────────────────────────────────

5. Row IDs

The Physical Address
─────────────────────────────────────────
  A row is identified physically by
  (page number, slot number).

    PostgreSQL   ctid
    Oracle       ROWID
    InnoDB       uses the PRIMARY KEY instead

  Indexes store this address as their pointer to
  the actual row.
─────────────────────────────────────────

-- PostgreSQL exposes it directly.
SELECT ctid, id, name FROM students LIMIT 3;
--  (0,1) | 1 | Asha        page 0, slot 1
--  (0,2) | 2 | Ravi
--  (0,3) | 3 | Meera
Heap-Organised vs Index-Organised
─────────────────────────────────────────
  HEAP-ORGANISED (PostgreSQL)
    The table is a heap; ALL indexes — including
    the primary key — point into it.
    Primary key and secondary lookups cost the
    same.

  INDEX-ORGANISED / CLUSTERED (InnoDB, SQL Server)
    The table IS the primary key's B+ tree; rows
    live in the leaves.
    Primary key lookups are one traversal.
    SECONDARY indexes store the primary key, so
    they need TWO traversals — one in the secondary
    index, one in the clustered index.

  This is why InnoDB advice says to keep the
  primary key small: every secondary index stores
  a copy of it.
─────────────────────────────────────────

6. Row vs Column Storage

Two Layouts for the Same Table
─────────────────────────────────────────
  ROW STORE (OLTP — the default)
    page: [id,name,city,marks][id,name,city,marks]...
    Whole rows together.

    GOOD:  fetch a whole row, write a whole row
    BAD:   SUM(marks) over 10M rows still reads
           every column of every row

  COLUMN STORE (OLAP — analytics)
    page: [id,id,id,...][name,name,...][marks,...]
    Each column stored separately.

    GOOD:  SUM(marks) reads ONLY the marks pages —
           often 10-50x less I/O. Compresses far
           better, since a column holds similar
           values.
    BAD:   fetching one whole row touches every
           column's pages. Single-row writes are
           expensive.
─────────────────────────────────────────

Choosing
─────────────────────────────────────────
  Many small reads and writes of whole rows —
  an application backend
      ──► ROW store. Postgres, MySQL, SQLite.

  Scanning a few columns across enormous tables —
  analytics, reporting, dashboards
      ──► COLUMN store. ClickHouse, DuckDB,
          BigQuery, Parquet files.

  The rest of this curriculum assumes a row store,
  because that is what "a database" usually means.
  Recognising when your workload wants the other
  one is the valuable part.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • A disk read costs more than a hundred thousand comparisons, so databases optimise for pages touched rather than comparisons made — which changes which algorithms win.
  • I/O happens in fixed-size pages, so narrower rows mean fewer pages for the same scan, making SELECT * a performance decision.
  • Rows are addressed by slot rather than byte offset, which lets a row move within its page without invalidating every index pointing at it.
  • A full scan is the correct plan when reading a large fraction of a table, because sequential reads are far cheaper per page than random ones.

Concept Check

  1. Why is a row's address a slot number rather than a byte offset, and what would break otherwise?
  2. A table's average row grows from 100 to 800 bytes. What happens to the cost of a full scan, and why?
  3. Give a workload where a column store would substantially outperform a row store, and say why.

Next Chapter

→ Chapter 2: B+ Tree Indexes

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index