DEV Community

Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Why Do Database Indexes Slow Down INSERTs? (The B+ Tree Page Split Dilemma)

#sql #performance #programming #database

Every junior engineer learns that adding an index to a database column makes SELECT queries blazing fast—reducing full table scans ((N)$) to logarithmic B+ Tree lookups ((\log N)$).

So why shouldn't we just index every single column in the table?

Because on an indexed table, a simple INSERT is never just an append. In high-throughput systems, over-indexing can spike write latency by 300% to 500%.

Here is what actually happens inside a database storage engine during an INSERT.

1. Unindexed Table: The O(1) Sequential Append

When a table has no secondary indexes, inserting a row is straightforward:

  • The database appends the raw row to the end of the current heap data page.
  • This is a fast, sequential write ((1)$ complexity).
  • Disk I/O is minimal, and Write-Ahead Log (WAL) records are simple.

2. Indexed Table: The Write Amplification Problem

When you add indexes (such as B+ Trees on email, created_at, or status), the database must maintain every single index in strictly sorted order.

Every single INSERT statement now triggers a 2-phase execution:

  1. Heap Storage Write: The row is written to raw heap storage.
  2. Index Traversal: The storage engine traverses the B+ Tree of every secondary index down from the root page to the target leaf page to find the exact insertion slot.
  3. Key Shifting: Existing keys on that 8KB or 16KB leaf page must be shifted down to insert the new key in sorted order.

3. The Real Killer: B+ Tree Page Splits

What happens when the target 16KB leaf page is completely full?

The database cannot simply overwrite adjacent memory. It is forced to trigger an expensive Page Split:

  1. Allocate New Page: The engine allocates a new 16KB disk page.
  2. Migrate Keys: Exactly 50% of the keys from the full page are moved to the new page.
  3. Update Parent Pointer: A new routing key and pointer are inserted into the parent node.
  4. Cascading Splits: If the parent node is also full, the split cascades upward toward the root, increasing the height of the tree.
  5. WAL Logging: Every modified page generates multiple Write-Ahead Log (WAL) records for durability.

The Result: A single INSERT statement turns into multiple random disk I/O operations and write amplification!

Key Takeaways for Backend Engineers

  • Indexes are not free: Every index you add speeds up reads at the direct expense of write throughput and storage bloat.
  • Avoid indexing high-cardinality volatile fields: If a column changes constantly and isn't frequently used in WHERE clauses, do not index it.
  • Batch Inserts: When loading bulk data, inserting in sorted order of the clustered index drastically reduces page splits.

🚀 Explore the Interactive Visualizer:
We built an interactive B+ Tree Page Split simulator and memory rail on Binary Dose to help engineers grasp storage engine internals in under 3 seconds.

👉 Read the Full Deep-Dive & Play with the Simulator on Binary Dose

Top comments (0)