Database Internals

Same query, same index, same data shape. Staging: 2ms. Production: 800ms. Why? The answer is the buffer pool. In staging, your 8 GB buffer pool easily holds the entire index and most of the hot data pages. In production, 500 million rows means the index alone is 12 GB — larger than your buffer pool. Pages are constantly being evictedWhen the buffer pool is full and needs to load a new page, it removes (evicts) the least-recently-used page to make room. If that evicted page was modified (dirty), it must be written to disk first. and re-read from disk.

Run this in PostgreSQL to see exactly what's in your buffer pool right now:

-- See what's in the buffer pool RIGHT NOW
-- Each row = one 8KB page in shared memory
SELECT c.relname AS table_name,
       count(*) AS pages_in_buffer,
       pg_size_pretty(count(*) * 8192) AS size_in_buffer,
       round(100.0 * count(*) / (SELECT setting::int
         FROM pg_settings WHERE name = 'shared_buffers'), 2) AS pct_of_pool
FROM pg_buffercache b
JOIN pg_class c ON b.relfilenode = c.relfilenode
WHERE b.reldatabase = (SELECT oid FROM pg_database WHERE datname = current_database())
GROUP BY c.relname
ORDER BY pages_in_buffer DESC
LIMIT 10;

This shows you exactly which tables and indexes are hogging your buffer pool. If your users table is taking 60% and your index is fighting for the remaining 40%, you've found your bottleneck. Without understanding the buffer pool, you'd waste hours profiling the query itself — which isn't the problem.

A power outage took down your database server. When it came back, you discovered that the last 30 seconds of committed transactions were missing. Users who got a "success" response had their data vanish. How is that possible if the database said it committed?

The answer lies in the WAL (Write-Ahead Log) and how fsyncA system call that forces the operating system to flush its file buffers to the physical storage device. Without fsync, data that the OS says is "written" might actually still be in an OS cache in RAM — vulnerable to power loss. works. Some configurations delay flushing the WAL to disk for performance (synchronous_commit = off in PostgreSQL). The database told the client "committed" when it wrote to the WAL in memory, but the WAL hadn't been flushed to disk yet. Power dies → WAL in memory is gone → those transactions are lost.

Without understanding the WAL, you'd never know this setting existed, let alone the trade-off: synchronous_commit = off makes commits ~5× faster but risks losing the last few hundred milliseconds of data on crash. For a logging system? Fine. For a payment system? Catastrophic.

A B+ tree is the data structure behind the vast majority of relational database indexes. The name sounds intimidating, but the idea is simple: it's a tree where each node can have hundreds of children instead of just two. This makes the tree incredibly shallow — even with billions of entries.

Here's the key number: fanout. Fanout means "how many children does each node have." In a B+ tree stored in 8 KB pages, if each key is 8 bytes and each pointer is 6 bytes, you can fit about (8192 - header) ÷ (8 + 6) ≈ 500 children per node. That's the magic.

The math is beautiful. Level 1 (root): 1 node → points to 500 children. Level 2: 500 nodes → each points to 500 = 250,000 entries. Level 3: 250,000 nodes → each points to 500 = 125,000,000 entries. Level 4: 125,000,000 × 500 = 62.5 billion entries. So for 500 million rows, you need 3 levels — maybe 4 if the pages aren't perfectly full. That's why the EXPLAIN showed Buffers: shared hit=4: one page per level, plus one to fetch the actual row from the heap.

You can inspect a real B+ tree index in PostgreSQL:

-- See the internal structure of your B+ tree index
-- Requires pageinspect extension
SELECT * FROM bt_metap('idx_users_email');
-- magic  | version | root | level | fastroot | fastlevel
-- 340322 |       4 |    3 |     3 |        3 |         3
--                          ↑ root is page 3
--                                  ↑ tree has 3 levels!

-- Look at stats of any internal page
SELECT * FROM bt_page_stats('idx_users_email', 3);  -- page 3 = root
-- blkno | type | live_items | dead_items | avg_item_size | free_size
-- 3     | r    | 487        | 0          | 15            | 508
--        ↑ r = root    ↑ 487 child pointers (close to our 500 estimate!)

Critical detail: leaf nodes are linked. B+ tree leaf nodes form a doubly-linked listEach leaf page has a pointer to the next leaf page AND the previous one. This means once you find a starting leaf (e.g., for email > 'a' and email < 'b'), you can just follow the forward pointers to scan through all matching entries without ever going back up the tree.. This is what makes range queries fast: WHERE email BETWEEN 'a' AND 'b' finds the first leaf, then follows the linked list forward. No need to traverse the tree for each row.

Every database has a section of RAM reserved for caching pages — this is the buffer pool. In PostgreSQL, it's controlled by the shared_buffers setting (typically 25% of system RAM). In MySQL/InnoDB, it's innodb_buffer_pool_size (typically 70-80% of RAM).

The buffer pool is the single most important performance tuning knob. When a query needs a page, the database checks the buffer pool first. If the page is there (buffer hitThe requested page was found in the buffer pool (RAM). Costs about 0.1 microseconds. The EXPLAIN output shows this as "shared hit=N".), great — that's a memory access (~100 nanoseconds). If not (buffer missThe requested page was NOT in the buffer pool and had to be read from disk. Costs about 100 microseconds for SSD, 10 milliseconds for HDD. The EXPLAIN output shows this as "shared read=N".), the database must read the page from disk (~100 microseconds on SSD) — that's 1,000× slower.

-- What's your buffer pool hit ratio?
-- (Should be > 99% for OLTP workloads)
SELECT
  sum(blks_hit) AS hits,
  sum(blks_read) AS misses,
  round(100.0 * sum(blks_hit) / nullif(sum(blks_hit) + sum(blks_read), 0), 2)
    AS hit_ratio_pct
FROM pg_stat_database
WHERE datname = current_database();
-- hits: 847,293,104 | misses: 2,341,987 | hit_ratio_pct: 99.72%

-- If hit_ratio < 95%, your buffer pool is too small.
-- Pages are being evicted and re-read constantly.

When the buffer pool is full and a new page needs to be loaded, the database evicts the least-recently-used page (using a clock-sweep algorithm in PostgreSQL, LRU in InnoDB). If the evicted page was dirtyA page that has been modified in the buffer pool but not yet written to disk. Evicting a dirty page requires writing it to disk first (a "flush"), which adds I/O overhead. (modified but not yet written to disk), it must be flushed to disk first.

Remember the "fast in staging, slow in production" problem from Section 4? Now you can diagnose it: if your index is 12 GB but your buffer pool is 8 GB, the B+ tree's upper levels compete with data pages for space. The root page stays cached (it's accessed on every query), but internal and leaf pages get evicted constantly — turning a 4-page buffer hit into a 4-page disk read.

Here's a scary scenario. You INSERT a row. The database modifies the page in the buffer pool (RAM). It returns "INSERT 0 1" — success. Then the power goes out. The modified page was in RAM and never written to disk. Is your data gone?

No — because of the WAL. Before the database modifies any page in the buffer pool, it first writes a description of the change to a sequential log file on disk. This log is the Write-Ahead Log. The rule is absolute: the WAL record hits disk before the client gets a success response. If the server crashes, the database replays the WAL on startup — re-applying any changes that were in the buffer pool but hadn't been written to the actual data files yet.

Sequential writes are much faster than random writes — 10-100× faster on HDDs, 2-5× faster even on SSDs. So the WAL gives you the best of both worlds: the durability of writing to disk immediately (via sequential WAL writes) and the performance of batching random data page writes (dirty pages are flushed in the background by the checkpointerA background PostgreSQL process that periodically writes all dirty pages from the buffer pool to disk and records a "checkpoint" in the WAL. After a checkpoint, WAL records before that point are no longer needed for crash recovery and can be recycled.).

# See actual WAL records — what was written when you did an INSERT
# (Run as postgres user on the server)
pg_waldump --start=0/1A8E000 --end=0/1A8F000 /var/lib/postgresql/14/main/pg_wal/000000010000000000000001

# Output looks like:
# rmgr: Heap    len (rec/tot): 59/211  tx: 7843291
#   desc: INSERT off 12, blkref #0: rel 1663/16384/16389 blk 7832491
#         ↑                                              ↑
#         inserted at item 12 on the page       this is heap page 7,832,491!
#
# rmgr: Btree   len (rec/tot): 64/64   tx: 7843291
#   desc: INSERT_LEAF off 143, blkref #0: rel 1663/16384/16392 blk 94021
#         ↑                                                    ↑
#         B-tree leaf insert                     index page 94,021

Look at that output. One INSERT caused TWO WAL records — one for the heap page (the actual data) and one for the B-tree leaf page (the index). Every indexed column adds another WAL record per write. This is the write amplification cost of indexes — and it's why the WAL is often the bottleneck in write-heavy systems.

Here's a question that seems impossible: how can two transactions see different versions of the same row at the same time? Transaction A is reading Alice's balance while Transaction B is updating it. A sees the old balance, B writes the new one, and neither blocks the other. How?

The answer is MVCCMulti-Version Concurrency Control — instead of using locks to prevent concurrent access to the same row, the database keeps multiple versions of each row simultaneously. Each transaction sees the version that was current when it started. (Multi-Version Concurrency Control). Instead of locking a row when someone reads it, the database keeps multiple versions of the row simultaneously. Each version is tagged with which transaction created it and which transaction deleted it.

In PostgreSQL, every row (tuple) on a page has two hidden columns: xmin (the transaction ID that created this version) and xmax (the transaction ID that deleted/updated it — 0 if it's still alive). You can see them:

-- See the hidden MVCC columns on your rows
SELECT xmin, xmax, ctid, email FROM users WHERE email = 'alice@example.com';
-- xmin     | xmax | ctid          | email
-- 7843291  | 0    | (7832491,12) | alice@example.com
--  ↑         ↑       ↑
--  created   alive   page 7,832,491, item 12 on that page
--  by tx             (this is the physical location!)
--  7843291

-- Now UPDATE the row:
UPDATE users SET name = 'Alice Smith' WHERE email = 'alice@example.com';

-- Check again:
SELECT xmin, xmax, ctid, email FROM users WHERE email = 'alice@example.com';
-- xmin     | xmax | ctid          | email
-- 7843310  | 0    | (7832491,39) | alice@example.com
--  ↑                  ↑
--  NEW tx ID          DIFFERENT item on the page!

-- The old version (xmin=7843291) is still on the page
-- but with xmax=7843310. Running transactions that
-- started before tx 7843310 can still see the old version.

Notice the ctid changed — that means the UPDATE created a new copy of the row at a different position on the page. The old version is still there, marked as dead. This is PostgreSQL's MVCC in action: an UPDATE is really a DELETE + INSERT at the storage layer. The old version stays around until VACUUM removes it.

MySQL/InnoDB handles MVCC differently. Instead of creating new row versions in the main table pages, InnoDB stores old versions in a separate undo logA separate storage area where InnoDB keeps the previous versions of modified rows. When a transaction needs to see an old version, the database follows a chain of undo records backwards to reconstruct what the row looked like at the start of that transaction.. When a transaction needs to see an old version, it follows the undo chain backwards. This keeps the main table pages clean but makes long-running transactions expensive (the undo log grows and old versions can't be purged).

We've touched on this difference in Section 6, but it's important enough to explore in detail. PostgreSQL and MySQL/InnoDB store table data in fundamentally different ways, and this affects everything from INSERT speed to secondary index size.

Heap storage (PostgreSQL): Rows are stored in an unordered heap file. New rows go wherever there's free space. The primary key index is just another B+ tree that points to the physical location (page number + item offset) of each row. This means:

• Inserts are always fast — just find a page with space and put the row there
• Primary key range scans require random I/O — the rows aren't physically sorted
• Secondary indexes are the same size as the primary index (both store physical locations)
• UPDATEs create new row versions that might be on a different page (HOT updates avoid this when possible)

Clustered storage (MySQL/InnoDB): The table data IS the primary key B+ tree. Rows are physically sorted by PK in the leaf pages. This means:

• PK range scans are blazing fast — rows are contiguous on disk
• Random PK inserts (UUIDs) cause page splits — terrible performance
• Sequential PK inserts (auto-increment) always append to the end — great performance
• Secondary indexes store the PK value (not a physical pointer), so they're smaller but require a second lookup

Everything we've discussed assumes data lives on disk and gets cached in the buffer pool. But what if the entire dataset fits in RAM? Then you eliminate disk I/O completely, and the data structures can be optimized for memory access patterns instead of disk page access patterns.

Redis internals: Redis keeps all data in memory and uses data structures optimized for RAM, not disk. Instead of B+ trees, Redis uses hash tablesA data structure that maps keys to values using a hash function. Average O(1) lookups. Redis uses a hash table as its global keyspace — every key you SET is stored in this hash table. for key-value lookups (O(1) average), skip lists for sorted sets (O(log n) like a tree but simpler), and ziplistA compact, memory-efficient encoding used by Redis for small lists, hashes, and sorted sets. Instead of using pointers (8 bytes each on 64-bit), entries are packed tightly in a contiguous block of memory. Saves significant RAM for small datasets but becomes slow for large datasets due to O(n) operations./listpack for small collections (trading CPU for memory savings). Redis uses jemalloc as its memory allocator to minimize fragmentation.

But "in-memory" doesn't mean "data disappears on restart." Redis offers two persistence options: RDB snapshots (periodic full dumps to disk — fast recovery but you lose data since the last snapshot) and AOF (Append-Only File — like a WAL, logs every write command — slower recovery but less data loss). You can use both together for the best of both worlds.

VoltDB takes a different approach: it's a full SQL relational database that lives entirely in memory. It uses no buffer pool at all — every transaction operates directly on in-memory data. For durability, it uses command logging (similar to WAL) and K-safety replication (synchronous copies to other nodes). VoltDB achieves millions of SQL transactions per second on a single node because there's zero disk I/O in the critical path.

In 2016, Uber published a blog post titled "Why Uber Engineering Switched from Postgres to MySQL." The reason came down to one internal detail: how secondary indexes store row pointers.

In PostgreSQL, every index entry points to a physical location on disk — a (page_number, offset) tuple called a ctidIn PostgreSQL, every row has a ctid (current tuple identifier) that specifies its physical location: (page_number, item_offset). Secondary indexes store this ctid to find rows. The problem: when VACUUM moves a row, ALL indexes pointing to that row must be updated.. When VACUUM compacts a table and moves rows to new locations, every single index pointing to that row must be updated — that's write amplification proportional to the number of indexes. Uber's trip tables had dozens of indexes, so a single VACUUM pass triggered massive cascading index updates.

InnoDB's clustered index solves this differently. Secondary indexes store the primary key value, not a physical location. When a row moves, secondary indexes don't change — only the clustered index (which IS the table, sorted by PK) needs updating. For Uber's workload — wide tables with many indexes and heavy UPDATE traffic — this meant 10x less write amplification during maintenance.

Facebook stores petabytes of social graph data in MySQL. Their problem: InnoDB's B+ tree storage wastes space. A B+ tree page targets ~70% fill factor after splits, meaning 30% of every page is empty. For a 10 TB database, that's 3 TB of wasted disk. Multiply by thousands of shards and it adds up to millions of dollars in SSDs.

The math: 30 PB × 30% waste = 9 PB of overhead with InnoDB. With LSM at ~90% utilization, overhead drops to ~3 PB. That's a 6 PB saving. At $0.10/GB/month: 6,000,000 GB × $0.10 = $600,000/month in storage costs alone. Facebook built MyRocks — MySQL with RocksDB as the storage engine — and achieved the predicted ~50% space reduction. The trade-off: read latency P99 increased from 2ms to 8ms because LSM reads might check multiple levels. For their write-heavy social graph, that was acceptable.

The key compaction tuning: Facebook uses leveled compaction with a custom rate limiter that caps compaction I/O at 100 MB/s during peak hours and allows 500 MB/s during off-peak. Without rate limiting, compaction storms can consume all disk bandwidth and make foreground queries timeout.

There are roughly 1 trillion active SQLite databases in the world right now. Every Android phone has dozens of them. Every iPhone. Every Mac. Every Chrome browser, every Firefox browser, every Electron app. It's in every Boeing 787 and every Airbus A350. SQLite is not a client-server database — it's a library linked directly into your application, reading and writing a single file on disk.

Internally, SQLite uses the same fundamentals: B+ tree pages (4 KB default), a WAL for crash recovery, and an in-process page cache. But with one crucial design constraint — single writer. Only one connection can write at a time (readers never block). This eliminates all the concurrency complexity (MVCC version chains, lock managers, deadlock detection) that makes PostgreSQL and MySQL so complex. For embedded use cases — a phone app's local storage, a browser's IndexedDB, an IoT sensor's log — you don't need concurrent writers. You need a reliable, zero-configuration, single-file database. SQLite is 150,000 lines of C with 100% branch coverage in its test suite — one of the most tested software projects in history.