Key takeaways

Asymptotics describe how cost grows, not what it is made of. The same O(1) for an array index and a lookup in a distributed table are different invoices: nanoseconds versus milliseconds. O(n) over contiguous memory is often cheaper than O(log n) over scattered nodes while n is modest.

Every structure buys some operations by making others expensive. An array invests in locality and cheap access. A linked list invests in local inserts without shifting a block. A hash table invests memory for fast lookup. A tree invests in order. A heap invests in a fast minimum or maximum without a full sort.

The unit of analysis is the workload, not “the structure.” Read/write mix, object size, sequential versus random access, memory caps, and latency budgets change the winner. “Which structure is faster?” is almost always an incomplete question.

The expensive part is usually not the key comparison — it is moving data. Between registers, caches, RAM, SSD, and the network, prices jump by orders of magnitude. A B-tree looks odd only if you measure it with the logic of a binary tree in RAM; on disk it minimizes expensive page trips.

The same ledger reappears in databases and clusters. Indexes, denormalization, caches, materialized views, replication, and sharding are the same investments: you pay memory, duplication, or complexity to buy lookup, reads, availability, or scale.

A data structure as an economic system

The textbook view of arrays, linked lists, hash tables, trees, and heaps collapses to properties and asymptotic complexity. That answers “how does the number of steps grow with n.” Production code asks a different question: what will this cost on this machine, with this data, with this mix of operations.

The alternative metaphor is economics. Any structure makes some operations cheaper and others more expensive. Memory, CPU, cache, I/O, and the network are different resources with different prices. A data structure is a mechanism for reallocating cost: you decide in advance what you will pay continuously and which invoices you want cheap on the hot path.

This is not decoration. Engineering choice is an acceptable trade-off, not an absolute maximum of performance. The same lens already works at the quality layer: in the economics of testing you buy insurance for the size of the loss, not the floor area of the warehouse. Here the insurance is extra memory, node headers, rebalancing, spare capacity.

What we actually mean by cost

To compare structures honestly you need one model. Six invoices follow. They do not replace Big-O — they say which kinds of cost Big-O hides inside the constant.

Storage cost

Useful payload is only part of the bill. Next to it sit node metadata, pointers, object headers in managed languages, alignment padding, and unused capacity in a dynamic array. A linked list of a million integers on the Java or Python heap easily occupies several times the memory of the same numbers in a contiguous buffer. “Cheap insert” is already paid in bytes that never appear in the textbook drawing of three boxes.

Access cost

Search, index read, key lookup, sequential scan, and random access are different prices even under the same O(1) or O(n) label. A sequential pass over an array feeds prefetchers and SIMD. Random pointer chasing feeds cache misses. A hash lookup adds hash computation; a tree adds comparisons and pointer descents.

Mutation cost

Insert, delete, update in place, shifting neighbours. In an array, insert in the middle is a bulk move. In a list with a known node, two pointer writes. In a hash table, usually a local write plus collision risk. The price of “change” is never the price of “read.”

Maintenance cost

Resize, rehash, rebalance, index updates, keeping invariants. These jobs are invisible in the “average case” of a single operation, and they are the structure’s hidden tax. A balanced tree sells an O(log n) guarantee for rotations on every insert. A dynamic array sells a cheap push for an occasional full copy.

Movement cost

Copies inside RAM, cache misses, traffic between memory hierarchy levels, I/O, network transfer. In practice this invoice settles more arguments than the comparison count. While data fits in CPU cache you argue about nanoseconds. Once it rides an SSD or another host, the structure that saves trips beats the structure with the “better” in-RAM asymptotics.

Synchronization cost

Locks, atomics, contention on a cache line, distributed consensus. A structure that is ideal on one thread can become expensive as soon as eight cores pull on it. Here the economics is no longer about nodes and pointers; it is about how many threads can work without blocking each other.

Why Big-O is not the price of an operation

The same O(1), different real cost

Array access by index is address arithmetic and, with high probability, a cache hit. A hash lookup is a hash, a bucket, maybe several comparisons on collision. A pointer dereference is one hop that may land on another page. A key lookup in a database on another host is often written down as “constant from the client’s point of view,” while inside you pay network, buffers, and pages. All four are easy to label O(1). The invoices differ by orders of magnitude.

O(n) does not automatically mean “bad”

A linear scan over contiguous memory is one of the cheapest ways to process data on a modern machine: locality, prefetch, SIMD. An algorithm that “naively” walks a million integers often beats a “smart” algorithm with a logarithmic number of random jumps. That does not repeal complexity theory. It reminds you that the constant and the access pattern are part of the price.

The practical neighbour of this point is measurement rather than a fight over letters: in JavaScript performance work you freeze a baseline first, then change code. With structures it is the same: “array versus tree” without a workload is a debate about a model, not about a bill.

O(log n) is not always faster than O(n)

While n is hundreds or thousands, a logarithm of random pointer hops easily loses to a linear scan. Each internal tree node is a separate object, often on another cache line. Fewer comparisons, more memory trips. For small maps a sorted array with binary search is often cheaper than a red-black tree: less metadata, better locality, predictable scan.

Complexity as a growth model, economics as a price model

Asymptotics answer: how cost grows. Economics answers: what it is made of. You need both. The first saves you from a structure that explodes at millions of elements. The second explains why on your ten thousand elements the “worse” structure is faster, and why the winner flipped after the move to SSD.

Array, linked list, and hash table

Three basic structures show the same analysis pattern: what you buy, what you pay, which workload justifies them.

Array: pay for movement, buy locality

The model is simple: a contiguous region of memory; an index becomes an address. Cheap — index access, sequential traversal, iteration, cache-friendly processing. Expensive — insert and delete at the front or middle, resize, the need for a contiguous block.

The array’s economic formula: low access cost and low metadata cost in exchange for high cost of structural change. You pay up front by laying elements next to each other. You pay later when the row has to be opened.

A dynamic array adds capacity. Most appends are a write into already allocated space. Sometimes a resize happens: allocate a larger block, copy everything, free the old one. Average append cost stays low; the one-off cost is high. That is not a textbook trick. It is the same principle as batched disk writes and garbage collection: a rare large expense smeared across many cheap steps.

Linked list: pay memory and locality, save shifting

Nodes, pointers, scattered placement. Cheap — insert and delete if the place is already known. No bulk shift of neighbours. Expensive — extra memory for pointers and headers, pointer chasing, cache misses, finding the position. “Insert in the middle in constant time” assumes you are already standing on the right node. Finding that node is often a linear walk, and then the promised cheapness vanishes.

The list paradox: theoretically cheap insert, practically expensive CPU-cache behaviour. The local cost of the operation (“two pointers”) is not the system cost (“miss, miss, miss”). On a 2020s machine a list rarely beats an array on the tasks where the textbook promised a win — because the textbook counted comparisons, not trips through the memory hierarchy.

Hash table: invest memory to cheapen lookup

Hash function, buckets, collision resolution. You buy fast lookup and, on average, fast insert and delete. You pay extra memory, empty buckets, hash computation, collisions, and occasional rehash.

Load factor is an explicit economic dial. Too dense: more collisions, longer chains or probes, higher expected lookup cost. Too sparse: more empty slots, higher memory bill, worse cache density. The formula is simple: more memory → lower expected lookup cost, until you start evicting useful data from cache and run into rehash.

Tree, heap, stack, and queue

Not every structure optimizes “access to an arbitrary element.” Some buy order, some buy one expensive operation, some buy cheapness by forbidding extra behaviour.

Tree: pay for structure, buy order

A binary search tree gives search, insert, delete, and in-order traversal. That is a different purchase from a hash table: you pay not only for “present / absent” but for range, median, nearest neighbour.

Node overhead and random pointer access make a tree more expensive per element than an array. Locality is worse: nodes that are neighbours in key order rarely sit together in memory. Balanced trees add maintenance — rotations and recoloring — to keep the O(log n) guarantee. The guarantee is not free: you pay on every insert so the worst case does not collapse into a linear list.

Range queries are the moment extra structure becomes economically justified. If the workload is point lookup by key, a hash table is usually cheaper. If the workload is “all events in this hour” or “all keys from A to B,” order pays for metadata and rebalancing.

Heap: a structure tuned for one expensive operation

A heap returns the minimum or maximum quickly. You give up a total order and easy arbitrary access. A priority queue is an economic problem: there is no reason to pay for a full sort if the system regularly needs only the next priority element. Schedulers, event processing, Dijkstra — typical buyers of this deal.

The principle is broader than heaps: you do not need to organize all information if the system regularly needs only one access pattern. A full index, a full sort, full normalization are investments. Their payback is computed from the workload, not from the feeling that “this is more correct.”

Stack and queue: cheap because behaviour is restricted

A stack allows a narrow set of operations and LIFO. A queue is FIFO: cheap add at one end, cheap take at the other. The idea: restricting what you may do reduces maintenance cost. The fewer behaviours you must support, the cheaper the structure can be.

That sounds like a textbook truism; in production it is an architectural lever. A task queue is cheaper than a general list with inserts in the middle. A call stack is cheaper than an arbitrary activation graph. The moment you allow “one more convenient operation,” you often buy a new class of invariants and a new tax on every mutation.

When RAM is no longer the main resource

B-trees and the outside world

While everything lives in RAM, you argue about cache misses. Once SSD, filesystems, databases, and the network appear, the unit of cost changes. A disk page trip is orders of magnitude more expensive than a key comparison. The structure that minimizes those trips beats the structure with “elegant” binary branching.

A B-tree is shaped the way it is not out of love for fat nodes. A large branching factor packs many keys into one page and cuts tree height in units of storage trips, not comparisons. The page is the economic unit: data moves in blocks. I/O cost dwarfs a single comparison. The new formula: structure optimization = minimizing expensive data movement.

The same move as in the browser-to-database request path: the bottleneck rarely sits in the layer where it is convenient to count algorithm steps. It sits where data crosses an expensive boundary.

The hidden economy of memory: cache

The hierarchy is familiar: registers, L1/L2/L3, RAM, SSD, network. Temporal locality — reuse what you just touched. Spatial locality — touch neighbours. An array often beats a list not because of Big-O, but because of the cost of moving data between levels of that ladder.

Data-oriented design is the practical conclusion of the same economics: layout is part of the algorithm. A textbook structure smeared across tiny heap objects can keep the “right” complexity and lose on price. An engineer who switches from an array of structs to a structure of arrays is not micro-optimizing for sport — they are changing the movement bill.

A practical neighbour is cache as a system layer: the Node.js cache-stampede write-up shows how cheap cache reads turn into a stampede if you ignore coherence and simultaneous misses. Cache economics is not “put bytes closer”; it is buying latency with memory and consistency risk.

Workload is the real unit of analysis

The same structure has different economies. A mix of 99% reads and 1% writes loves indexes, spare capacity, denormalization. A 50/50 mix punishes every structure with expensive maintenance. Frequent inserts at the front destroy an array and make a deque sensible. Sequential streaming loves arrays and ring buffers. Random key lookup loves a hash table.

So the question should not be “which structure is faster?” but “which structure is cheaper for this workload?”

Workload is the economic passport of the problem. Write it down:

• frequency of each operation class;
• set size and object size;
• request distribution: uniform, hot tail, ranges;
• read/write ratio;
• latency requirements (mean versus tail);
• memory ceiling.

Without that passport, choosing a structure is aesthetics. With it, it is a calculation. The same lesson at schema level: EAV looks flexible while the profile is rare point fields; on reports and bulk reads the economy breaks, because you bought write flexibility at the price of access.

Amortized cost and the real price of memory

Why resize is a good teaching example

Most operations are cheap. Sometimes an expensive copy happens. Average cost is low, worst case is high. If your contract with the system is “almost always fast, occasionally we can wait,” amortization works. If the contract is “every operation fits the latency budget,” a rare spike is a contract breach, not a statistical footnote.

Amortization is spreading a large rare expense across many small regular payments. In real systems the same drawing appears in batching, buffering, garbage collection, and log compaction. You deliberately accumulate cheap dirt so you can pay once for order. That is a good deal while the maintenance pause fits the budget and the dirt does not start choking the hot path.

Memory cost is not just a byte count

Overhead: pointers, object headers, alignment, fragmentation. Two million tiny objects can “weigh” more than the same payload in two large buffers even if the useful fields sum to the same number.

Memory bandwidth: how many bytes you actually have to move to do useful work. A structure with excellent asymptotics and a wide stride through cache can hit the bus before it hits the ALU.

Cache footprint: how much useful information fits in L1 and L2. A dense table of small keys evicts less useful code and data than a sparse mesh of objects.

Garbage collection is a separate tax on object maintenance. A structure that allocates short-lived nodes pays not only allocation but collector work. Sometimes an “immutable” structure is beautiful in code and expensive in pause economics.

From data structures to databases and distributed systems

The economic principles do not stop at the array. They rise to storage and the cluster.

Index, denormalization, cache, materialized view

An index: you pay memory and update time, you buy fast lookup. That is a hash table and a tree lifted onto pages. Practical moves on the same ledger are in query-time cut strategies: index, materialized view, and cache are investments, not a “turn on speed” switch.

Denormalization: you pay duplication, you buy cheap reads. You deliberately break a canonical schema because the profile is many reads of a complex projection and few updates to the source.

Cache: you pay extra memory and staleness risk, you buy latency. A materialized view: you pay storage and maintenance on every source change, you buy a ready answer to a heavy query.

A vector index in production search is another portfolio of the same kind: memory and maintenance for cheap approximate lookup — see vector databases.

When network cost appears

The network is often the most expensive resource: latency, bandwidth, serialization, replication. Replication: you pay storage and synchronization, you buy availability and read performance. Sharding: you pay routing complexity and cross-shard operations, you buy scale. Data locality becomes part of the structure: where the information lives is as much a parameter as array layout in cache.

A distributed hash table, a leader log, a cache at the network edge — all answers to “which resource are we willing to spend to make this operation cheap.” The principle does not change; the unit price of movement does.

A universal analysis template

Before you pick a structure, walk the same template. It is the same for an in-process array, a PostgreSQL index, and a cluster shard.

Storage. How much memory? What metadata tax? How well is capacity used?

Access. Which operations are cheap? Which are expensive? What is the locality?

Mutation. What happens on insert, delete, update? Do you need a shift, a page split, a rehash?

Maintenance. What must be kept continuously: balance, load factor, index freshness, log compactness?

Movement. How much data actually travels between memory levels, to disk, over the network?

Scaling. How does each invoice change as N grows? Where does amortization’s comfort end and the latency budget break?

Workload. For which operation mix is the structure profitable? What happens if writes go from 1% to 30% tomorrow?

If you cannot answer those questions, the “array versus tree” argument has not started — you lack inputs. If you can, the choice usually collapses to one or two structures, and the rest is measurement, not guessing.

A map of data-structure economies

Each structure invests in different resources. It helps to hold that as a portfolio:

The comparison map below is conceptual, not a table of truth for every implementation. Exact numbers depend on language, allocator, load factor, and runtime.

Read the table together with the workload, not instead of it. “High storage” on a hash table can be the best deal in a service with millions of point reads. “Low locality” on a list can be acceptable if nodes are few and insert-at-a-known-node is the whole hot path.

FAQ

Further reading

This article is the first piece of a “computing economics” contour: from structures to algorithms, cache, databases, the network, and scale. Neighbouring write-ups on the same invoices already live on the site.

• Why cheap testing is expensive — the same investment frame and cost of failure, for quality
• JavaScript performance: 8 fixes that matter — measure first, then patch; the same refusal to argue without a baseline
• Database optimization: six strategies — indexes, materialized views, and cache as buying a cheap query
• Why EAV destroys ERP performance — schema flexibility as an expensive access structure
• How the modern web works: browser to database — where expensive movement sits in the request chain
• Vector databases — an index as a memory/search portfolio on another key type
• layercache: stopping cache stampedes — cache as buying latency with a consistency tax

Conclusion

Replace “which data structure should I pick?” with a better question: which resources is the system willing to spend, and which operations must become cheap?

Array, list, table, tree, heap, B-tree are not characters in a ranking. They are different answers to the same economic request. Designing a data structure is managing the cost of moving and transforming information. First the workload passport and the six invoices, then the textbook letter O, then measurement on your data.

A practical step this week: take one hot path in your service and write down what is cheap there (access? insert? range? next priority?), what you already pay (memory, misses, resize pauses, locks), and which structure encodes that deal. Often the argument was about complexity, and the pain was movement.

Possible continuation of the “Computing economics” series: the economics of algorithms; of memory and CPU cache; of databases and indexes; of distributed systems; of latency; of scaling; and a separate piece on why optimizing one resource often raises the cost of another. This article closes the first layer — structure as a portfolio, not as a handbook row.