Storage & File Organization

Circular magnetic disks that spin at 5,400–15,000 RPM. Data is encoded magnetically on concentric circular tracks. Multiple platters share a common spindle.

Electromagnetic head that floats nanometres above the platter surface. One head per platter surface. All heads move together on a common arm — seeking one track moves all heads simultaneously.

A concentric circle on a platter. The outermost track is track 0. Each track is divided into sectors (typically 512 bytes or 4KB per sector). Data is written sector by sector along a track.

The set of tracks at the same radial position across all platters and both surfaces. Data on the same cylinder can be accessed without moving the arm — important for sequential multi-platter reads.

Time to move the read/write arm to the correct track. 3–12ms typical. This is the dominant cost of random disk access and the primary reason random I/O is so expensive.

Time waiting for the desired sector to rotate under the head after the arm has seeked. Average = half a rotation. At 7,200 RPM: 60s/7200 × 0.5 ≈ 4ms average.

Time to actually read/write the data once the head is positioned. Proportional to data size. At 150 MB/s, reading 8KB takes ~0.05ms — tiny compared to seek + rotational latency.

Seek time + Rotational latency + Transfer time. For a random 8KB read: ~8ms + ~4ms + 0.05ms ≈ 12ms. For sequential: only transfer time after the first seek, so ~0.05ms per 8KB page.

The simplest file organisation. Records are stored in no particular order — new records are inserted wherever free space exists. This is the default table storage in PostgreSQL and most relational databases. No assumptions are made about the physical ordering of rows.

When it wins: Heap files are the right default for most OLTP tables because writes are fast (no need to maintain physical ordering), and most read access goes through indexes (which provide the RID for direct page access). The lack of physical ordering only hurts for range scans without an index — and in a well-designed schema, range scans always use an index.

Records are physically stored in sorted order on a designated search key. This is the same as a clustered index on that key — the physical file order matches the index order. Implemented in MySQL InnoDB (primary key is always clustered) and achievable in PostgreSQL with CLUSTER.

When it wins: When the primary access pattern is range scans on the sort key — time-series data (WHERE date BETWEEN), ordered paginated results (ORDER BY id LIMIT 100), or any workload where related rows by key are always accessed together. Clustered indexes on the primary key also eliminate the heap fetch step — the data row IS the leaf node of the index.

ISAM is a historical file organisation that combines a sorted data file with a simple static index structure. The data pages are sorted and fixed. The index is a separate static structure (like a simplified B-tree but not self-balancing) pointing into the sorted data pages. Overflow pages handle insertions that don't fit in the original data pages.

ISAM was an important step in database history (IBM's earliest database products used it) but it has two critical limitations compared to B+ trees. First, the index is static — it does not rebalance when data grows, so overflow chains accumulate over time and performance degrades. Second, concurrent access requires locking entire leaf pages (no fine-grained record locking possible in the original design).

Modern databases do not use ISAM directly — it has been entirely superseded by B+ trees. It remains on GATE syllabi as historical context and as a contrast case that explains why B+ trees were developed.

This distinction is critical and frequently confused. A clustered file stores records from related tables (those frequently joined) physically together in the same pages — not to be confused with a clustered index. An unclustered file stores each table's records in separate pages.

// CLUSTERED FILE: orders and their order_items stored interleaved by order_id
// Page 1: [order O001 header] [O001 item 1] [O001 item 2] [O001 item 3]
// Page 2: [order O002 header] [O002 item 1] [O002 item 2]
// Page 3: [order O003 header] [O003 item 1] [O003 item 2] [O003 item 3] [O003 item 4]

// BENEFIT: JOIN of orders and order_items is extremely fast
// Query: SELECT * FROM orders o JOIN order_items oi ON o.order_id = oi.order_id
// With clustered file: reading the order page ALSO reads its items — 1 page read per order
// Without: reading order page + separate order_items pages per order = many more reads

// UNCLUSTERED FILE (separate tables, standard):
// orders file:      [O001] [O002] [O003] [O004] ...
// order_items file: [O001_i1] [O001_i2] [O002_i1] ...
// JOIN requires: read from orders file + read from order_items file = separate I/Os

// PostgreSQL does NOT support clustered files (interleaved table storage).
// MySQL InnoDB uses clustered primary key (data stored in PK order) but not multi-table.
// Oracle supports clustered tables.
// Most widely available implementation: MySQL InnoDB clustered PK index.

Every record has exactly the same size. Fields are stored at fixed, predetermined byte offsets within the record. To access field N, compute byte_offset = sum of preceding field sizes.

Records have different sizes depending on actual data values. VARCHAR, TEXT, and BLOB columns are variable-length. The record stores both data and metadata about field boundaries.

Evict the page that was least recently accessed. The intuition: if a page hasn't been used in a long time, it is unlikely to be used soon. Tracks a timestamp or order of last access for every frame.

Implementation: Maintain a doubly-linked list of frames ordered by last access time. On each access, move the frame to the head of the list. Evict from the tail. O(1) per access with a hashmap for frame lookup.

The LRU-K problem (Sequential Flooding): A full table scan reads every page in the table exactly once. With basic LRU, these scan pages flood the buffer pool, evicting the frequently-used index and "hot" pages that are accessed constantly. After the scan, those hot pages must be re-read from disk. The scan, which needed each page only once, has destroyed the working set.

An efficient approximation of LRU using a circular buffer with a single "clock hand" pointer. Each frame has a reference bit (0 or 1). When a frame is accessed: set reference bit to 1. When the clock hand sweeps to a frame with bit=1: reset it to 0 and advance (give it a second chance). When the hand reaches a frame with bit=0: evict it.

// CLOCK ALGORITHM:
// frames = circular array of buffer frames
// hand = current position of clock hand
// ref_bit[i] = 0 or 1 for each frame

// On PAGE ACCESS (hit or after loading):
ref_bit[frame] = 1  // mark recently used

// On EVICTION NEEDED:
while True:
    if pin_count[hand] > 0:
        hand = (hand + 1) % total_frames  // skip pinned frames
    elif ref_bit[hand] == 1:
        ref_bit[hand] = 0                 // give second chance
        hand = (hand + 1) % total_frames
    else:
        // ref_bit[hand] == 0: evict this frame
        if dirty_bit[hand]:
            write frame to disk
        load new page into hand's frame
        ref_bit[hand] = 1
        break

// ADVANTAGE: O(1) amortised, much lower overhead than true LRU
// (no linked list manipulation on every access)
// USED BY: PostgreSQL's buffer pool uses a clock-sweep algorithm

Evict the most recently used page instead of the least recently used. This sounds counterintuitive but is optimal for sequential table scans — a page just scanned will not be needed again during the scan, so evicting it immediately frees space for the next page.

When to use MRU: specifically for pages being read by a sequential scan. Modern databases use "buffer ring" strategies where sequential scans use a small private ring buffer (a few frames cycling with MRU) instead of the main buffer pool — preventing scan pages from evicting the working set.

-- PostgreSQL buffer ring for sequential scans:
-- A sequential scan larger than 1/4 of shared_buffers gets a "bulk read" ring
-- The ring has only ~256KB (32 pages) of buffer frames
-- Scan pages cycle through this ring — never polluting the main buffer pool
-- The main buffer pool's working set is preserved

-- This is why a large table scan doesn't destroy buffer pool performance
-- for concurrent OLTP queries in PostgreSQL.

-- Check if a scan is using the ring strategy:
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM orders;
-- "Buffers: shared hit=X read=Y"
-- If Y is large but hit rate for other queries is still high:
-- The ring strategy is working correctly

LRU-K tracks the timestamps of the last K accesses to each page (not just the most recent). The eviction candidate is the page whose K-th most recent access was furthest in the past. With K=2, pages that have only been accessed once (like scan pages) have no second access timestamp and are treated as if their second access was infinitely far in the past — making them the first eviction candidates. Frequently accessed pages (many recent accesses) are protected.

LRU-2 is the most common choice. It effectively solves the sequential flooding problem: scan pages (accessed once) are immediately vulnerable to eviction. Index root pages (accessed thousands of times per second) have very recent K-th access timestamps and are practically never evicted.

# ─────────────────────────────────────────────────────────────────
# MEMORY SETTINGS
# ─────────────────────────────────────────────────────────────────

# Buffer pool — the most important setting. Set to 25% of total RAM.
# On a 64GB RAM server:
shared_buffers = 16GB

# Per-sort/hash work memory. Affects sort, hash join, hash aggregate.
# Set to: RAM_for_connections / (max_connections × 3)
# On 64GB server, 100 connections: 64GB × 0.75 / (100 × 3) ≈ 160MB
work_mem = 128MB
# WARNING: each query node (sort, hash join) gets work_mem
# A complex query with 5 operations uses 5 × 128MB = 640MB

# Memory for VACUUM and CREATE INDEX operations
maintenance_work_mem = 2GB

# OS cache (effective_cache_size tells the planner how much RAM is available
# for caching, including OS page cache + shared_buffers)
effective_cache_size = 48GB  # shared_buffers + OS cache estimate

# ─────────────────────────────────────────────────────────────────
# STORAGE TYPE SETTINGS
# ─────────────────────────────────────────────────────────────────

# For NVMe SSD (random I/O almost as fast as sequential):
random_page_cost = 1.1    # default is 4.0 (for spinning disks)
seq_page_cost = 1.0
# With random_page_cost = 1.1: planner will aggressively use indexes
# With random_page_cost = 4.0: planner prefers seq scans for lower selectivity

# ─────────────────────────────────────────────────────────────────
# WRITE-AHEAD LOG (WAL) SETTINGS
# ─────────────────────────────────────────────────────────────────

# Durability vs performance trade-off:
synchronous_commit = on   # default: durable, ~1-10ms added per commit
# For non-critical writes (logging, analytics): off saves latency at cost of
# up to synchronous_commit_delay ms of data on crash

# WAL buffer (in-memory buffer before WAL is flushed to disk)
wal_buffers = 64MB  # default: -1 (auto = 1/32 of shared_buffers, max 64MB)

# ─────────────────────────────────────────────────────────────────
# CHECKPOINT SETTINGS
# ─────────────────────────────────────────────────────────────────

# Spread checkpoint I/O over this fraction of the checkpoint interval:
checkpoint_completion_target = 0.9  # write dirty pages over 90% of interval
# Prevents I/O spike at checkpoint time

checkpoint_timeout = 15min   # maximum time between checkpoints
max_wal_size = 4GB           # trigger checkpoint if WAL grows past this

# ─────────────────────────────────────────────────────────────────
# AUTOVACUUM (MVCC dead tuple cleanup)
# ─────────────────────────────────────────────────────────────────
autovacuum = on
autovacuum_vacuum_scale_factor = 0.1    # vacuum when 10% of rows are dead
autovacuum_analyze_scale_factor = 0.05  # analyze when 5% of rows changed
autovacuum_vacuum_cost_delay = 2ms      # IO throttle for autovacuum

# ─────────────────────────────────────────────────────────────────
# MONITORING COMMANDS
# ─────────────────────────────────────────────────────────────────
-- Check buffer pool hit rate:
SELECT ROUND(100 * sum(blks_hit) / NULLIF(sum(blks_hit) + sum(blks_read), 0), 2)
AS hit_rate_pct FROM pg_stat_database;
-- Target: > 99% for OLTP workloads

-- Check pages currently in buffer pool:
SELECT c.relname, count(*) AS pages_in_pool,
       pg_size_pretty(count(*) * 8192) AS size_in_pool
FROM pg_buffercache b
JOIN pg_class c ON b.relfilenode = c.relfilenode
GROUP BY c.relname ORDER BY pages_in_pool DESC LIMIT 20;

Disk I/O operates in fixed-size blocks — the hardware reads or writes a minimum of one block at a time (typically 512 bytes to 4KB). Reading a single byte requires reading an entire block containing it. Database pages are sized to match or exceed the disk block size (PostgreSQL uses 8KB, MySQL InnoDB uses 16KB) so that each I/O operation is maximally useful. Reading one page brings in approximately 40 rows (for a 200-byte average row). If rows were accessed individually, the disk would need one I/O per row — 40× more I/O for the same data. Pages are also the unit of buffer pool management — it is practical to track 1 million 8KB frames in a buffer pool, whereas tracking 40 million individual row locations would be impractical.

A dirty page is a buffer pool frame that has been modified since it was last read from disk — its in-memory content is newer than the disk copy. Before a dirty page can be evicted from the buffer pool, its content must be written back to disk (or at least its changes recorded in the WAL) to preserve durability. A pinned page is a frame that is currently in use by one or more active threads — its pin count is greater than zero. A pinned frame cannot be evicted regardless of its dirty status, because evicting it while a thread is reading from or writing to it would cause data corruption. The pin count is incremented when a thread starts using a page and decremented when it finishes. A frame can be both dirty (modified) and pinned (in use) simultaneously.

An index scan on a non-clustered index involves two steps: read the index to get the row ID, then fetch the actual row from the heap (a random I/O). If the query returns many rows, each row fetch is a separate random disk access — on spinning disk each takes ~8-12ms. A sequential scan reads the entire table in physical page order, exploiting sequential I/O (which is 200-300× faster than random I/O per unit of data on spinning disk). The crossover point: when more than approximately 15-20% of the table rows match the query, a sequential scan reads less total data (all rows read sequentially) vs the index scan (random heap fetches for each matching row). The database query optimiser computes this crossover using the table's statistics (row count, selectivity estimates) and the cost parameters (random_page_cost vs seq_page_cost). Setting random_page_cost = 1.1 for SSDs (where random I/O is much cheaper) causes the optimiser to prefer index scans at much lower selectivity thresholds.

LRU sequential flooding occurs when a full table scan fills the buffer pool with pages that are each needed only once — while evicting the frequently-accessed "hot" pages (index root nodes, popular rows) that were providing high buffer pool hit rates. After the scan, all those hot pages must be re-read from disk, causing a spike in disk I/O and query latency. Databases solve this several ways. PostgreSQL uses a "buffer ring" strategy: sequential scans larger than 1/4 of shared_buffers use a small dedicated ring of ~32 pages with MRU replacement. Scan pages cycle through this ring and never touch the main buffer pool. LRU-K (especially LRU-2) is another solution: pages accessed only once (scan pages) have no second access timestamp and are immediately eligible for eviction, while frequently accessed pages (with many recent accesses) are protected. SQL Server uses a "stolen" buffer pool strategy where sequential scan allocations are tracked separately and are first candidates for eviction.

Choose columnar storage for analytical (OLAP) workloads that scan a small number of columns across a large number of rows — aggregations, GROUP BY, time-series analysis, reporting. The benefits are: (1) I/O reduction — only the needed columns are read, avoiding irrelevant columns (a query on 3 of 20 columns reads 85% less data). (2) Better compression — a column file contains one data type, enabling run-length encoding, delta encoding, and dictionary encoding that can achieve 5-10× compression ratios, further reducing I/O. (3) SIMD vectorisation — processors can apply the same operation to multiple values simultaneously when they are packed contiguously with the same type. Choose row storage for OLTP workloads that access complete rows — point lookups by primary key, inserts, updates, deletes. Inserting one row into a column store requires updating all column files. Use both: row store for transactional data, column store for the analytical data warehouse built from it.