Data structures

This guide builds every core data structure from scratch — array, hash table, tree, heap, trie, graph, the on-disk B-tree — and prices each operation by hand, in Python, with every number measured on the machine it was written on. Two questions run through all of it: how each structure actually works, and the problem shape that should make you reach for it. It ends on a decision table you can re-skim before an interview or a design review, with the understanding already built underneath it, not handed to you cold.

Big-O keeps the shape and throws the rest away

You have two ways to check whether an incoming request's IP is on your allow-list. A plain list, scanned start to finish, or a set. You time both against the eight prefixes you have in production today, the set wins by sixteen nanoseconds, and you have learned nothing — because the question was never about eight prefixes. It was about what happens when the list reaches eight thousand.

That is the problem this whole guide keeps running into: you have to compare two designs before either is built, at a size you do not have yet, on hardware you have not bought. Seconds cannot help you there. A second is a fact about your afternoon — this machine, this input, this once. Change the CPU and every number moves. So we throw the seconds away on purpose and keep the one thing that survives the move: how the cost grows as the input grows. That shape is what transfers, and Big-O is the notation for it.

Watch the terms fight

Say you count the operations some routine performs and get n² + 100n + 500, where n is the number of items. That middle term looks like the one to worry about — it has a hundred stuck to the front, and n² has nothing. So watch the three terms as n climbs:

      n             n^2         100n    500  n^2 share
     10             100        1,000    500       6.2%
    100          10,000       10,000    500      48.8%
   1000       1,000,000      100,000    500      90.9%
  10000     100,000,000    1,000,000    500      99.0%

At ten items the 100n term is winning comfortably and n² is a rounding error. By ten thousand it is the reverse: n² is ninety-nine percent of the work and the other two terms have vanished into it. They did not stop existing. They lost, and they lose harder the more input you hand over.

That is the entire justification for writing this routine off as O(n²) and forgetting the rest. Big-O keeps the term that wins in the end and drops every constant and every smaller term, because at the sizes where cost becomes a problem, the winning term is the cost.

Four shapes are almost the whole vocabulary

Nearly everything you meet in this guide is one of four growth shapes. Learn them as pictures, not formulas.

• O(1) — flat. The cost does not care how big the input is. A dict lookup is the same whether the dict holds ten keys or ten million.
• O(log n) — barely moves. Here log₂ n is just how many times you can halve n before you reach one: halve 1024 and you get 512, 256, 128, and so on down to 1 in ten steps, so log₂ 1024 = 10. Double the input and this cost goes up by one. A million items cost twenty; a billion cost thirty.
• O(n) — tracks the input one for one. Twice the data, twice the work. Scanning a list is this.
• O(n²) — explodes. Twice the data, four times the work; ten times the data, a hundred times. This is the shape of a loop inside a loop, and it is the one that turns a demo into an outage.

Between O(n) and O(n²) sits O(n log n), the cost of a good sort — a little worse than linear, nowhere near quadratic. That is the ladder, from "free" at the top to "dangerous" at the bottom.

Where the shape lies to you

Big-O describes the curve once n is large. It says nothing about where on that curve you are standing, and plenty of real work never leaves the small end.

Look again at the table. At n = 10, the 100n term and the constant 500 are the whole story, and the n² the notation kept is the part that does not matter yet. An allow-list of eight prefixes, a routing table of a hundred routes, a form with a dozen fields — these live at small n permanently, and there the constant factor Big-O discarded is exactly what decides the winner. This is why an O(n) linear scan can beat an O(log n) binary search (halving a sorted array to zero in on a key — the Algorithms guide builds it) on a short array, and why "it's the faster algorithm" is a claim you should always answer with "at what size?".

So Big-O is a lens with a fixed focal length. It brings the behaviour at scale into sharp focus and leaves the small-n foreground deliberately blurred. Keep both in mind: reach for the shape when the input can grow without bound, and measure when it cannot.

This is the pocket version — enough to price an operation as you meet each structure in the chapters ahead. The full treatment, where a single operation has a worst case, an average case and an amortised case that answer three different questions, belongs to the Algorithms guide. For now, one shape per operation is all you need.

An array is one multiply and one add

You write routes[9_999_999] on a list of ten million routes and it comes back instantly. You write routes[3] and it comes back exactly as instantly. The machine did not walk past the first nine million items to reach the ten-millionth — it went straight there, and it went there in the same time it takes to reach item three. That is worth stopping on, because it is the plainest example in the whole guide of a cost you can explain from the machine up, and once you can, half the structures ahead are variations on it.

Memory is a row of numbered cells

Start under the language. The working memory of the machine, RAM, is one enormously long row of cells, each holding one byte, each with a number called its address: cell 0, cell 1, cell 2, on up into the billions. The one thing the hardware is built to do fast is fetch the cell at an address you hand it. You give it a number, it gives you back what is in that cell, and it takes the same time no matter which number you gave. There is no walking. The address is not a position to seek to; it is more like a house number on an infinite street where every house is the same distance apart and the postman can teleport.

An array is a single reserved run of those cells, back to back, one element after another with no gaps. Reserve room for a million 8-byte elements and you get a contiguous block: the first element sits at some starting address (call it the base), the second at base + 8, the third at base + 16, and element i at base + i × 8.

That formula is the whole trick. To find element i, the machine does not search. It multiplies i by the element size, adds the base, and fetches that one address. One multiply, one add, one fetch — a fixed amount of work whether i is 3 or nine million. That is what O(1) indexing is: not "fast", but arithmetic instead of searching. The word for reaching any element in the same fixed time, without touching the others, is random access, and an array has it because its elements are evenly spaced and it knows where they start.

You can watch the flatness directly. Here is the time to read one element out of the middle of a Python list, at a hundred thousand elements and at a million:

  N=   100000  list[N/2]   10.5 ns
  N=  1000000  list[N/2]   10.8 ns

Ten times the data, the same ten nanoseconds. The list did not get slower because indexing never looks at the size — it computes an address.

Nothing moves one byte

Now the part the indexing formula hides, and the reason arrays are not merely convenient but fast in a way that matters.

When the machine fetches the cell at an address, it does not bring back one byte. It brings back the whole 64-byte block that byte lives in, a cache line, and parks it in a small, fast store on the CPU called a cache. Ask for one byte and you get sixty-four, whether you wanted them or not. The next sixty-three are now sitting in the cache, and reading them costs almost nothing until they are evicted to make room for another line.

This is decided entirely by layout. Walk an array front to back and every 64-byte line you pull delivers the next several elements for free — you touch memory once and then coast through what it brought. Scatter the same data across the heap and every element is its own line fetched from far away, most of it wasted. Same number of reads, same O(n); wildly different cost.

You can see it in Python, even buried under the interpreter. Take five million distinct integer objects allocated in order, and sum them. Then sum the same objects through a list that has been shuffled, so the walk jumps around the heap instead of moving through it:

N = 5,000,000 identical integer objects, summed
  allocated in order        10.6 ns/element
  same objects, scattered   66.8 ns/element
  scattered / in-order = 6.3x

Same objects, same additions, same O(n). The only thing that changed is whether the next integer was in a line the machine already had. Six times the cost, bought with nothing but where the objects sat.

And that six is a floor, because Python's ten-nanosecond-per-step interpreter overhead is sitting on top of the effect, shrinking it. Strip the interpreter away and it grows. The sharpest version can only be timed in C, where a step costs a nanosecond instead of ten and there is nothing to hide behind: on this machine, a contiguous array of four million integers summed at 0.6 nanoseconds each, and the identical values chased through scattered linked nodes cost around 100 nanoseconds each — well over a hundredfold, from memory layout alone.

The 64 itself is measurable the same way: stride through memory touching one byte every 1, 2, 4 … bytes and the per-touch cost climbs until the stride hits 64 and then flattens, because past 64 every touch already lands on its own fresh line. That flattening point is the cache line, read straight off a stopwatch. (These are cited from the reference machine rather than shown, because a 1-nanosecond effect is invisible under a ten-nanosecond interpreter; the durable fact is the shape, and the shape is a cliff at 64 bytes.)

So an array is fast twice over. The index is O(1) because it is arithmetic. The walk is fast because contiguity hands the cache line something it can reuse — and that second win is invisible to Big-O, which counts your reads and says nothing about how far apart they landed.

When to reach for it

Reach for an array (a list in Python) as your default sequence: whenever the data is a run of items you address by position and, above all, walk in bulk. Reading by index is O(1), iterating front to back is as fast as the machine gets, and nothing else you will meet beats it at "go through all of these in order". What you give up is cheap change in the middle: inserting or deleting anywhere but the end has to shift every element after it along by one, and that is the next chapter's problem — first the trouble with the end, then the trouble with the middle.

The list that grows, and the copy you never see

You are collecting a response body chunk by chunk:

chunks = []
for chunk in response.iter_content():
    chunks.append(chunk)

append is O(1). You have been told this and it is true. It is also, every so often, O(n): a full copy of everything the list already holds. The reason it averages out to O(1) anyway is one of the prettier arguments in this guide, and the last chapter left a thread hanging that it ties off.

The problem with a fixed run of cells

Last chapter's array had one flaw hiding inside its virtue. Its speed came from being a single contiguous run of cells with the next element always at the next address. But that means the run has a fixed length. Reserve room for eight elements and the ninth append has nowhere to go — the cell just past the end belongs to something else, and you cannot grow into it.

So the list does the only thing it can. It asks the allocator for a new, larger run somewhere with room, copies every element it already holds into the new block, frees the old one, and then stores the new element. That copy is the expensive append. If the list held n items, growing it moved all n.

Most appends are a single store into a slot that was already reserved — genuinely O(1). But every so often one append triggers a full copy. The question is how to honestly price an operation whose cost is "cheap, cheap, cheap, expensive, cheap, cheap …", and the answer is to stop pricing single appends and price the whole run instead.

Add up the whole run, then divide

Here is the accounting. Suppose the list doubled its capacity every time it filled — the version every textbook teaches. To grow a list to a million elements, it copied when it was full at 500,000, and before that at 250,000, and before that at 125,000, all the way down:

500,000 + 250,000 + 125,000 + ... + 4 + 2 + 1  =  999,999

That sum is just under a million. A million appends, and the total copying they triggered across the entire run is about a million moves — one copy per append, averaged over the run, and that stays true no matter how large the list gets. The expensive appends are rare enough, and the cheap ones numerous enough, that the average is a constant.

The fact doing the work is that a sum whose terms keep halving stays finite: 1 + ½ + ¼ + … never exceeds 2, so the whole history of copies costs about as much as the single most recent copy. That "average cost over any run of operations" has a name, amortised cost, and this is its worked example. The full treatment, with its three different ways of proving the same bound, is the Algorithms guide's; here you need only the conclusion, that a periodic copy paid for by the appends between copies comes out to O(1) each.

CPython does not double

Everyone learns the doubling proof and then assumes the implementation doubles. Watch a real Python list grow, reading its capacity out of sys.getsizeof:

 len at realloc  sizeof(bytes)  capacity(slots)
              0             56                0
              1             88                4
              5            120                8
              9            184               16
             17            248               24
             25            312               32
             33            376               40
             41            472               52
             53            568               64
             65            664               76

4, 8, 16, 24, 32, 40, 52, 64, 76. It doubles for the first few tiny steps and then very much does not — 52 to 64 is not a doubling, it is about a ninth more. Here is the line that produces it, from Objects/listobject.c at tag v3.11.15:

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

newsize >> 3 is newsize divided by eight. So the new capacity is newsize plus an eighth of itself plus six, rounded down to a multiple of four — a growth factor of 1.125, not 2. The sequence in the comment is exactly the one you just watched come out of getsizeof.

Any factor above one is a dial, not a rule

Does the smaller factor break the amortised argument? No — and seeing why is the whole point. Port CPython's real rule to Python, count the slots copied across a million appends, and set it beside doubling and beside a tempting-looking "just grow by four each time":

  CPython (x1.125+6)  reallocs      86  slots copied       8,445,096  =     8.45 per append
  doubling (x2)       reallocs      19  slots copied       1,048,572  =     1.05 per append
  grow-by-4           reallocs 250,000  slots copied 124,999,500,000  = 124999.50 per append

Read the last column. Doubling copies 1.05 slots per append; CPython copies 8.45. Both are constants — they do not grow as the list grows, so both are amortised O(1). CPython copies eight times as often as doubling, and in exchange wastes at most 12.5% of the block on empty slots where doubling wastes up to 100%. The growth factor is a dial between copying and slack memory, and every setting strictly above 1 lands in the same complexity class.

The third row is what happens when the dial goes to zero. Grow by a fixed four each time and the cost per append is 124,999.50 — and that number is not a constant, it grows with n. A fixed increment means the copies never get rarer as the list gets bigger, the geometric series becomes an arithmetic one, and appending goes from O(1) to O(n). The lesson the two proofs share: multiplicative growth is O(1) amortised, additive growth is O(n), and the multiplier only moves the constant.

When to reach for it

You already reach for this one: it is Python's list, the default sequence from the last chapter, and now you know the machinery under append. Reach for it whenever you are building a sequence by accumulation, and trust that sustained appending is safe: the copies are real but they thin out geometrically, so a million appends cost about a million stores plus a handful of copies. What you are paying for it is a little slack — up to an eighth of the block sitting empty — and the one worst-case append that copies the whole list, which matters only if you need a hard latency ceiling on a single operation rather than over the run.

Two disciplines on top of a list

An editor's undo, a browser's back button, the matching of brackets in a parser, the call stack that unwinds when a function returns — all four want the same thing: give me back the most recent thing first. A build pipeline, a rate limiter's backlog, a printer spool, a breadth-first walk want the opposite: give me back the oldest thing first. These are the two most common access disciplines in software, and neither is a new structure. Both are a list with a rule about which end you are allowed to touch.

A stack touches one end

A stack is a list where you only ever add to and remove from the same end. Add is push, remove is pop, and because both happen at the end, both are the array's cheap operation from the last two chapters — an O(1) amortised append and an O(1) pop, no shifting.

  push '(' -> ['(']
  push '[' -> ['(', '[']
  push '{' -> ['(', '[', '{']
  pop  '{' -> ['(', '[']
  pop  '[' -> ['(']
  pop  '(' -> []

The last thing in is the first thing out, which is why this discipline is called LIFO — last in, first out. Watch what it is doing: the pops come back in exactly the reverse of the order the pushes went in. That reversal is the whole reason a stack is useful. Checking whether brackets balance is nothing but this — push every opener, and every closer must match the most recent unmatched opener, which is the one on top:

  balanced('([]{})') = True
  balanced('([)]') = False
  balanced('(((') = False

([)] fails because when the ) arrives, the thing on top of the stack is [, not ( — the brackets cross instead of nest. A plain Python list is a perfect stack as it comes, no import required, because push and pop are exactly its two cheap operations.

A queue wants the other end, and that is the trap

A queue is the fair version: first in, first out — FIFO. Jobs come out in the order they arrived.

  enqueue 'build' -> ['build']
  enqueue 'test' -> ['build', 'test']
  enqueue 'deploy' -> ['build', 'test', 'deploy']
  dequeue 'build' -> ['test', 'deploy']
  dequeue 'test' -> ['deploy']
  dequeue 'deploy' -> []

Enqueue is an append — the cheap end again. But dequeue takes from the front, and the natural instinct is to write queue.pop(0). That line is correct, it passes every test you will write for it, and it is quadratic.

Here is why. An array's speed came from being a contiguous run with element i at base + i × size. Remove the front element and every other element is now in the wrong place — item 1 has to become item 0, item 2 has to become item 1, all of them sliding down one slot to keep the run contiguous. Removing from the front of an n-element list moves the other n − 1. Do that for every element as you drain the queue and you have shifted the whole array once per removal: O(n) per dequeue, O(n²) to empty it.

       N   list.pop(0) ms   deque.popleft ms    ratio
   10000          122.347              0.199     615x
   20000          491.731              0.440    1117x
   40000         1963.535              0.857    2292x
   80000         7906.030              1.780    4442x

Read the list.pop(0) column: every doubling of N roughly quadruples the time — 122, 491, 1963, 7906 — which is what O(n²) looks like on a stopwatch. At eighty thousand items the naive queue is over four thousand times slower than the fix, and the gap keeps widening. This is a bug that looks correct in review and only shows up as a mystery slowdown once the queue gets deep in production.

The fix is a linked list of little arrays

The right tool is collections.deque (a "double-ended queue"), and its shape is worth seeing because it is a clever answer to a question the next chapter asks in full. From Modules/_collectionsmodule.c at v3.11.15:

#define BLOCKLEN 64
...
 * Textbook implementations of doubly-linked lists store one datum
 * per link, but that gives them a 200% memory overhead (a prev and
 * next link for each datum) ... By using fixed-length blocks, the
 * link to data ratio is significantly improved ... The data blocks
 * of consecutive pointers also improve cache locality.

A deque is not one big array, and it is not a textbook linked list of single items either. It is a chain of small fixed blocks of 64 slots each, linked front to back. Append fills the last block until it is full, then links a fresh block; popleft empties the first block, then unlinks it. Neither end ever shifts the other, so both are genuinely O(1):

  N=   100000  deque[0]     18.5 ns   deque[N/2]     2595.6 ns   list[N/2]   10.5 ns
  N=  1000000  deque[0]     18.4 ns   deque[N/2]    32200.4 ns   list[N/2]   10.8 ns

The ends are flat and instant. But look at deque[N/2]: reaching the middle means walking the chain of blocks to find the right one, so middle indexing is O(n) and grows with size — 2,600 nanoseconds at a hundred thousand, 32,000 at a million — while a list stays flat at ten because it can compute the address. The block layout bought O(1) at both ends and paid for it with the random access an array has. You cannot have both, which is the recurring bargain of this whole subject.

When to reach for each

Reach for a stack whenever the job is "most recent first": undo histories, matching and parsing, backtracking, and depth-first search — the traversal that the Algorithms guide builds on this. A plain list already is one. Reach for a queue whenever the job is "oldest first" or "process in arrival order": work backlogs, buffering between a fast producer and a slow consumer, and breadth-first search. Use collections.deque, and treat list.pop(0) as the mistake it is. What a queue gives up, in either the deque form or any other, is cheap access to the middle — these are structures for the ends, and the moment you need to reach an arbitrary interior element by position you are holding the wrong tool.

The O(1) insert that loses to the O(n) one

Here is the most famous result in the whole subject, the one everybody remembers from the complexity table: inserting into a linked list is O(1), inserting into an array is O(n), so linked lists are good for insertion. It is the first genuinely counterintuitive thing anyone learns about data structures, and it is a trap — not because the O(1) is wrong, but because of the four words the table leaves off the end of it. This chapter builds the structure the claim is about, and then measures the words it left off.

A node is a value and a pointer

An array put its elements next to each other and used the spacing to find them. A linked list does the opposite: it lets the elements live anywhere in memory and has each one carry the address of the next. The unit is a node — a value plus a pointer to the following node — and the list is just the first node, from which you can reach all the rest by following pointers.

built:       a -> b -> c

The walk is the giveaway: to visit the list you start at the head and follow .next until it runs out, one node at a time, because there is no other way in. You cannot compute where the third node is — there is no formula, no base + i × size, because the nodes are not evenly spaced and not next to each other. The only route to node three is through nodes one and two.

The splice really is O(1)

Now the operation the table is bragging about. To insert a node between two others, you do not move anything. You repoint two pointers:

after splice: a -> x -> b -> c
after delete: a -> b -> c

Inserting x after a is two writes: x.next = a.next, then a.next = x. Deleting is one: point a past the node to skip it. No element slides, no array is copied, and it costs the same whether the list holds three nodes or three million. This is the real thing — an array would have had to shift every element after the insertion point to make room, and the linked list does not.

Making delete as cheap as insert needs one addition. In the list above, to remove a node you must know who points at it, and the singly linked node does not know its own predecessor. So a doubly linked list gives every node a prev pointer as well as a next, and now a node holds everything needed to splice itself out:

doubly, after unlinking the node we held: a -> c

Given only b, you set b.prev.next = b.next and b.next.prev = b.prev, and b is gone in O(1). This exact structure — nodes with two pointers, spliceable in place — is the recency list inside an LRU cache, which is chapter 13.

The four words the table left off

The splice is O(1) once you are holding the node. That clause is the entire catch, because getting to the node is the part the table does not price.

To reach the node before you can splice at it, you walk the pointers — O(n). And that walk is the worst kind of O(n) there is. Chapter 2's array walk pulled a 64-byte cache line and coasted through the next several elements for free. The linked-list walk cannot: each node sits at an address you only learn after fetching the previous node, so every step is a dependent load into a fresh, cold, scattered part of the heap. There is nothing to prefetch, because the machine cannot guess an address it has not read yet, and nothing reused, because each node is its own line most of which is wasted.

That is the bill chapter 2 measured. The same values in a contiguous array summed at under a nanosecond each; chased through scattered nodes they cost around a hundred nanoseconds each on the reference machine — over a hundredfold, and even in pure Python the scattered walk ran six to seven times slower than the in-order one. So the "O(1) insertion" that beats the array's "O(n) insertion" comes attached to a traversal that is a hundred times slower per step, and in almost every real workload the traversal is where the time goes.

You do not have to take the argument on faith — the people who write Python already took it. The fastest queue in the standard library, collections.deque, needed a linked structure but refused the textbook one node per item, because (its own source, from the last chapter) one datum per link "gives them a 200% memory overhead" and scatters the data. They linked arrays of 64 instead, precisely to claw back the cache locality a pure linked list throws away. When the experts who need a linked list build a hybrid to avoid the real thing, that tells you where the real thing belongs.

When to reach for it

Rarely, and that is the honest answer. Reach for a linked list when you are already holding the node you want to change — an iterator sitting on it, or another structure pointing straight at it — and you need to splice in O(1) without ever indexing by position. That is a narrow case, and when it comes up it usually comes up as half of a composite structure (chapter 13), not on its own. For the ordinary jobs the table seems to recommend it for — "lots of inserts", "a queue", "a growable sequence" — a dynamic array or a deque wins, because the constant factor the table discarded is a cache miss on every step, and it is bigger than the asymptotic difference it was hiding.

A dict is an array with a hash for an index

Your service keeps sessions in a dict, session id to record, and you have never thought about it because it just works. Every complexity table describes it with two characters, O(1), and that is genuinely the least interesting thing about it. Underneath the dict are four decisions, and all four are visible from the outside once you know where to look: how a key becomes an array slot, what happens when two keys want the same slot, how full the array is allowed to get, and what a deletion leaves behind. Get those and the O(1) stops being a fact to memorise and becomes a bet you can see the terms of.

From a key to a slot

An array reaches element i with arithmetic on i. A dict has keys, not indices ("session:8a3f", not 7), so the first job is to turn a key into an array slot, and that is what a hash function is for. hash(key) grinds the key into an integer, often an enormous one. The table has some fixed number of slots. Folding the first into the second is modular arithmetic: divide by the number of slots and keep the remainder, which is guaranteed to land in 0 … slots−1. That is all % is doing — squashing an unbounded integer down into the range of the array.

CPython never actually divides, because it keeps the table size a power of two, and for a power of two the remainder is just the low bits of the number:

h = 9999999967
h % 8   = 7    h & 7   = 7
h % 256 = 223    h & 255 = 223

& 7 keeps the bottom three bits and throws the rest away — the same answer as % 8, in one instruction instead of a division. Power-of-two table sizes exist precisely so this substitution is legal, and nearly every hash table you will meet is built that way.

Now a genuine surprise about Python specifically. Its integers hash to themselves ([hash(i) for i in range(6)] is [0, 1, 2, 3, 4, 5]), and the source is unrepentant about it (Objects/dictobject.c, v3.11.15):

Most hash schemes depend on having a "good" hash function, in the sense of simulating randomness. Python doesn't … in a table of size 2**i, taking the low-order i bits as the initial table index is extremely fast, and there are no collisions at all for dicts indexed by a contiguous range of ints.

A dict keyed by range(1000) has zero collisions and fills its slots in order, because the hash is the identity. Randomness was never the goal here; cheapness was, and the collisions that a lazy hash creates were made someone else's problem — the probe sequence's.

Two keys, one slot

Build the flat array yourself and the collision problem shows up immediately. Here is a hand table of eight slots, keyed by user id (ids are ints, so the initial slot is id & 7):

  put key   17 -> slot 1
  put key    3 -> slot 3
  put key   25 -> slot 2  (slot 1 taken, probed 1 on to 2)
  put key   11 -> slot 4  (slot 3 taken, probed 1 on to 4)
  table: ['-', 17, 25, 3, 11, '-', '-', '-']

Key 25 wants slot 1 (25 & 7), but 17 is already there, so it steps to slot 2. This is open addressing: there is one flat array, and when your slot is taken you go looking for another one in the same array. It is not what the textbooks draw — the textbook picture has each slot holding a linked list of everything that hashed there, called chaining, which is what Java's HashMap does. CPython has no chains and no per-entry lists. One array, and a rule for where to look next.

The whole design is in that rule. Stepping to the very next slot, the way the demo does, is simple but it makes collisions clump. CPython instead jumps around using the rest of the hash:

    perturb >>= PERTURB_SHIFT;      /* PERTURB_SHIFT is 5 */
    j = (5*j) + 1 + perturb;
    use j % 2**i as the next table index;

5*j + 1 alone visits every slot in the table exactly once before repeating — from slot 5 in an eight-slot table the order is 5, 2, 3, 0, 1, 6, 7, 4 — so a probe never gets stuck in a corner. The perturb term mixes in the high bits of the hash, which the initial & mask ignored. Without it, two keys that agree in their low bits would follow the identical probe path forever; with it, they diverge after the first step. Hold that thought — it is about to be the difference between a slow dict and a broken one.

How full is too full

The load factor, α, is how full the array is: entries over slots. Here is what probing costs as α climbs, measured on a table with random keys, against the formulas Knuth derived (his "closed forms", in brackets):

 load factor   successful lookup        insert / miss
        0.66        1.97  (1.97)         4.91  (4.83)
        0.75        2.52  (2.50)         8.97  (8.50)
        0.90        5.75  (5.50)        56.71 (50.50)
        0.95       11.29 (10.50)       243.98 (200.50)
        0.99       57.33 (50.50)      4621.14 (5000.50)

A successful lookup grows as 1/(1−α). But an insert or a miss grows as 1/(1−α)², because it has to probe until it finds an empty slot, and empty slots are exactly what is running out. Squaring turns a slope into a wall: five probes at two-thirds full, but 244 at ninety-five percent. That is why the cliff is a cliff and not a ramp. So CPython refuses to get near it — it resizes the table at two-thirds full, USABLE_FRACTION in the source, sitting deliberately just below the knee. You can watch the resizes fire from outside, at two-thirds of 8, 16, 32, 64, 128, 256, 512:

 len before insert  sizeof after
                 5           272
                10           464
                21           832
                42          1584
                85          3328
               170          6576
               341         13056

Each resize grows the table to about three times the live entry count (GROWTH_RATE is used*3). Because it counts live entries, not slots, a dict that has had as many deletions as insertions comes out of a resize smaller than it went in.

What deletion leaves behind, and the order that came free

You cannot blank a slot when you delete from an open-addressed table. Some other key may have probed past this slot on its way to its own home, and an empty slot ends a probe — blank it and you cut that key off from its own data. So a deletion writes a tombstone, a marker meaning "occupied once, keep walking":

Dummy slots cannot be made Unused again else the probe sequence in case of collision would have no way to know they were once active.

The last decision is a gift nobody asked for. Modern CPython splits the dict in two — a small array of indices, and a dense array of (hash, key, value) entries that is only ever appended to:

+---------------------+
| dk_indices[]        |   <- the hash table proper: an index into dk_entries
+---------------------+
| dk_entries[]        |   <- (hash, key, value) triples, appended in order
+---------------------+

That split was done to save memory — the index array can use one byte per slot for small tables instead of a full entry. But it means the entries sit in the order they were inserted, and, in the source's words, "we can get insertion order by just iterating dk_entries." Insertion order was a side effect of a memory optimisation. It was an implementation detail in 3.6 and became a language guarantee in 3.7.

What the O(1) is actually resting on

Every "O(1)" for a dict is an average, and the average assumes one thing: that your hashes spread out roughly at random, so most keys find their slot on the first probe. Break that assumption and watch what happens. Three dicts of 4,000 keys — ordinary objects, then keys whose hashes differ only in the high bits, then keys whose __hash__ returns 0 for everything:

  well-distributed hashes       0.168 ms   1.0x
  high-bit-only difference      0.585 ms      3.5x
  every key hashes to 0       343.924 ms   2052.2x

Two thousand times slower, and it gets worse with size — the all-collide case quadruples every time the key count doubles, which is O(n²) hiding inside the structure whose whole reputation is O(1). Nothing is broken; the average-case bound was always conditional on the hashes behaving, and a __hash__ that returns a constant violates it completely. Notice the middle row, though: keys colliding only in their low bits cost a mild 3.5×, not quadratic, because the perturb term pulls in the high bits and rescues them. The perturbation you met three sections ago is the thing standing between "a bit slower" and "denial of service".

This is also why you almost never see the attack with string keys: Python hashes strings with a randomised algorithm (siphash13), seeded differently in every process, so an attacker cannot predict which strings collide. Print hash("session:8a3f") in three fresh interpreters and you get three different numbers. The exposure that remains is a __hash__ you wrote — every engineer has written one, and almost none have measured one.

When to reach for it

Reach for a dict — or a hash table in any language — whenever the job is "find the value for this key", and lookup, insert and delete by key are the operations that matter. It is the right default for any keyed store, and its O(1) holds up in practice as long as your keys hash sanely. What you give up is every question about order: a hash table scatters keys across the array on purpose, so it cannot tell you the smallest key, the next key after this one, or everything between two bounds — and if you find yourself needing any of those, you are looking at the structures in the next several chapters.

A set is the same machine, tuned for "have I seen this?"

You are processing a stream and you need to skip anything you have already handled. The reflex is a set of seen ids, and a membership test on every item. It is the right reflex, and the structure under it is the last chapter's hash table with the values torn out — but "torn out" undersells it, because the people who maintain CPython built the set its own implementation on purpose, and the reasons are a clean lesson in tuning a structure to its job.

Keys, and nothing but keys

A set stores keys and associates no values with them. That single change turns the hash table into a machine for one question — is this thing present? — and the answer is a hash and a probe, O(1), exactly as it was for a dict lookup:

  stream: ['a1', 'b2', 'a1', 'c3', 'b2', 'a1']
  first-seen only: ['a1', 'b2', 'c3']
  set literal dedups: {1, 2, 3}
  paid & active (both):      {'u2', 'u3'}
  paid | active (either):    {'u1', 'u5', 'u2', 'u3', 'u4'}
  paid - active (lapsed):    {'u1', 'u5'}

The dedup falls straight out of membership: check in, add if absent. And because both operands are hash tables, the algebra — intersection &, union |, difference - — runs at hash speed. Finding which paid users are still active is one pass that probes the smaller set against the larger, not the nested loop over two lists that the same question in plain code would become. That is the set's real pitch: it makes "which items are in both / either / one-but-not-the-other" cheap.

Why it is not just a dict with the values deleted

It would be reasonable to assume set is dict minus a column, sharing the code. It is not, and the header comment of Objects/setobject.c (v3.11.15) says why:

To improve cache locality, each probe inspects a series of consecutive nearby entries before moving on to probes elsewhere in memory … Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance.

Two design choices follow from that difference. First, on a collision a set does not immediately jump the way a dict does — it scans nine consecutive slots (LINEAR_PROBES is 9) before it perturbs off elsewhere. Nine 16-byte entries is about 144 bytes, two or three cache lines, and the first is already loaded — so a short run of collisions is resolved by reading memory the machine has effectively already fetched, which is far cheaper than nine scattered jumps. A dict, whose keys are usually present and found fast, does not bother; a set, built for the not-found case where you probe until you hit an empty slot, pays for locality up front.

Second, the two structures resize on different schedules. A set grows when it reaches three-fifths full rather than the dict's two-thirds, keeping it sparser so those probe runs stay short, and while it is small it grows to four times the live count on each resize rather than three, buying extra headroom for the membership-heavy workload it expects. Same idea as a dict, different constants — because the question a set answers is a different question.

A set does not preserve insertion order, and you can see it above: paid | active printed in neither input's order. The dict's ordering was a by-product of its compact index-plus-entries layout, and the set does not use that layout, so the order is not there to keep.

When to reach for it

Reach for a set whenever the question is membership — deduplication, "have I seen this id", "is this ip on the blocklist" — or whenever you are comparing two collections for overlap, where the algebra operators turn a nested loop into a single pass. What you give up over a dict is the ability to hang a value off the key: a set remembers that it saw something, never what went with it. And like every hash-based structure, it gives up order — which is what finally sends the next chapter looking for a structure built to keep it.

The tree that sorts itself, until it doesn't

A hash table scatters your keys across an array on purpose — that scattering is exactly what makes a lookup independent of size. But it means the keys land nowhere near each other, and three questions become unanswerable: what is the smallest key, what is the next key after this one, and which keys fall between two bounds. Those are all questions about order, and to answer them cheaply you need a structure that keeps its keys in order without paying to sort them every time. That structure is a search tree, and it has one beautiful property and one failure mode that is not exotic at all — it is the most common way you will actually use it.

From hierarchy to an invariant

A tree is nodes arranged in a hierarchy: one node on top, each node holding links to some nodes below it, called its children, and no cycles — you never loop back to where you started. A binary tree restricts each node to at most two children, a left and a right. So far that is just a shape. What makes it a search tree is a rule about which key goes where, the binary-search-tree invariant: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. That rule holds at every node, all the way down. Building the tree is nothing more than enforcing it on the way in: to insert a key, start at the top and at each node go left if your key is smaller, right if it is larger, until you fall off the bottom, and that is where you attach. Insert eight keys in a jumbled order and watch what the invariant does with them:

  inserted:  50 30 70 20 40 60 80 35
  in-order walk: [20, 30, 35, 40, 50, 60, 70, 80]

The keys went in scrambled and came out sorted, and nothing ever called sort. The tree it built looks like this:

          50
        /    \
      30      70
     /  \    /  \
    20   40 60   80
        /
      35

The sorted output is not a coincidence — it is what you get from visiting the tree in a particular order. Go all the way left first, then take the current node, then go right, and recurse: at every node you emit everything smaller than it before it and everything larger after it, which is the definition of sorted. That traversal is called an in-order walk, and the fact that it yields sorted keys for free is the tree's whole reason to exist. (Traversals in general — this one, and the breadth-first and depth-first walks the graph chapter needs — are the Algorithms guide's subject; here you need only that in-order gives you order.)

Searching uses the invariant directly. To find 35, start at 50 (smaller, go left), then 30 (larger, go right), then 40 (smaller, go left), then 35 — found in four comparisons. Each step throws away a whole subtree, the same halving that made binary search cheap:

  height: 4   search for 35 took 4 comparisons

A search costs the tree's height — the length of the longest path from the top to a leaf. If the tree stays bushy, height is about log₂ n, and search, insert and "find the next key" are all O(log n). That is the advertisement: ordered data, and every operation logarithmic.

The failure mode is the ordinary case

Here is the bill. The height is only log n if the tree is balanced — if the two sides stay roughly even. Nothing in the insert rule guarantees that, and one very common input breaks it completely. Insert keys that are already in sorted order, and every single key is larger than the one before it, so every key goes right, and right, and right:

        n  sorted insert  random insert   log2(n)
     1000           1000             24      10.0
    10000          10000             32      13.3
   100000         100000             39      16.6

Inserting a hundred thousand sorted keys builds a tree of height a hundred thousand. It is not a tree in any useful sense — it is a linked list with an unused left pointer on every node, and every "O(log n)" operation on it is O(n). Search is a full walk, and you have paid for pointers and cache misses to get something slower than an array.

And this is not an adversarial input you have to go looking for. It is what auto-increment primary keys look like (1, 2, 3, 4, inserted in order), which is the most common insertion pattern in any application with a database behind it. The plain binary search tree's worst case is the everyday case, which is why you will essentially never use a plain one.

What balancing buys, and what it costs

The fix is a balanced tree — the family with names like AVL, red-black, and the B-tree of chapter 12. After each insert, a balanced tree checks whether one side has grown too much longer than the other and, if so, does a small local rearrangement to even them out, an operation called a rotation. The mechanics of rotations and the exact rebalancing rules are the Algorithms guide's; what matters here is the trade they buy.

What you get is a guaranteed height of O(log n) for every insertion order, the sorted one included — the failure mode above cannot happen. What you pay is a constant factor of extra work on every write to keep the tree even, and a chunk of fiddly code you have to trust. Random insertion, for reference, lands at about 2.3× the ideal height on its own — 39 against a perfect 17 at a hundred thousand keys — which is fine, and which you cannot rely on, because production data arrives sorted far more often than shuffled.

When to reach for it

Reach for a balanced search tree when you have keys that must stay in order and you need several order-based operations at once — search a key, list a range, find the next or nearest, walk everything in sorted order — with writes arriving continuously so you cannot just sort an array once and be done. That combination is what a tree serves and a hash table cannot. What you give up is the hash table's flat O(1): every operation is O(log n) instead of O(1), and you pay a constant factor on every write for the balancing that keeps it there. When the ordered data also outgrows memory, the same idea takes a different shape — chapter 12.

The tree with no pointers

You want the twenty slowest endpoints out of two million requests. The obvious move is to sort the two million by duration and take the first twenty — and it works, and it is wasteful, because you sorted 1,999,980 things you are about to throw away to find twenty you want. Full order is far more than the question asked for. The question only ever needs the extreme, and there is a structure that keeps the extreme cheap and does not bother ordering the rest. It is a tree, and its best trick is that it is not really a tree at all.

A weaker invariant, and an array

A binary search tree kept a strict rule: left subtree all smaller, right subtree all larger, which is what let it produce fully sorted output. A heap keeps a much weaker rule, the heap invariant, from the heapq documentation:

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero.

Read both sentences, because they are describing two different things. The first says each parent is ≤ its children — nothing about left versus right, only parent versus child. That is enough to force the smallest element to the very top, since nothing can be smaller than its parent all the way up, but it says nothing about the order of siblings. It is a rule about extremes, not about sorting.

The second sentence is the clever part. The tree is stored as a plain array, with node k's children at positions 2k+1 and 2k+2. There are no pointers. A node's children are found by arithmetic on its index, exactly the way an array element was found by arithmetic on i back in chapter 2 — so a heap is one contiguous block, with all the cache-friendliness that bought, and none of the scattered-node cost a real tree of objects pays.

Build one and the array-tree duality is right there:

  pushed 5 3 8 1 9 2 7
  array: [1, 3, 2, 5, 9, 8, 7]   <- heap[0] is always the minimum: 1
  popping in order: [1, 2, 3, 5, 7, 8, 9]
  heapq.heapify same data: [1, 3, 2, 5, 9, 8, 7]

That array is this tree, laid out level by level:

            1 [0]
          /      \
       3 [1]     2 [2]
       /   \     /   \
    5[3]  9[4] 8[5]  7[6]

To push, drop the new value at the end of the array and let it sift up: compare it with its parent, swap if it is smaller, repeat until it settles. To pop the minimum, take heap[0], move the last element into the root, and let it sift down: swap it with its smaller child until the invariant holds again. Each operation walks at most the height of the tree, which for n nodes packed level by level is about log₂ n — so push and pop are O(log n). The hand-rolled version above produces the identical array to CPython's heapq.heapify, because it is the identical algorithm.

Building is cheaper than it looks, and the real job

Turning an existing list of n items into a heap seems like it should cost n pushes at O(log n) each — O(n log n). It does not. heapify is O(n), and you can count the sift steps to see it:

        n   heapify sifts      /n   push-one-by-one sifts   /(n log2 n)
    1,024             962    0.94                   2,312         0.226
    8,192           7,726    0.94                  18,738         0.176
  262,144         246,481    0.94                 596,455         0.126

heapify does about 0.94 sift steps per element, flat at every size — under one, and not growing. The reason is a fact about the shape: in a packed binary tree, half the nodes are leaves that can sift down nowhere, a quarter are one level up and sift at most once, an eighth at most twice. The many cheap nodes at the bottom swamp the few expensive ones at the top, and the sum settles to a constant per element. Pushing one at a time, by contrast, sifts up from the bottom where the tree is tallest, and that genuinely costs n log n.

Now the job the heap was built for. To get the twenty largest of two million, keep a heap of only the twenty largest seen so far; each new item is compared against the smallest of those twenty (the root, O(1) to peek), and either dropped or swapped in. That is heapq.nlargest:

  sorted(log)[:k]      O(n log n)      2116.4 ms   holds all 2,000,000 in a new list
  heapq.nlargest(k)    O(n log k)        80.0 ms   holds 20

Twenty-six times faster, and the speed comes from two places at once. The complexity dropped from n log n to n log k — you are paying log of twenty per item, not log of two million. And the memory dropped from two million to twenty: sorted allocates and fills a new two-million-element list, while nlargest holds twenty things the whole way through, so it never touches the memory system the way the big allocation does.

When to reach for it

Reach for a heap — a priority queue — whenever the job is "give me the smallest (or largest) one next", over and over, as items keep arriving: a scheduler pulling the highest-priority task, an event loop firing the nearest-deadline timer, the top-k of a stream, or any repeated extract-the-extreme. heapq gives you the min-heap; negate your keys, or store (-priority, item) tuples, for a max-heap. What you give up is everything that is not the extreme. A heap cannot find an arbitrary key, cannot tell you whether 47 is present without scanning, and imposes no order on the elements that are not at the top — heap[0] is instant and meaningful, and every other index is just wherever the sifting happened to leave things.

The right structure that loses anyway

Autocomplete has a data structure that looks obviously right. Someone types "che" and you want every term that starts with it — "check", "cheese", "chess" — and there is a structure whose whole reason for existing is prefix lookup, with a property that sounds unbeatable: it finds all the completions of a prefix in time that depends only on the length of the prefix, not on how many terms you are searching. Three characters typed, three steps, whether your vocabulary is a thousand words or ten million. This chapter builds it, and then measures it against a boring sorted array, and the boring array wins. The reason it wins is the most useful thing in the chapter.

One node per character

A trie — the name is from retrieval, and it is usually said "try" to distinguish it from "tree" — stores one node per character, and lets words that share a prefix share the nodes for that prefix. The word "checkout" is a path of eight nodes, c → h → e → c → k → o → u → t; "check" is the first five of that same path, marked as a word-end; "cheese" branches off after "che". Insertion is walking the characters and creating nodes where they are missing; looking up a prefix is walking to the prefix's node and collecting every word-end in the subtree below it.

  completions('che'): ['check', 'checkout', 'cheese', 'chess']
  completions('check'): ['check', 'checkout']
  completions('xyz'): []

Walking to the "che" node took three steps regardless of how many words hang below it, and completions('xyz') bailed out after the first character because no child x exists. That is the pitch, and on paper it is a strong one: the cost of the walk is the length of the prefix, independent of the number of keys. A hash table can tell you if "check" is present, but it scattered its keys on purpose and cannot hand you everything starting with "che"; a trie is built for exactly that question.

Now measure it

Build a trie over two hundred thousand url slugs and race it against the alternative — put the same slugs in a sorted array and binary-search for the prefix with bisect, then walk forward along the array collecting matches while they still share the prefix. Both beat a full scan by a mile; the interesting comparison is trie against sorted array:

  full list scan             28.503 ms per prefix query
  bisect on sorted list       0.002 ms per prefix query
  trie descent                0.017 ms per prefix query

nodes in the trie: 1,378,382  (0.69 nodes per character in the corpus)

The "right" structure loses to binary search on a plain array by about eight times. And this is chapter 2 collecting a debt you forgot you owed. The trie is 1,378,382 separate node objects, scattered across the heap by the allocator, and every character of every descent is a dependent load — follow a pointer to a node you cannot predict, read its children dict, follow the next pointer — each one a cold cache miss, the pointer-chase from the linked-list chapter wearing a different hat. The sorted array is one contiguous block, and bisect runs its binary search in compiled C over memory that arrives in cache lines several elements at a time. The trie has the better complexity and the worse constant, and on a machine with a memory hierarchy the constant is a cache miss per character, which is larger than the asymptotic advantage it was supposed to buy.

This is the same lesson as the O(1) linked-list insert that lost to the array: a complexity class describes the shape of the curve and says nothing about the cache behaviour that decides where the two curves actually cross. The trie's win is real in the limit and invisible in practice at the sizes and on the hardware you have. It is also why the search systems that genuinely need prefix and range lookup at scale — Lucene, LevelDB, RocksDB — store sorted blocks on disk rather than pointer tries: they chose the structure the machine likes.

When to reach for it

Reach for a sorted array plus bisect first, any time the data is mostly read and you need prefix or range lookup — it is the structure the cache hierarchy rewards, and it will usually be both simpler and faster than the clever alternative. Reach for a trie when a measurement says the array is not enough: when the set of keys changes constantly (a sorted array is expensive to insert into, the trouble chapter 8 sent us away from), when you need per-node information the flat array cannot hold — counts, weights, the branching structure itself — or when you are in a compiled language where the per-node pointer chase is cheap enough that the asymptotic win survives. The rule the numbers teach is not "tries are slow". It is benchmark the boring structure before you build the clever one, because the machine has opinions that Big-O does not express.

Relationships need a shape

Almost everything you have modelled on a whiteboard is a graph. Users following users, pages linking to pages, services calling services, tasks that depend on other tasks, cities joined by roads — the moment your data is things and the connections between them, you have a graph, whether or not you called it one. A graph is not a clever structure the way a heap is; it is the plain shape that relationships take. What this chapter is about is the choice you make when you put one in memory, because there are two ways to store the connections and they are good at opposite things.

Vertices, edges, and two ways to hold them

The vocabulary is two words. A vertex (or node) is one of the things: a user, a service, a city. An edge is one connection between two of them: a follow, a call, a road. Edges can be directed (web calls auth, but auth does not call web) or undirected (a road runs both ways). The graph is the set of vertices plus the set of edges, and the only real decision is how to write down the edges.

The first way is an adjacency list: map each vertex to the list of vertices it connects to. In Python that is a dict of lists, and you have almost certainly built one without naming it:

adjacency list (only the edges that exist):
  web    -> ['auth', 'cache']
  auth   -> ['db']
  cache  -> ['db']
  db     -> []
  edge web -> auth?   True

The second way is an adjacency matrix: an n×n grid where the cell in row i, column j holds a 1 if there is an edge from vertex i to vertex j, and a 0 if there is not. Same graph, written as a grid:

          web  auth cache    db
  web       0     1     1     0
  auth      0     0     0     1
  cache     0     0     0     1
  db        0     0     0     0

  4 vertices, 4 edges: matrix holds 16 cells, list holds 4 entries

Both describe an identical graph. The list stored four entries, one per edge. The matrix stored sixteen cells — one for every possible edge, whether it exists or not — and twelve of them are zeros.

The trade is sparse against dense

That difference is the whole decision, and it turns on one property: how many of the possible edges actually exist. A graph where most possible edges are present is dense; one where few are is sparse.

The matrix costs n² cells no matter what, because it reserves a slot for every pair. In exchange, it answers one question in true O(1): is there an edge from i to j? — look at cell [i][j], one array index, done. That is a genuine strength when the graph is dense (the cells would be full anyway) or when you constantly ask about specific edges, and n is small enough that n² is affordable.

The adjacency list costs only as much as the edges you have. Its weakness is the mirror of the matrix's strength: to ask "is there an edge from i to j?" it has to scan i's neighbour list, which is O(number of neighbours), not O(1). But for the graphs you actually meet, that trade is overwhelmingly worth it, because real graphs are sparse. Here is a real one — the import graph of the Python standard library, every module a vertex and every import an edge, read off this machine:

modules (vertices): 179
import edges:       759
density E/V^2:      0.0237   (sparse: adjacency LIST, not matrix)
adjacency matrix would be 32,041 cells; the list holds 759 entries

A hundred and seventy-nine modules could in principle have over thirty-two thousand directed edges between them. They have 759 — about two percent. A matrix would be ninety-eight percent zeros, forty times larger than the graph it describes, and every real-world graph you are likely to build (a social network, a web crawl, a dependency tree, a road map) is this shape or sparser: each vertex connects to a handful of others, not to all of them. So the adjacency list is the default, and the matrix is the special case you reach for when the graph is dense or tiny.

What lives here, and what lives next door

Notice what this chapter did not do: it never walked the graph. Finding the shortest chain of imports between two modules, detecting a cycle, visiting every reachable vertex — the breadth-first and depth-first traversals, Dijkstra's algorithm, topological sort — are the Algorithms guide's subject, because they are algorithms that run over a graph, not the graph itself. And they run over exactly the representation you just chose: a breadth-first search is a queue (chapter 4) walking an adjacency list, a step at a time. This chapter builds the board; the next guide plays the game on it.

When to reach for it

Reach for a graph whenever your data is relationships rather than records — anything you would naturally draw as dots and connecting lines, and anything where the interesting questions are about paths, reachability, or connection. Store it as an adjacency list (a dict of neighbours) by default, because real graphs are sparse and the list pays only for the edges that exist. Reach for an adjacency matrix only when the graph is dense, or small, or you need constant-time "is i joined to j?" checks more than you need to save space. What you give up either way is nothing a single structure could have given you instead — a graph is the shape the problem already had; you are only deciding how to write it down.

When counting comparisons is the wrong question

Every structure so far lived in memory, where the cost model was "count the operations". Here is the constraint that breaks that model. Two hundred thousand short links (an id, a seven-character slug, a target url, a timestamp) take about twenty megabytes once you add an index. Multiply by any real product and the table stops fitting in memory, so it has to live on disk. And on disk, counting comparisons is the wrong question, because a comparison is no longer the expensive thing. This chapter is about the structure that answers the right question, and it turns out to be the thing sitting under every database you have ever queried.

On disk, you count pages

Between disk and memory, data does not move a byte or a word at a time. It moves in pages (fixed blocks, 4096 bytes on this machine), the same way memory moved in 64-byte cache lines back in chapter 2, one scale up. And a page is expensive to fetch. A random page read on this machine costs around 46 microseconds (measured with direct reads over a 512-megabyte file; it is a cloud VM, so that includes a virtualisation tax, and bare-metal flash is faster). Set that against a DRAM access at roughly a tenth of a microsecond, and a page read is hundreds of times slower. Against a comparison between two values already sitting in memory, it is not close at all — the comparison is free.

So the cost model flips. Once your data is on disk, the number of comparisons your algorithm does stops mattering, because they happen in memory where everything is cheap. The only quantity that matters is how many separate pages you had to go and fetch. Count pages, not comparisons.

By that measure, a binary search tree is close to the worst structure imaginable. Each node holds one key and two child pointers, each child lives at some unrelated address, so every step down the tree is a fresh page fetched from disk. A million keys is about twenty levels, which is twenty dependent page reads — twenty times 46 microseconds — each one impossible to start until the previous one lands. The tree that was fine in memory is a millisecond of waiting on disk, almost all of it the disk arm, none of it the comparisons.

So put hundreds of keys in every page

The fix is to stop wasting the page. If fetching a page costs the same whether it holds one key or five hundred, then hold five hundred. A B-tree does exactly that: each node is sized to fill one page, and it packs it with hundreds of keys and hundreds of child pointers instead of one. Now a single page fetch brings back hundreds of keys, you binary-search within the page for free because it is already in memory, and you follow one pointer to the next page down. Fewer, fatter nodes means a far shorter tree, and height is what you are paying for.

Here is a real one, not a diagram of one. Build the two hundred thousand links in SQLite with a unique index on the slug, then read the index's structure straight out of the database file — SQLite exposes it through a virtual table called dbstat, so this is the actual tree on disk:

   depth 1:     1 pages,       4 cells, avg    4.0 cells/page
   depth 2:     5 pages,     840 cells, avg  168.0 cells/page
   depth 3:   845 pages,  199156 cells, avg  235.7 cells/page

One root page at the top holding 4 keys, pointing down to 5 pages, pointing down to 845 leaf pages that hold the actual slugs — about 236 keys per leaf page. The whole index of two hundred thousand keys is three levels deep. To find one slug, you read the root, read one of the 5, read one of the 845, and you have it: three page reads to locate a row among two hundred thousand, plus one more to fetch the row itself from the table. Four pages, sixteen kilobytes of I/O, for an eighty-one-byte row.

Why it is three, and why it stays three

The number of keys a tree holds is its fanout, the number of children per node, raised to its height: fanout^height. With about 236 keys per node, three levels holds 236³, roughly thirteen million. Turn that around and the height is the logarithm of the key count in base 236 — how many times you divide by 236 to reach one — where a binary tree's height is the logarithm base 2. Same idea, enormously bigger steps, and the payoff is dramatic:

           200,000 keys -> B-tree height 3   binary-tree height 18
        10,000,000 keys -> B-tree height 3   binary-tree height 24
     1,000,000,000 keys -> B-tree height 4   binary-tree height 30

Both trees are O(log n) — the B-tree did not beat the binary tree on complexity class, they are the same class. It beat it on the base of the logarithm, and the base is set by how many keys fit in one unit of transfer. Fifty times the data takes the B-tree from three levels to four. A billion keys is four page reads; the binary tree's thirty reads, at 46 microseconds each, is well over a millisecond of pure waiting, against the B-tree's fraction of one. When the unit of transfer is a block, the structure that packs the block wins, and it is not remotely close.

This is the database index, and the bridge out

Ask SQLite how it will run the lookup and it says so in as many words:

(3, 0, 0, 'SEARCH links USING INDEX idx_slug (slug=?)')

SEARCH ... USING INDEX is the four-page descent you just traced. Every relational index you have ever created is a B-tree; so is the sorted-block layout inside RocksDB and LevelDB, and so is a filesystem's map of where a file's pieces live. And the principle generalises past disk exactly the way chapter 2 promised: when transfer is blocked, count blocks — the 64-byte cache line and the 4096-byte page are the same idea at two scales, and one level up the block is a network round trip. What the database does with this index — how the query planner chooses it, why a covering index skips the last fetch, what continuous writes cost the tree — is the Systems design guide's subject, and this is the structure it starts from.

When to reach for it

You will rarely hand-build a B-tree; you reach for it by creating a database index, and the point is to know what you are creating and when it earns its keep. It is the structure for sorted data that is too big for memory and is written to continuously — the case chapter 8's in-memory balanced tree could not reach, and the case chapter 10's sorted array could not, because a sorted array is O(n) to insert into. What you give up is real: an index is disk space, it makes every write do extra work to keep the tree sorted and balanced, and it is a structure the database owns rather than one you control. You accept all of that because the alternative is scanning every page — 4,348 of them for this table, seventeen megabytes — to find one row.

Most real structures are two structures

Here is a move that almost no course teaches as a move, even though the standard library is full of it: when one structure cannot answer both of your questions, use two, and have them point at the same objects. It sounds like a hack. It is the normal way real structures are built, and the clearest example is one you have used without opening — the cache behind functools.lru_cache.

One job, two questions

An LRU cache (least recently used) holds the most recent N items and evicts the oldest when it fills. That one sentence hides two demands that pull in opposite directions. You need to find any item by key in O(1), which is a dict. And you need to know which item is oldest so you can evict it in O(1), which is a question about order — exactly the thing a dict scatters and refuses to answer. No single structure from this whole guide does both: the hash table has the lookup and not the order, a linked list has cheap eviction from the end and not the lookup.

So use both, over the same nodes. A dict maps each key to a node; the very same nodes are strung together in a doubly-linked list kept in recency order, most-recent at the front. On a hit, the dict finds the node in O(1), and because it is a doubly-linked node you are already holding, you unlink it and splice it to the front in O(1) — the chapter 5 splice, finally in its element. On a miss when the cache is full, the node at the back is the least recently used, so you evict it in O(1) and delete its key from the dict.

  put a,b,c        order: ['c', 'b', 'a']
  get a            order: ['a', 'c', 'b']
    evict 'b'
  put d (full)     order: ['d', 'a', 'c']
  get b: None  (gone)

Reading a moved it to the front; adding d to a full cache evicted b, which had drifted to the back, and its key vanished from the dict in the same step. Every write touches both structures — that is the price, and the next section is the point.

This is exactly functools.lru_cache

None of that is a teaching simplification. It is what ships. From Lib/functools.py at v3.11.15:

    PREV, NEXT, KEY, RESULT = 0, 1, 2, 3   # names for the link fields
    cache = {}
    root = []                # root of the circular doubly linked list
    root[:] = [root, root, None, None]     # initialize by pointing to self

cache is the dict from key to link node; root anchors a circular doubly-linked list whose nodes are four-element lists — a previous pointer, a next pointer, the key, and the cached result. On a hit it unlinks the node and relinks it at the front, the move you just watched. On a miss when full it does one lovely trick — rather than allocate a new node and free the old one, it reuses the oldest node as the new one, overwriting its key and result and rotating the root pointer, so a hot cache settles into steady state allocating nothing at all.

Notice what happened to chapter 5's warning. A doubly-linked list was the structure you should almost never reach for, because reaching a node costs an O(n) pointer-chase through cold memory. Here that cost never appears, because you never search the list — the dict hands you the exact node every time, and all the list ever does is the O(1) splice it is genuinely good at. The composite is what makes the linked list worth using: pair it with a hash table, and each structure covers the other's weakness.

When to reach for it

Reach for a composite whenever one dataset has to be fast under two different access patterns at once — by key and by recency, by key and by priority, by id and in sorted order. The pattern is always the same: pick the structure for each access pattern, and have them share the underlying nodes instead of duplicating the data. What it costs you is discipline — every write must update every structure, in the right order, or they drift out of sync in a way a single structure can never do to itself, and a cache that disagrees with its own index is a genuinely nasty bug. That is the real price of the move, and once you have seen it named, you will start noticing it everywhere the standard library kept quiet about it.

The table, with the understanding under it

Somewhere there is a complexity table you were handed once, all O(1)s and O(log n)s in a grid, and it never became understanding because it arrived with nothing underneath it. This is the same table, and it is the whole point of the guide — but you have now built every structure in it from the machine up, watched each one succeed and fail on a real measurement, and priced what it gives up. So read this as a reminder of arguments you have already had, not a list to memorise. Each row is a problem shape, the structure that fits it, and the thing you surrender by choosing it.

The shape you have	Reach for	What you give up	Chapter
A sequence, read by position, walked in bulk	Array / list	Cheap insert or delete anywhere but the end — those shift the tail, O(n)	2, 3
Building a sequence by accumulating	list + append	A little slack memory, and one worst-case copy when it grows	3
Most-recent-first: undo, parsing, backtracking, depth-first search	Stack (a plain list)	Everything but the top — no reaching into the middle	4
Oldest-first: buffering, scheduling, breadth-first search	Queue (collections.deque)	O(n) access to the middle. Never use list.pop(0)	4
Find the value for a key, no order needed	Hash table (dict)	All order — no range, next, nearest, or sorted walk; O(1) rests on sane hashes	6
Membership, dedup, "have I seen this", set overlap	set	Storing a value alongside the key, and all order	7
Ordered keys needing search and range and next/nearest, written continuously in memory	Balanced search tree	Flat O(1): every operation is O(log n), plus a constant factor on writes	8
Repeatedly "give me the smallest/largest next"; top-k; priority scheduling	Heap (heapq)	Everything that is not the extreme — no search, no order among the rest	9
Prefix or range lookup on mostly-read data	Sorted array + bisect first; a trie only if measured	(sorted array) O(n) inserts; (trie) cache locality, so it usually loses in practice	10
Things and the connections between them	Graph: adjacency list if sparse, matrix if dense	Nothing a single structure would have given instead — it is the shape the data had	11
Sorted data too big for memory, written continuously	B-tree (i.e. a database index)	Disk space, extra work per write, and control — the database owns it	12
Two access patterns on one dataset at once (by key and by recency / order / priority)	Two structures sharing nodes (a dict + doubly-linked list, say)	Every write must update both, and they can drift out of sync	13

The one row that is a genuine move rather than a single tool is the last: functools.lru_cache is a dict and a linked list sharing nodes, and most real structures are two structures wearing one name. When nothing in the table fits, that is usually because your problem is two rows of it at once.

Running it on a shape you haven't seen

The table stops where your problem gets unusual, so carry the procedure that built it, not just the rows. Four questions place almost anything.

What operation dominates? Not which operations happen — which one happens on the hot path, a million times. Look up by key points at a hash table; by position, an array; by order, range, or nearest, a tree; the extreme, a heap; membership, a set; a prefix, a sorted array. The structure is chosen by the operation you do most, and the others are what you agree to make slower.

Read-heavy or write-heavy? A sorted array is unbeatable to read and O(n) to write; a tree takes writes but pays a constant factor for them; an immutable-once-built lookup wants the array, a constantly-churning one wants the tree. The read/write ratio moves the answer more than the complexity class does.

Does it fit in memory? If yes, count cache lines and prefer contiguous structures — the array beat the linked list and the trie for exactly this reason. If no, count pages and reach for the block-packed structure, the B-tree. Same logic, different unit of transfer, and it is the pivot the whole second half of the guide turned on.

Do you need two access patterns at once? Then stop looking for the one perfect structure — there is not one — and compose two, sharing nodes.

And under all four, the first chapter's warning: work out what n actually is, and remember that Big-O describes the curve at scale and lies about the small end. When two structures are close on paper, the tie is broken by the constant that the notation threw away and the cache that the notation cannot see — so at the sizes you actually run, measure. The trie chapter is the standing proof that the asymptotically better structure can be the slower one, and the only way to know which side of the crossover you are on is to time it on the data you really have.

Further reading

Primary sources, one line each on what it is good for.

• CPython source, tag v3.11.15 — the implementations this guide reads out rather than describes: Objects/listobject.c for the list growth rule, Objects/dictobject.c for probing, resize, tombstones and insertion order, Objects/setobject.c for the linear-probe layout tuned for the not-found case, Modules/_collectionsmodule.c for deque's 64-slot blocks, and Lib/functools.py for lru_cache built as a dict plus a circular linked list.
• Python standard library documentation — heapq states the heap invariant and the array layout, bisect the binary search over a sorted list, collections the deque. What the language guarantees, as distinct from how it is built.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (4th ed., MIT Press, 2022) — the formal treatments behind the intuition here: heaps (ch. 6), hash tables (ch. 11), binary search trees and balancing (ch. 12–13), amortized analysis (ch. 16), B-trees (ch. 18).
• Ulrich Drepper, "What Every Programmer Should Know About Memory" (2007) — the long-form account of the cache hierarchy behind chapter 2. The absolute numbers have aged; the shape holds.
• Bayer and McCreight, "Organization and Maintenance of Large Ordered Indexes" (1972) — the paper that introduced the B-tree, the structure chapter 12 finds inside a database index.
• Aggarwal and Vitter, "The Input/Output Complexity of Sorting and Related Problems" (1988) — the external-memory model: the cost function that counts blocks moved rather than comparisons made.
• SQLite dbstat virtual table (sqlite.org/dbstat.html) — how chapter 12 read a real B-tree's height and fanout straight out of a live database file.