Engineering Atlas › Foundations

Data Structures Every Backend Uses

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Arrays and dynamic arrays

An array is a block of memory holding elements of the same size side by side. Element i lives at start + i * size, so reading any element is one address calculation and one memory load. Python lists, Go slices and JavaScript arrays are dynamic arrays: when full, they allocate a bigger block and copy everything across. Because the new block is a multiple of the old size, copying averages out to a constant cost per append ("amortised O(1)"). Inserting or deleting in the middle is O(n), because everything after that point must shift.

Hash maps and sets

A hash map stores key-value pairs in an array of slots. A hash function turns the key into a number, and that number modulo the array size picks a slot. Two keys can land on the same slot (a collision), so every implementation needs a rule for that: chain the entries in a small list, or probe the next slots until a free one turns up. Lookups, inserts and deletes are O(1) on average, as long as the table is not too full. When it fills past a threshold, the map grows and rehashes every entry into a bigger array. A set is a hash map with keys and no values, and it is the standard tool for deduplication: "have I seen this request ID before?"

Hash maps give you no order. For "all orders between 9:00 and 10:00", a hash map has to look at every entry.

Sorted trees and B-trees

A balanced search tree keeps keys in sorted order, so lookups, inserts and deletes cost O(log n), and range scans are cheap: find the start, then walk forward. In-memory libraries use red-black trees or similar; the Linux CFS scheduler kept runnable tasks in a red-black tree ordered by how much CPU time each had had (kernel docs). Since Linux 6.6 CFS has been giving way to the EEVDF scheduler, which picks by virtual deadline instead (kernel docs), a reminder that even a textbook structure choice is an implementation detail. Databases use B-trees, where each node is a page holding hundreds of keys. With hundreds of children per node, a tree only three or four levels deep can index billions of rows.

Queues, stacks and ring buffers

A queue is first in, first out; a stack is last in, first out. Queues sit everywhere work is handed from producers to consumers: a web server's accept queue, a job queue, a channel between goroutines. A ring buffer is a fixed-size array used as a queue, with a head index and a tail index that wrap around. It never allocates after creation, which is why log buffers, network card receive queues and Linux io_uring use rings: io_uring's submission and completion queues are ring buffers shared between user space and the kernel (man page). When a ring is full, the producer must block or data is dropped: a design decision, not an accident.

Heaps and priority queues

A binary heap is an array arranged so each parent is no larger than its children. The smallest item is always at index 0; pushing and popping cost O(log n). Heaps power priority queues: timers ("which deadline expires next?"), schedulers, Dijkstra's shortest path, and "top 10 of a million" queries, where you keep a heap of size 10 and drop anything smaller than its minimum. Python's heapq is a binary min-heap on a list, and Go's container/heap works on any slice that implements its interface, with Push and Pop both O(log n). Both are min-heaps, so a max-heap needs negated keys or a reversed Less.

Linked lists

A linked list stores each element in its own node with a pointer to the next (and, in a doubly linked list, the previous). Inserting or removing a node you already hold costs O(1), with no shifting. Finding a node costs O(n), and every step is a pointer jump to a different place in memory. Linked lists are rarely the main store of data in a backend, but they are a perfect partner for a hash map: the map finds the node, the list keeps the order.

The same shape everywhere

Every structure answers "how do I find what I need without looking at everything?" A session store hashes the token. A ride-hailing service buckets drivers by map cell so it only checks nearby ones. A search engine keeps an inverted index from word to documents. An AI assistant doing retrieval keeps a vector index so it compares a question with a few thousand candidates, not millions. Hash, sort, bucket or index: the four answers repeat in every domain.

Down the stack

Layer 1The contract

Each structure promises a cost curve, not a time. A hash map promises O(1) average lookups and O(n) in the worst case, when many keys collide. A dynamic array promises O(1) amortised append, which means most appends are cheap and an occasional one copies the whole array. A B-tree promises O(log n) lookups and ordered iteration. A heap promises O(1) access to the minimum and nothing about the order of the rest. Iteration order is part of the contract too: Python dicts keep insertion order by language guarantee since 3.7 (Python docs), Go's spec leaves map iteration order unspecified and the runtime randomises it so nobody depends on it (Go spec), and a sorted tree iterates in key order.

Layer 2The mechanism

CPython's dict uses open addressing with a compact layout: a small array of indices (dk_indices) points into a dense array of entries stored in insertion order, which is how it keeps order cheaply. It resizes when the table is about two thirds full (USABLE_FRACTION in dictobject.c). Go maps for many years used buckets of 8 slots with an overflow chain and grew incrementally, moving a few buckets on each write so no single insert paid for the whole copy. Go 1.24 switched to a Swiss table design that probes groups of 8 slots using a control byte per slot, and splits each map into tables of at most 1024 entries so one insert never copies the whole map (Go blog). Redis sorted sets combine a hash table (member to score) with a skip list (ordered by score), so both "what is Alice's score?" and "who is ranked 100 to 110?" are fast (t_zset.c); small sets use a compact listpack encoding instead, by default up to 128 entries of 64 bytes each (redis.conf). Postgres B-tree indexes store keys in 8 KB pages, with each internal page pointing to child pages and every level linked as a doubly linked list of pages for range scans; duplicate keys are merged into posting lists by default (Postgres docs).

Layer 3The machine

On real hardware, the cost that dominates is usually memory access, not comparisons. A RAM access that misses the CPU cache costs about 100 ns, while a comparison costs under 1 ns. A hash map lookup typically costs one hash computation plus one or two cache misses. A linked list of one million nodes can cost a cache miss per step, so walking it takes around 100 ms, while summing an array of one million integers takes well under 1 ms. B-trees exist because a disk or SSD reads whole pages: fetching an 8 KB page costs about the same as fetching 8 bytes, so you pack hundreds of keys into each node and binary search inside it in RAM. Resizes are real events too: growing a map of 10 million entries allocates a new table of hundreds of MB and touches every entry, which shows up as a latency spike.

Why it's built this way

  1. Programs mostly ask a few questions: find by key, find in a range, find the smallest, process in arrival order.
  2. Scanning everything is too slow once data is large, so each question gets a structure that avoids the scan.
  3. Memory is fast in order and slow when scattered, so the best real structures are array-backed or page-backed rather than one node per item.
  4. Storage reads whole pages, so on-disk structures make each node as big as a page and keep trees shallow.
  5. No single structure answers every question, so production systems pair them, accepting double the bookkeeping to make two kinds of query fast.

Diagram

flowchart TD
  Q["What do you need to ask?"] --> K["Find by exact key"]
  Q --> R["Find a range or sorted order"]
  Q --> M["Find the smallest or largest"]
  Q --> F["Process in arrival order"]
  K --> HM["Hash map or set, O(1) average"]
  R --> BT["Sorted tree or B-tree, O(log n)"]
  M --> HP["Heap, O(log n) push and pop"]
  F --> QU["Queue or ring buffer, O(1)"]
  HM --> LRU["Hash map + linked list = LRU cache"]

Worked example

A login service stores 1 million active sessions and handles 2,000 requests per second, each of which must find the session for a token.

The first version keeps sessions in a list and scans for a matching token: on average 500,000 string comparisons, plus cache misses as it walks the objects, so a few milliseconds per lookup. At 2,000 requests per second that is several cores busy just on lookups, and it grows with the user count. Switching to a hash map keyed by token makes each lookup a hash plus a cache miss or two: well under a microsecond. The service now spends more time parsing JSON than finding sessions.

Next, the product team wants "the 10 users with the most logins today". Sorting 1 million users costs about 20 million comparisons (n log n). A heap of size 10 needs one pass: each user is compared to the heap's minimum and only pushed if bigger, about 1 million comparisons plus a few heap operations. For a dashboard refreshed every few seconds, that difference matters.

Finally, sessions should expire when the store holds more than 1 million entries, dropping the least recently used. A hash map alone cannot say which entry is oldest without a full scan. Adding a doubly linked list ordered by last use fixes it: on every access, the map finds the node and the list moves it to the front in O(1); on eviction, remove the node at the back. Each entry now carries two extra pointers (16 bytes on a 64-bit machine), or about 16 MB for a million sessions, which is a fair price for O(1) eviction.

In the wild

Trade-offs

StructureStrengthsWeaknessesChoose when
Array or sliceFast index and in-order scans, cache friendlySlow middle inserts, occasional resize copyLists you iterate or index by position
Hash map or setO(1) average lookup, insert, deleteNo order, resize spikes, memory overheadLookup by exact key, deduplication
Sorted tree or B-treeOrdered iteration, range queriesO(log n), more complexRanges, prefixes, "next after X"
HeapCheap smallest or largestRest of the items unorderedTimers, schedulers, top-k
Queue or ring bufferO(1) at both ends, fixed memory for a ringRing is full means block or dropHanding work between producers and consumers
Linked listO(1) insert and remove at a known nodeSlow search, scattered memoryPaired with a map to keep order

Pitfalls in production

Leadership lens

Check yourself

  1. Why can a hash map not answer "all keys between A and C" efficiently, while a B-tree can?

    Show answer

    Hashing scatters keys across slots with no relation to their order, so the map must check every entry; a B-tree keeps keys sorted, so it finds A and walks forward until C.

  2. A dynamic array occasionally copies all its elements on append. Why is append still called O(1)?

    Show answer

    The array grows by a multiple of its size, so copies get rarer as it grows and the total copying work divided by the number of appends is a constant. The single append that triggers a copy is still slow.

  3. Why is an LRU cache built from a hash map and a linked list rather than either one alone?

    Show answer

    The map finds an entry by key in O(1) but has no notion of recency; the list keeps recency order and can move or remove a known node in O(1) but cannot find one quickly. Together they make get, put and evict all O(1).

  4. Why do database indexes use B-trees with hundreds of keys per node instead of binary trees?

    Show answer

    Storage reads whole pages, so one 8 KB read can bring in hundreds of keys; wide nodes keep the tree three or four levels deep, so a lookup costs a few page reads instead of about 30.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →