Course contentsShow
← Computer Science
Lesson 529 of 2,87212. Binary Search TreesFree lesson

Cache Performance and BSTs

Understanding how pointer-based BST structure affects CPU cache behavior compared to array-based structures.

Cache Performance and BSTs

You'll learn: Why pointer-based Binary Search Trees tend to have worse cache performance than array-based structures like sorted arrays or heaps.

The Cache Locality Problem

Modern CPUs don't fetch data one byte at a time—they grab entire cache lines (typically 64 bytes) from memory. When you access one piece of data, nearby data comes along for free. This is called spatial locality.

Arrays have excellent cache locality: elements sit next to each other in memory. When you access arr[5], the CPU likely also loads arr[6], arr[7], etc. into cache automatically.

BSTs, however, use pointer-based nodes scattered randomly across the heap. When you traverse from a parent to its left child, you're jumping to a completely different memory location. The CPU can't predict where that node lives, so it must fetch a new cache line—often from slow main memory.

Why This Matters

Imagine searching a BST of 1,000 nodes. Even though you only visit ~10 nodes (log₂ 1000 ≈ 10), each node access might trigger a cache miss—a costly trip to RAM that can be 100× slower than accessing cached data.

In contrast, binary search on a sorted array benefits from prefetching. The CPU loads chunks of the array speculatively, keeping your search blazingly fast despite visiting the same number of elements.

The Tradeoff

BSTs offer O(log n) insertion and deletion in average cases, which arrays can't match. But for search-heavy workloads with infrequent updates, the cache-friendly array often wins in practice, even though both are O(log n) theoretically.

Key Takeaway: Pointer-based BSTs suffer from poor cache locality because nodes are scattered in memory, making them slower in practice than cache-friendly array-based structures for many workloads despite similar Big-O complexity.