Data Structures, Algorithms, and Computational Complexity

What asymptotic analysis tells you, and what it hides

Asymptotic complexity counts operations as the input grows. It ignores constant factors, and that is the point. An O(n log n) algorithm beats an O(n squared) algorithm at some input size, whatever the constants, and the crossover point does not move much.

The model has one large blind spot. It assumes that every memory access costs the same. Chapter 1 showed that accesses differ by a factor of eighty between L1 and DRAM, and by a factor of eighty thousand between DRAM and a drive. An algorithm with fewer operations and worse locality often loses to an algorithm with more operations and better locality.

A linked list and a dynamic array both support iteration in O(n). Walk a linked list of one million 32 byte nodes that a general allocator placed in arbitrary order. Each next pointer is a dependent load, so the loads serialize, and each one costs a cache miss. The walk takes about 95 milliseconds. Walk an array of the same million elements and the prefetcher hides every miss. The walk takes about 0.3 milliseconds. The complexity class is identical and the measured ratio is more than three hundred.

Two rows in Table 3.1 need a comment. The linked list in allocation order is fast because the allocator placed consecutive nodes consecutively, so the prefetcher works. That layout survives until the first pattern of inserts and deletes, after which the list scatters and the cost rises toward the first row. Do not build a design on it.

The B+tree row is more interesting. A B+tree search does more comparisons than a binary search on the same data. It runs five times faster because it touches three cache lines instead of twenty. Binary search on one million sorted 32-bit integers jumps 2 MiB, then 1 MiB, then 512 KiB, and the first ten jumps each miss every cache level. A B+tree with 512 entries per node reaches the leaf in three levels, and the top two levels stay resident in L2.

The external memory model

The right model for large data counts block transfers rather than operations. In the external memory model, the machine has a fast memory of size M and moves data in blocks of size B. The cost of an algorithm is the number of block transfers. The model applies to any two adjacent levels of the hierarchy: cache and DRAM, or DRAM and an SSD.

The model produces different answers than the operation count model. Scanning n items costs n divided by B transfers, not n. Sorting n items costs (n/B) times log base (M/B) of (n/B), not n log n. Searching a B-tree costs log base B of n, not log base 2 of n.

Those formulas explain the whole design of storage engines. Set B to 4096 bytes and an 8 byte key, so that 512 keys fit one block. Searching one billion keys costs log base 512 of 1e9, which is about 3.3 block reads. A binary search tree costs log base 2 of 1e9, which is 30 block reads. The B-tree wins by a factor of nine, and Chapter 7 spends the whole result.

  Binary search tree                B+tree, 512 keys per node
  ------------------                -------------------------
  depth 30                          depth 4
  30 block reads                    4 block reads
  30 x 80 us = 2.4 ms               4 x 80 us = 0.32 ms   (from NVMe)

  level 0 ......... 1 node          level 0 ......... 1 node,  cached
  level 1 ......... 2               level 1 ......... 512,     cached
  level 2 ......... 4               level 2 ......... 262,144, mostly cached
  ...                               level 3 ......... 134 million leaves
  level 29 ........ 536 million

  The top two levels of the B+tree fit in 1 MiB and stay in cache.
  Only the leaf read touches the device.

Cache-oblivious algorithms reach the same bounds without knowing B or M. The van Emde Boas layout stores a tree in memory so that any subtree of any size sits contiguously, which gives optimal block behavior at every level of the hierarchy at once. The idea is elegant, and in practice engineers tune B explicitly, because the constant factor of a tuned structure beats the constant factor of an oblivious one.

Hash tables in 2026

A hash table gives expected constant time lookup. The two classical designs handle collisions differently. Separate chaining puts colliding keys in a linked list per bucket. Open addressing puts them in the next free slot of the same array.

Open addressing wins on modern hardware for almost every workload. Chaining follows a pointer on every collision, and each pointer is a cache miss. Open addressing probes the next slot, which usually sits in the same cache line. The cost appears when the table fills, because probe sequences lengthen sharply above about 80 percent load.

Linear probing, quadratic probing, and Robin Hood hashing differ in how they place a colliding key. Linear probing takes the next slot and has the best cache behavior. Robin Hood hashing moves entries so that every key sits at a similar distance from its ideal slot, which cuts the variance of probe length and therefore cuts tail latency.

The best current design is the Swiss table, which absl::flat_hash_map in C++ and hashbrown in Rust both implement. It splits the table into a control byte array and a slot array. Each control byte holds seven bits of the hash plus one state bit. A lookup loads sixteen control bytes into a SIMD register, compares all sixteen against the target in one instruction, and produces a bitmask of candidate positions. One cache line therefore answers sixteen candidate comparisons.

  hash = 0x9F3C21A7

  h1 = hash >> 7          -> bucket index, selects a 16-slot group
  h2 = hash & 0x7F        -> 7-bit tag stored in the control byte

  control bytes (16 in one 128-bit register)
  +----+----+----+----+----+----+----+----+ ... +----+
  | 27 | FF | 27 | 80 | 5A | 27 | FF | 11 |     | 27 |
  +----+----+----+----+----+----+----+----+ ... +----+
    ^ full     ^empty       ^ deleted

  _mm_cmpeq_epi8(control, broadcast(h2)) -> bitmask 0b0000000000100101
  Test only the 3 slots that matched. Empty byte in the group ends the probe.

Three numbers govern hash table behavior in production. The load factor controls memory against speed, and 0.75 to 0.875 is the usual range. The hash function quality controls the probe length, and a weak hash on adversarial input turns O(1) into O(n). The growth policy controls tail latency, because a table that doubles copies every element in one operation.

Rehashing produces a latency spike that shows up at the 99.9th percentile. A table with ten million entries takes about 200 milliseconds to double, and every request that arrives during the copy waits. Three fixes exist. Reserve the final capacity at construction when you know it. Use incremental rehashing, where each operation moves a few entries from the old table to the new one, which is what Redis does. Use a structure that never rehashes in bulk, such as an extendible hash or a tree.

Trees that production systems use

A balanced binary search tree gives O(log n) with a small constant in operation count and a bad constant in cache behavior. Red-black trees appear in the Linux kernel, in std::map, and in TreeMap, and they are correct choices when the data is small and ordered iteration matters.

B-trees and B+trees dominate anything larger. The B+tree keeps all values in the leaves and links the leaves, which makes a range scan a linear walk. Node size follows the block size of the level below: 256 to 512 bytes for a cache-resident index, 4 KiB to 16 KiB for a disk-resident one. Chapter 7 covers the concurrency and durability side.

Tries index by key prefix rather than by comparison. A lookup costs O(k) where k is the key length, independent of the number of keys. A plain trie wastes enormous memory, because each node holds 256 child pointers. The Adaptive Radix Tree, or ART, fixes that by using four node layouts of increasing size, switching between them as a node gains children. ART matches a hash table for point lookups and keeps ordered iteration, which a hash table cannot do.

Skip lists reach O(log n) expected with probabilistic balancing and no rotations. Each node appears in level i with probability one half to the power i. The structure is simple to make lock-free, which is why the LevelDB and RocksDB memtable uses one and why Redis uses one for sorted sets.

The last row is the reminder that the simplest structure often wins. A sorted array has the smallest memory footprint, the fastest range scan, and no concurrency story at all. Systems that can rebuild an index in the background and swap it atomically use exactly that, and they beat every mutable structure on read performance.

Probabilistic structures: trading exactness for space

A Bloom filter answers one question: is this key possibly in the set, or definitely not in it? It never reports a false negative and it reports a false positive at a tunable rate. It stores no keys, so its size depends only on the count and the target error rate.

The filter is a bit array of m bits and k hash functions. Insert sets k bits. A query tests k bits and returns "possibly present" only when all k are set. The optimal number of hashes is k equal to minus log base 2 of p. The required bits per element is minus log base 2 of p, divided by the natural log of 2.

Read the table as the central fact about Bloom filters. Each factor of ten in accuracy costs 4.8 more bits per element, forever. Most systems pick ten bits per element with a 1 percent error rate. That holds a billion keys in 1.2 gigabytes, where the keys themselves need 30 gigabytes or more.

The production use is always the same. Put a filter in front of an expensive lookup so that the lookup runs only when the filter says "possibly present". An LSM-tree storage engine puts one filter per sorted table file, and a point read that misses skips the file entirely rather than reading its index. Chapter 7 measures the effect, which is large: without filters a read touches every level, and with them it touches one.

Two variants matter. A counting Bloom filter replaces each bit with a small counter so that deletion works, at four times the space. A cuckoo filter stores short fingerprints in a cuckoo hash table, supports deletion, and uses less space than a Bloom filter for false positive rates below about 3 percent.

Cardinality estimation uses a different trick. HyperLogLog hashes each element and tracks the maximum number of leading zeros seen, per bucket. The intuition is that seeing a hash with 20 leading zeros suggests about a million distinct elements. With 16,384 buckets of 6 bits each, the structure occupies 12 kilobytes and estimates cardinality within about 0.81 percent, for any cardinality from ten to billions. Two sketches merge by taking the per-bucket maximum, so the structure distributes across machines with no coordination.

Frequency estimation uses the Count-Min sketch. It is a two dimensional array of counters with one hash function per row. An update increments one counter per row. A query takes the minimum across rows, which bounds the overestimate. Set the width to e divided by the error and the depth to the natural log of one over the failure probability. Heavy hitter detection, rate limiting at scale, and stream analytics all run on this structure.

Spatial and vector indexes

Spatial queries ask for objects near a point or inside a region. A one-dimensional index cannot answer them, because sorting by latitude separates points that sit next to each other in longitude.

A quadtree divides a plane into four quadrants and subdivides a quadrant when it holds more than a threshold of points. Query cost is O(log n) for a balanced distribution and degrades badly for clustered data, because dense regions produce deep subtrees. A k-d tree splits on alternating dimensions at the median, which stays balanced for any distribution and handles higher dimensions up to about 20.

An R-tree indexes rectangles rather than points, which suits map features, bounding boxes, and any object with extent. Nodes hold minimum bounding rectangles that can overlap, and a query descends into every child whose rectangle intersects the query. PostGIS, SQLite, and most spatial databases use an R-tree variant. The R*-tree improves the split heuristic and cuts overlap, which is the main cost driver.

Space filling curves take a different approach. They map two or three dimensions onto one while keeping most of the locality, so that an ordinary B-tree can serve the query. A geohash interleaves the bits of latitude and longitude, so a shared prefix means spatial proximity. Uber's H3 system uses hexagons instead of squares, which gives every cell the same distance to all six neighbors and removes the corner artifacts of a square grid.

  QUADTREE                    K-D TREE
  +-------+-------+           split x at median, then y, then x ...
  |  .  . |   .   |           balanced for any distribution
  +---+---+-------+           good to about 20 dimensions
  |. |. .|   .    |
  +---+---+-------+           R-TREE
  |   .   |  ...  |           nodes hold bounding rectangles
  +-------+-------+           rectangles may overlap
  subdivide dense cells       handles extent, not just points

  GEOHASH / Z-ORDER                  H3 HEXAGONS
  interleave lat and lon bits        equal distance to all neighbors
  9q8yy -> shared prefix = near      no corner-adjacency artifact
  one B-tree serves the query        7 children per cell, approximate

High-dimensional vector search broke all of these. Above about 20 dimensions, every tree structure degrades to a full scan, a result known as the curse of dimensionality. The distance between the nearest and the farthest point converges, so pruning stops working.

Approximate nearest neighbor search replaced exact search. Hierarchical Navigable Small World, or HNSW, builds a layered proximity graph. The top layer holds few nodes with long edges, and each lower layer adds nodes and shorter edges. A search starts at the top, greedily walks toward the query, drops a layer, and repeats. Query cost is about O(log n) with a small constant, and recall runs above 95 percent with tuned parameters.

HNSW carries three costs that matter in a production design. Memory runs between 1.5 and 2 times the raw vector size, because each node stores its edges. Build time is high, because each insert searches the existing graph. Deletion is awkward, because removing a node breaks paths, and most implementations mark a node as deleted and rebuild later. Inverted file indexes with product quantization, or IVF-PQ, trade recall for a much smaller footprint, and they suit billion-scale collections where HNSW does not fit in memory.

Sorting, at every scale

Comparison sorting has a lower bound of n log n comparisons, and the bound is tight. The interesting question is which constant factor and which memory behavior a given implementation delivers.

Pattern-defeating quicksort, or pdqsort, is the current default in Rust and in several C++ standard libraries. It runs quicksort with good pivot selection, detects the patterns that cause quadratic behavior, and falls back to heapsort when the recursion goes too deep. It also detects already sorted runs and returns early. The result is quicksort speed with a worst case of O(n log n).

Timsort exploits existing order. It finds ascending and descending runs, extends short runs with a binary insertion sort, and merges runs under invariants that keep the merge balanced. Real data is often partly sorted, and Timsort runs in O(n) on such input. Python and Java use it for object arrays, where comparison cost dominates and stability matters.

Radix sort escapes the comparison bound entirely by using the key structure. It sorts n keys of k digits in O(nk) with counting sort per digit. For 32-bit integers with 8-bit digits that is four passes, and a well implemented radix sort beats a comparison sort by two to three times on large integer arrays. The cost is memory traffic, because each pass scatters.

Sorting data larger than memory uses external merge sort. Read chunks that fit in memory, sort each one, and write it as a run. Then merge the runs with a heap, reading a block from each. The I/O cost is (n/B) log base (M/B) of (n/B), which for a terabyte with 64 gigabytes of memory is two passes. Every analytics engine and every LSM compaction uses this algorithm.

Graphs and the memory wall

Graph algorithms are the hardest case for the memory hierarchy. A breadth first search touches neighbors in arbitrary order, so it misses the cache on almost every edge. Complexity says O(V + E). Hardware says that each edge costs a DRAM access.

Layout carries most of the gain. Compressed sparse row, or CSR, stores a graph in two arrays: an offset array of length V plus one, and a neighbor array of length E. The neighbors of vertex v sit contiguously between offsets[v] and offsets[v+1], so reading them is sequential and the prefetcher helps. Adjacency lists made of pointers cost a miss per neighbor.

/* CSR breadth-first search. Neighbors of v are contiguous. */
void bfs(const int32_t *offsets, const int32_t *neighbors,
         int32_t n, int32_t source, int32_t *dist) {
    for (int32_t i = 0; i < n; i++) dist[i] = -1;
    dist[source] = 0;

    int32_t *frontier = malloc(n * sizeof(int32_t));
    int32_t *next = malloc(n * sizeof(int32_t));
    int32_t fsize = 1, nsize = 0, level = 0;
    frontier[0] = source;

    while (fsize > 0) {
        nsize = 0;
        for (int32_t i = 0; i < fsize; i++) {
            int32_t v = frontier[i];
            for (int32_t e = offsets[v]; e < offsets[v + 1]; e++) {
                int32_t u = neighbors[e];          /* sequential read */
                if (dist[u] == -1) {               /* random read */
                    dist[u] = level + 1;
                    next[nsize++] = u;
                }
            }
        }
        int32_t *tmp = frontier; frontier = next; next = tmp;
        fsize = nsize; level++;
    }
    free(frontier); free(next);
}

Direction-optimizing BFS cuts the cost further on graphs with a heavy-tailed degree distribution, which describes social graphs and web graphs. When the frontier is large, the algorithm switches from pushing out of frontier vertices to pulling into unvisited vertices, and it stops as soon as it finds one visited parent. The switch cuts total edge traversals by three to six times on real social graphs.

Choosing a structure

The choice follows the dominant operation and the size relative to the cache. Table 3.4 gives the short form.

One warning applies to every row. Measure the structure on your data and your access pattern before you commit. Published benchmarks use uniform random keys that fit in cache, and production keys are neither uniform nor cache-resident.

Sources and further reading

Thomas Cormen and others, "Introduction to Algorithms", fourth edition, for the analysis. Alok Aggarwal and Jeffrey Vitter, "The Input/Output Complexity of Sorting and Related Problems", 1988, for the external memory model. Viktor Leis and others, "The Adaptive Radix Tree", ICDE 2013. Yu Malkov and Dmitry Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", 2018. Bin Fan and others, "Cuckoo Filter: Practically Better Than Bloom", CoNEXT 2014. Philippe Flajolet and others, "HyperLogLog", 2007. The Abseil flat_hash_map design notes for the Swiss table.