What is the fundamental architectural difference between a B-Tree and a B+ Tree in database storage engines?

In a classic B-Tree, both internal (routing) nodes and leaf nodes store full data records (or pointers to heap tuples) alongside search keys. This severely limits the branching factor (fanout) of internal nodes because data records consume substantial space, requiring a deeper tree and more disk I/O per search. In contrast, a B+ Tree stores data records (or row pointers) EXCLUSIVELY in the leaf nodes; internal nodes store only discriminant routing keys and child page pointers. This maximizes the fanout of internal nodes (often 200 to 500 keys per 8KB page), allowing billions of rows to be indexed in a tree of height 3 or 4. Furthermore, all leaf nodes in a B+ Tree are linked together via bidirectional pointers (doubly linked list), allowing range queries (e.g. WHERE id BETWEEN 100 AND 500) to execute as an initial point lookup followed by fast, sequential leaf page traversal without traversing back up through parent nodes.

How does node splitting occur in a B+ Tree and why does it cause Write Amplification and disk fragmentation?

When an insert occurs into a leaf page that already contains the maximum allowable keys (order M), the page undergoes a split: (1) The keys are partitioned into two half-full pages (typically floor(M/2) keys each); (2) The median routing key is copied or moved up into the parent node; (3) Sibling pointers are updated to link the new page into the leaf chain; (4) If the parent node is also full, the split cascades recursively up the tree, potentially creating a new root and increasing the tree height by 1. Node splitting causes Write Amplification because inserting a small 20-byte key requires writing multiple full 8KB or 16KB pages to disk and appending WAL records. Furthermore, splits on random insert workloads result in 50% average page fill factors, doubling storage footprint and halving buffer pool cache efficiency.

What is the structural difference between MySQL InnoDB Clustered Index and PostgreSQL Heap-Organized Tables with secondary indexes?

MySQL InnoDB is an index-organized table: the table IS the primary key B+ Tree. The leaf nodes of the primary clustered index directly contain the full row data columns. Secondary indexes in InnoDB store the primary key value as their leaf payload, requiring a secondary lookup (bookmark lookup) to traverse the clustered index unless all requested columns are covered by the secondary index. In contrast, PostgreSQL uses heap-organized storage: table data rows are stored in unordered heap pages. All indexes (primary and secondary) are separate B+ Trees whose leaf nodes store 6-byte ItemPointers (ctid = block_number, item_offset) pointing to the physical heap page. PostgreSQL utilizes Heap-Only Tuples (HOT) to prevent secondary index write amplification when non-indexed columns are updated on a page with free space.

How does Fill Factor tuning (e.g. 70% vs 90% vs 100%) trade write performance against read scan speed?

Fill Factor designates the percentage of each 8KB database page reserved for data during initial index creation or VACUUM/OPTIMIZE operations: (1) A 100% Fill Factor packs pages completely with zero wasted space, maximizing sequential scan performance and buffer pool memory density for read-heavy or static historical datasets. However, any subsequent insert or update instantly forces an expensive 50/50 page split. (2) A 70% to 80% Fill Factor reserves 20% to 30% of each page as free space ("slack space"). When random writes and updates arrive, new tuples fit into existing pages without triggering immediate splits, reducing lock contention and disk write amplification at the expense of requiring 25% more disk space and buffer cache memory.

What is the Slotted Page architecture and how does it prevent pointer invalidation during in-page tuple defragmentation?

A Slotted Page (used in PostgreSQL, SQLite, and InnoDB) divides an 8KB disk page into three regions: (1) A fixed-size page header at the start of the page; (2) An array of 4-byte line pointers (ItemId array) growing forward from the header; (3) Variable-length tuple data growing backward from the end of the page. External indexes reference data using a logical Item Pointer (Tuple ID = Page Number + Slot Index). When a row is updated or deleted, the storage engine can shift bytes inside the page to reclaim fragmented holes and update the internal 4-byte slot offset. The external index pointer (Page X, Slot Y) remains completely unchanged, avoiding massive index updates across millions of secondary index entries when rows change size.

Why do LSM Trees offer higher write throughput than B+ Trees, and what trade-offs do they introduce in read latency?

B+ Trees perform random, in-place page writes: updating a 30-byte field modifies an 8KB or 16KB page, requiring full-page flushes to storage and generating high Write Amplification Factors (WAF = 10x to 50x) that can saturate disk write queues. Log-Structured Merge (LSM) Trees (RocksDB, Cassandra, ClickHouse) eliminate random in-place updates: all writes are appended sequentially to a memory buffer (MemTable) and a Write-Ahead Log. When the MemTable is full, it is flushed sequentially to an immutable SSTable file on disk. While LSM trees achieve 5x to 10x higher write throughput, they introduce Read Amplification: finding a key may require checking multiple SSTable levels and Bloom filters, causing higher P99 read latency compared to the deterministic O(log N) single-page traversal of a B+ Tree.

Verified Specification | Standardized Formulas | Instant Precision

Secure & Private (Zero Data Retention) Free Access • No Sign-Up

B+ Tree Internals Slotted Page Anatomy WAF & IOPS Cost InnoDB vs nbtree

B-Tree, B+ Tree & Storage Engine Internals Studio

Architect production database storage engines and indexing algorithms: simulate live B+ Tree node splitting and range scans in memory, inspect 8KB slotted page anatomy and line pointers, model Write Amplification Factors (WAF) and SSD endurance degradation, compare PostgreSQL nbtree vs InnoDB clustered index, and synthesize production Go and Rust storage code.

3 levels

B+ Tree Depth

256 keys

Page Fanout / Node

32.0x

Write Amplification (WAF)

1.42 GB

Index Footprint on Disk

Interactive In-Memory B+ Tree Visualizer

Insert keys, observe automatic node splitting, rebalancing, and pointer chaining.

Order (M):

■ Blue: Internal Routing Nodes (Keys Only) ■ Green: Leaf Nodes (Payloads + Linked List Chain)

PostgreSQL & SQLite 8KB Slotted Page Anatomy

Inspect how variable-length row data and fixed-size line pointers share physical 8,192-byte disk pages:

+-------------------------------------------------------------------------+ 0 bytes (Top of Page) | PageHeaderData (24 bytes) | | - pd_lsn (8B): Last Write-Ahead Log sequence number | | - pd_checksum (2B): Page integrity checksum | | - pd_flags (2B): Page state flags | | - pd_lower (2B): Byte offset to end of line pointers (grows downward) | | - pd_upper (2B): Byte offset to start of tuple data (grows upward) | | - pd_special (2B): Byte offset to special B-tree space | +-------------------------------------------------------------------------+ 24 bytes | Line Pointer Array: ItemIdData [4 bytes per tuple] | | [Slot 0: offset=8096, len=96] | [Slot 1: offset=7980, len=116] ... | ===> Grows DOWNWARD +-------------------------------------------------------------------------+ pd_lower | | | FREE SPACE HOLE | | (Reclaimed dynamically during in-page defragmentation) | | | +-------------------------------------------------------------------------+ pd_upper | Tuple 2 Data Storage (116 bytes) | <=== Grows UPWARD +-------------------------------------------------------------------------+ 7980 bytes | Tuple 1 Data Storage (96 bytes) | +-------------------------------------------------------------------------+ 8096 bytes | Special Space: BTPageOpaqueData (16 bytes) | | - btpo_prev (4B), btpo_next (4B) [Sibling Doubly-Linked Pointers] | | - btpo_level (2B), btpo_flags (2B) [Leaf vs Internal Flag] | +-------------------------------------------------------------------------+ 8192 bytes (End of Page)

Why Line Pointers Guarantee Immutability: When an index stores a reference to a table row, it stores (Block Number, Slot ID) rather than the physical byte offset. If a tuple expands or is defragmented inside the page, the database moves the bytes around in the bottom region and simply updates the 2-byte offset in the Line Pointer array. The external index never needs updating!

Write Amplification Factor (WAF) & SSD Endurance Calculator

Quantify disk write magnification, IOPS saturation, and NVMe SSD flash wear caused by random B+ Tree page updates:

Total Database Records: 50,000,000

Average Row Payload Size: 128 bytes

Target Fill Factor: 75%

Database Page Block Size

Random Write Throughput (Updates / Sec)

Storage Engine Architecture Metrics

Total Table Size on Disk

8.53 GB

Index Size on Disk

1.60 GB

Estimated B+ Tree Height

3 levels

B+ Tree WAF Factor

64.0x

Disk Write Bandwidth

9.83 MB/s

Annual NVMe Flash Wear

310 TBW / yr

Enterprise Storage Engine Index Architecture Matrix

Compare the underlying storage architectures across modern database engines:

Engine	Primary Table Layout	Secondary Index Pointers	Page Size	MVCC Mechanism
PostgreSQL (nbtree)	Heap-Organized Pages (Unordered)	ctid (6-byte Block + Slot ItemID)	8 KB (Compile-time tunable)	Tuple header flags (`t_xmin`, `t_xmax`). HOT optimization avoids index updates.
MySQL (InnoDB)	Clustered Index (B+ Tree contains rows)	Primary Key value (forces bookmark lookup)	16 KB (Default)	Undo Logs + Rollback Segment (`DB_TRX_ID`, `DB_ROLL_PTR`).
SQLite	intkey B-Tree (RowID is key)	RowID integer	4 KB (Default)	Write-Ahead Log (WAL) frame index or rollback journal.
MongoDB WiredTiger	B-Tree with hazard pointers	Record ID / B-Tree Leaf	4 KB to 64 KB configurable	In-memory transaction update chains + snapshot isolation.

Production Storage Engine Implementations

// Select an artifact above

B-Tree, B+ Tree & Storage Engine Internals Studio

Interactive In-Memory B+ Tree Visualizer

PostgreSQL & SQLite 8KB Slotted Page Anatomy

Write Amplification Factor (WAF) & SSD Endurance Calculator

Storage Engine Architecture Metrics

Enterprise Storage Engine Index Architecture Matrix

Production Storage Engine Implementations

🔍 Companion Workbenches & Verification Tools

RabbitMQ & AMQP 0-9-1 Queue Architecture & Backpressure Studio

Linux Page Faults, Copy-on-Write (COW) & VMA Allocator Studio

Linux io_uring Registered Buffers & Fixed Files Architecture Studio

PostgreSQL Write-Ahead Log (WAL), Replication & CDC Architecture Studio

Why Smart Users Are Switching to This Free Toolkit

The Browser Feature Most People Never Use

Stop Paying for Software You Can Get Free

File Conversion Tricks That Save Hours Every Week

This Free Tool Replaced 5 Paid Apps for Our Team

What Your Browser Can Do Without Any Extensions