Stackbook Logo
data-stateestablished · low operational burden

B-Tree Index

Also known as: b-plus-tree, btree-index

Intent

Provide ordered, logarithmic-time lookups and range scans over disk-resident data using a shallow, wide tree of fixed-size pages.

Problem

Scanning an entire table to find rows is far too slow once data outgrows memory. Queries need both exact lookups and ordered range scans with predictable latency. Each disk access is expensive, so the structure must minimize page reads.

Forces

  • •Disk and SSD access is page oriented, so wide nodes reduce I/O
  • •Writes must keep the tree balanced and ordered
  • •Each extra index slows inserts and updates
  • •Concurrent readers and writers need safe page-level locking

Solution

Overview

The B-tree, in practice the B+ tree, is the default index structure of relational databases. Its high fanout keeps the tree only a few levels deep, so each lookup needs just a handful of page reads, and the first levels usually stay cached.

How it works

A composite index on (customer_id, created_at) serves equality on the first column and ranges on the second.

CREATE INDEX idx_orders_cust_time ON orders (customer_id, created_at);

root:      [ 400 | 900 ]
internal:  [100|250] [500|700] [950|990]
leaves:    k1 k2 ... -> k3 k4 ... -> (linked for range scans)

Leaf pages are chained, so a range scan finds the start key once and then walks sideways.

Because pages are updated in place, a write first traverses to the correct leaf, modifies it in the buffer cache and logs the change in the write-ahead log. When a leaf is full it splits into two and the parent gains a separator key; in rare cases the split cascades to the root, which then grows the tree by one level. Sequential keys append to the rightmost leaf and keep pages dense, whereas random keys land everywhere and leave pages half full. That is why key choice has a visible effect on index size and insert speed.

Pitfalls

  • Putting columns in the wrong order in a composite index so the leftmost prefix rule is not satisfied.
  • Random UUID primary keys that scatter inserts and split pages constantly.
  • Over-indexing: every secondary index must be updated on each write.
  • Wrapping an indexed column in a function so the index cannot be used.

Key takeaways

  • B-trees give logarithmic lookups and ordered scans.
  • Column order in composite indexes decides which queries benefit.
  • Indexes are a read versus write trade-off; measure with query plans.
  • Drop indexes that no query uses.

✓ When to Use

  • •OLTP workloads with point lookups and range queries
  • •Columns used in WHERE, JOIN and ORDER BY clauses
  • •Read-heavy systems that need predictable latency

✗ When Not to Use

  • •Extremely write-heavy ingestion where an LSM tree fits better
  • •Low-selectivity columns such as a boolean flag
  • •Full-text or vector similarity search needing specialized indexes

Pros

  • +Predictable logarithmic read latency
  • +Efficient range scans and ordered output
  • +Mature, well understood in every relational engine

Cons

  • −In-place updates mean random writes and page splits
  • −Every extra index adds write cost and storage
  • −Fragmentation can degrade performance over time

Cost Profile

Infrastructure

Low - indexes consume extra disk and buffer cache

Operational

Low - periodic reindex and statistics refresh

Cognitive

Medium - composite key order and covering indexes need care

Failure Modes

  • Page splits under random inserts cause write amplification and fragmentation

  • Unused or redundant indexes slow writes with no read benefit

  • Stale statistics lead the planner to ignore a good index

Real-World Examples

Alternatives

    Related Patterns

    • database-indexing
    • data-modeling

    Competency Domains

    data staterequirements constraints