Database Indexing Mechanics: From $O(N)$ to $O(\log N)$

Understanding how databases retrieve data efficiently is one of the most critical skills in backend engineering. At its core, database indexing is about avoiding full-table scans — transitioning a query's time complexity from $O(N)$ (examining every row) to $O(\log N)$ (narrowing the search space exponentially per step) or even $O(1)$ in specialized cases.

This deep-dive explores three fundamental access patterns that underpin virtually every modern database engine:

The key insight: no single structure dominates all workloads. Engineering the right indexing strategy requires understanding the structural mechanics and complexity trade-offs of each approach.

The Sequential Table Scan: $O(N)$ Baseline

A sequential scan is the simplest — and often the most expensive — access path. The database reads every page of the heap table, evaluating each row against the query predicate.

Why Sequential Scans Still Matter

Despite their $O(N)$ complexity, sequential scans are not always wrong:

1. Small tables: If a table fits in a few pages, the overhead of index traversal (random I/O) exceeds the cost of scanning all pages (sequential I/O). PostgreSQL's query planner, for instance, has a built-in random_page_cost threshold and will prefer sequential scans for small datasets .

2. High selectivity queries: When a query returns a large percentage of rows (e.g., >10–15%), reading the index + random heap fetches becomes more expensive than just scanning everything sequentially. This is because each index-based row access requires a separate random I/O, whereas a sequential scan reads contiguous blocks .

3. No useful index exists: If no index matches the query's filter columns, there is no alternative.

I/O Cost Model

The fundamental comparison:

$C_{\text{seq}} = \frac{N}{P} \cdot C_{\text{seq\_io}}$

$C_{\text{index}} = \log_B(N) \cdot C_{\text{rand\_io}} + S \cdot C_{\text{rand\_io}}$

Where $N$ = number of rows, $P$ = rows per page, $S$ = number of matching rows, $B$ = branching factor, $C_{\text{seq\_io}}$ = cost of sequential I/O, and $C_{\text{rand\_io}}$ = cost of random I/O.

Since random I/O is typically 10–100× slower than sequential I/O on HDDs (and still significant on SSDs), there exists a selectivity threshold beyond which the full scan wins.

B-Tree Indexing: From $O(N)$ to $O(\log N)$

The B-Tree is the most ubiquitous index structure in relational databases — used by PostgreSQL, MySQL (InnoDB), SQLite, Oracle, and SQL Server. It provides $O(\log N)$ lookups, insertions, and deletions.

Structural Anatomy

Unlike a binary search tree (which has branching factor 2), B-Trees have a high branching factor (typically 100–1000+), meaning the tree is extremely shallow. A B-Tree with branching factor $B$ and $N$ keys has height:

$h \leq \lceil \log_B(N) \rceil$

For a table with 1 billion rows and branching factor 500:

$h \leq \lceil \log_{500}(10^9) \rceil \approx 4 \text{ levels}$

This means only 4 disk reads are needed to find any row — the difference between seconds and microseconds.

B-Tree Mechanics: Search, Insert, Delete

Search: Start at the root. At each node, perform a binary search within the node's sorted keys to select the correct child pointer. Descend until a leaf node is reached.

Insert: Traverse to the correct leaf. If the leaf has room, insert the key. If it's full, split the leaf into two halves and propagate the median key upward. This may cause cascading splits up to the root (which grows the tree by one level) .

Delete: Find the key, remove it. If the node falls below minimum occupancy, merge with a sibling or redistribute keys from a sibling. This may cascade upward.

B+Tree: The Practical Variant

Most databases actually implement B+Trees, not pure B-Trees. The critical differences:

• Internal nodes contain only keys (no data) — maximizing branching factor
• All data is in the leaf level — making scans uniform
• Leaf nodes are linked in a doubly-linked list — enabling efficient range scans without re-traversing the tree

$\text{Range scan cost}: O(\log_B N + K/P)$

Where $K$ is the number of matching rows and $P$ is the page size. The linked-list structure means once you reach the first matching leaf, you scan contiguous leaves — no more tree traversals .

LSM-Trees: Engineering for Write-Heavy Workloads

The LSM-Tree (Log-Structured Merge Tree) was introduced by Patrick O'Neil et al. in 1996 as a fundamentally different approach: optimize for writes, not reads .

The Write Problem with B-Trees

B-Trees are read-optimized but write-hostile. Every insert, update, or delete requires:

1. Traversing $O(\log_B N)$ levels to find the target leaf
2. Loading the page (random I/O)
3. Potentially triggering page splits, rebalancing, and WAL logging
4. Each write incurs random I/O — the worst case for disk performance

For write-heavy workloads (time-series data, event logs, IoT telemetry), this random I/O pattern becomes the bottleneck.

LSM-Tree Architecture: The Write Path

LSM-Trees flip this model by making writes sequential:

Write Complexity: $O(1)$ amortized — writes go to the in-memory MemTable (no disk I/O for most writes). The MemTable is flushed to disk as a new SSTable only when it reaches a size threshold .

The Read Path: Where Complexity Increases

While writes are cheap, reads become more complex. To find a key:

1. Check the MemTable (memory): $O(\log N_{\text{mem}})$
2. Search Level 0 SSTables (newest to oldest): $O(L_0 \cdot N_{\text{sstable}})$ — each L0 SSTable may overlap
3. Search Level 1+ SSTables: $O(\log N)$ per level (one SSTable per level due to key range partitioning)
4. Use Bloom filters to skip SSTables that definitely don't contain the key

$\text{Worst-case read cost}: O(L_0 + \log_{B} N \cdot L_{\max})$

Where $L_0$ is the number of un-compacted SSTables and $L_{\max}$ is the maximum level. Without bloom filters, this can degrade toward $O(N)$ — a critical concern.

Compaction: The Background Garbage Collector

Compaction is the mechanism that keeps read performance from degrading:

Write amplification in leveled compaction can be significant: a single write may be re-written $L_{\max}$ times during compaction. For LevelDB/RocksDB with 7 levels and size ratio 10, write amplification can reach 30–50× .

Complexity Transition Analysis: $O(N) \rightarrow O(\log N)$

The fundamental question: when does an index actually help, and when does it hurt?

The Cross-Over Point

Consider a table of $N$ rows stored across $P = N / R$ pages (where $R$ = rows per page). The cost of sequential scan:

$C_{\text{seq}} = P \cdot t_{\text{seq}} = \frac{N}{R} \cdot t_{\text{seq}}$

The cost of B-Tree index scan returning $K$ rows:

$C_{\text{btree}} = h \cdot t_{\text{rand}} + K \cdot t_{\text{rand}}$

Where $h = O(\log_B N)$ is the tree height and $t_{\text{seq}}$ and $t_{\text{rand}}$ are sequential and random I/O times respectively.

Setting $C_{\text{seq}} = C_{\text{btree}}$ and solving for the selectivity threshold $\sigma = K / N$:

$\sigma^* \approx \frac{1}{R} \cdot \frac{t_{\text{seq}}}{t_{\text{rand}}}$

On HDDs, an index scan is only beneficial when retrieving fewer than 0.02% of rows. On NVMe SSDs, the advantage window widens significantly because random I/O is much faster .

Big-O Summary

$\boxed{\text{Sequential Scan: } O(N) \text{ - always, with no overhead}}$

$\boxed{\text{B-Tree Point Lookup: } O(\log_B N) \text{ - but } + O(K) \text{ random I/Os for fetches}}$

$\boxed{\text{LSM-Tree Point Lookup: } O(\log_B N) \text{ best case, } O(N) \text{ worst case without bloom filters}}$

$\boxed{\text{B-Tree Range Scan: } O(\log_B N + K) \text{ - logarithmic entry + linear scan of leaves}}$

$\boxed{\text{LSM-Tree Write: } O(1) \text{ amortized - constant-time in-memory insert}}$

When Each Structure Wins: Decision Matrix

References