Why Are Pointer-Chasing BSTs Slower Than Flat Arrays?

In modern classical computing, pointer-chasing binary search trees often perform worse than flat array searches despite having the same theoretical time complexity. This performance gap stems from how modern CPUs access memory through hierarchical caches rather than uniform-cost RAM. When a data structure scatters its nodes across memory, each pointer dereference can trigger an expensive cache miss, whereas contiguous arrays take full advantage of hardware prefetching and spatial locality.

The Memory Hierarchy and Cache Lines

Modern processors operate much faster than main system memory (DRAM). To bridge this speed gap, CPUs rely on small, fast static RAM caches—typically L1, L2, and L3—situated close to the processor cores. Data is not transferred between DRAM and these caches one byte at a time; instead, it moves in fixed-size blocks called cache lines, which are commonly \(64\text{ bytes}\) wide on x86-64 architectures.

When the CPU requests a memory address, it first checks the L1 cache. If the data is present (a cache hit), access takes only a few clock cycles. If it is absent (a cache miss), the CPU must fetch the entire \(64\text{-byte}\) cache line from L2, L3, or main memory, which can stall execution for hundreds of cycles.

Why Pointer-Chasing Hurts Performance

In a traditional pointer-based binary search tree (BST), each node is typically allocated dynamically on the heap. A node contains a key, a value or payload, and at least two pointers to its left and right children. Because heap allocations happen over time and across different memory regions, a parent node and its children rarely reside in the same cache line.

Traversing a pointer-chasing BST requires following a chain of memory addresses:

  1. Read the current node's key.
  2. Compare it with the search target.
  3. Dereference the left or right child pointer to find the next node's address.

Because the address of the next node is unknown until the current node is loaded and compared, the CPU cannot predict which memory locations will be needed next. This creates a serial dependency chain where every step risks a cache miss. For a tree with \(n\) nodes, a search takes \(O(\log_2 n)\) steps, and in the worst case, nearly every step can incur a full main-memory latency penalty.

How Flat Arrays Exploit Cache Locality

A sorted flat array stores all elements contiguously in memory. When performing a binary search on a flat array, the algorithm still takes \(O(\log_2 n)\) comparisons, but its memory access pattern is far more cache-friendly, especially as the search narrows:

  • Spatial locality: Once the search range shrinks to fit within a single cache line (or a few adjacent lines), all remaining comparisons happen entirely within L1 cache without any further main-memory fetches.
  • Reduced memory footprint: Flat arrays do not store left and right child pointers. Without pointer overhead, more keys fit into a single \(64\text{-byte}\) cache line, increasing the effective branching factor per cache fetch.
  • Hardware prefetching: Modern CPUs include hardware prefetchers that detect predictable, strided, or sequential memory access patterns. While early steps of a binary search jump across the array, linear scans over small subarrays—often used as a hybrid cutoff in flat-array searches—trigger prefetchers to load upcoming cache lines before the CPU even requests them.

Branch Prediction and Memory-Level Parallelism

Pointer-chasing also limits instruction-level parallelism. Modern out-of-order processors try to execute independent instructions simultaneously, but a dependent chain of pointer dereferences forces the CPU to wait for each load to complete before issuing the next one.

In contrast, flat arrays allow simpler index arithmetic. For small arrays or the final stages of a search, branchless linear or binary search implementations can eliminate mispredicted branches altogether. Even when comparing large datasets, cache-conscious layouts such as B-trees or Eytzinger (BFS-ordered) arrays pack multiple keys into each cache line, reducing the total number of cache misses from \(O(\log_2 n)\) to \(O(\log_B n)\), where \(B\) is the number of keys per cache line.

Summary

While pointer-chasing binary search trees and flat array binary searches share the same \(O(\log n)\) asymptotic complexity, Big-O notation assumes uniform memory access costs. On modern hardware, memory latency dominates execution time. Because pointer-chasing scatters nodes across memory and serializes dependent loads, it suffers frequent cache misses, making flat arrays—and cache-aligned contiguous structures—significantly faster in practice.