Skip to content
Episode 10 · The import that grew 45 times slower

Data structures: choosing by the operations you need

Wednesday, 07:40: the nightly price import, 55 seconds in January, ran for 41 minutes and only finished at 07:40, after guests woke up. Search showed yesterday's prices, and nobody had touched the code.

Lists, maps, sets, trees and queues each make some jobs quick and others slow. Pick by what you'll do most, and one line of code can be 1,000 times faster.

30 min foundationChoosing a data structure by its operationsHash maps and sets: average O(1) lookupTrees and graphsQueues (FIFO) and stacks (LIFO)Big-O intuition: O(n) vs O(log n)Database indexes
  1. Problem

    A hotel search endpoint that was instant with 500 hotels takes 4 seconds with 200,000.

  2. Why the simple system fails

    Storing everything in one array and scanning it for every lookup costs time proportional to the data. It's invisible at small sizes and crushing at large ones.

  3. Engineering concept

    Each data structure makes some operations cheap and others expensive. Pick the structure for the operations you do most: lookup by key, range, order, first-in-first-out, relationships.

  4. Technology

    Arrays, hash maps and sets, balanced trees and B-trees, queues, stacks and heaps, graphs; their production forms: indexes, Redis, message queues, graph traversals.

  5. Trade-offs

    Faster reads cost memory, slower writes or lost ordering. There's no best structure, only the best fit for the access pattern.

01

The problem

2 min
Wednesday, 07:40. The nightly price import has only just finished.
  1. Omar · On-call SRE
    Price import: 55 s in January, 41 min last night. Search showed yesterday's prices until it finished.
  2. You · Engineer at StayHub
    We went from 180 hotels to 1,200: about 7× more data. Why 45× slower?
  3. Lina · Senior engineer, your mentor
    Guess before we open the code.
02

The big idea

4 min
Why the import got 45 times slower
The big idea

Pick the data structure for the operation you do most.

The code isn't slow; the shape is wrong. We look rows up by key 240,000 times, and we stored them in a structure made for reading in order.

03

How it works

5 min

A data structure is a way of arranging data so certain operations are fast and others slow. The import keeps 240,000 rows (1,200 hotels × 200 nights) in an : items in order, instant by position, but finding by value means checking items one by one.

What the loop really does
  1. 1
    Take one update

    "Hotel h42, 3 Nov, €118." There are 240,000 of these.

  2. 2
    Scan for its row

    rows.find(...) checks row 1, row 2, row 3… until hotel and date match. On average, half the list: about 120,000 checks.

  3. 3
    Repeat for every update

    240,000 × 120,000 ≈ 29 billion comparisons.

  4. 4
    Grow the data

    7× more updates, each scanning a 7× longer list: 7 × 7 ≈ 45× the work.

  5. 5
    Use the right shape

    A (key → value) reaches any key in about the same time, however many there are. No order. Keyed by hotelId:date: about 480,000 operations in total.

Each structure makes some operations cheap: hash map / for get by key or "is it here?"; sorted structures like a index for ranges and "cheapest first"; a for first in, first out. Ask: what will I do with this data most often?

04

Watch a decision being made

4 min
Worked example

Lina fixes the 41-minute import

The import matches 240,000 price updates against 240,000 rows and takes 41 minutes. Make it fast without new hardware, and prove it.

  1. 1List the operations

    Find a row by hotel + date (240,000 times), change its price (240,000 times), save all rows (once).

    Why: The structure follows from the most frequent operation: "get by exact key".

  2. 2Pick the structure and its key

    Exact-key lookup → a hash map. The key is what identifies a row: "h42:2026-11-03".

    Why: The key must be exactly what the update knows, and unique per row.

  3. 3Build once, look up many times

    Fill the map once, outside the loop.

    ts
    const byKey = new Map<string, Row>();
for (const r of rows) byKey.set(`${r.hotelId}:${r.date}`, r);  // 240,000 inserts, once
for (const u of updates) {
  const row = byKey.get(`${u.hotelId}:${u.date}`);           // one direct lookup
  if (row) row.priceCents = u.priceCents;
  else unknown.push(u);                                      // count, don't crash
}

    Why: Building the map inside the loop would cost as much as the scan.

  4. 4Check the cost, measure again

    About 40 MB of memory on an 8 GB server. On last night's data: 0.4 s instead of 41 min.

    Why: Faster lookups always cost something, usually memory. A fix you haven't measured is a hope.

The whole thing in one line: Name the dominant operation, count the work, pick the structure that makes it cheap, pay the setup once. 41 minutes became 0.4 seconds for 40 MB.
05

In real life

3 min
"Latest items for this person": two structures

Twitter (X): a ready-made list per user

  • Has publicly described keeping each home timeline as a precomputed list in Redis
  • Reading is just reading the top of a list
  • Cost: every post is copied into many lists

Worth it when reads vastly outnumber writes, at huge scale.

A typical web app: an index, queried on demand

  • Each item stored once, with a B-tree index on (owner, created_at)
  • "Latest 50" is one query reading 50 rows of the sorted index

Worth it for most apps until the scale is huge.

06

What goes wrong

3 min
`array.find` or `includes` inside a loop

10,000 × 10,000 = 100 million comparisons, growing with the square of the data.

Instead

Build a Map or Set once before the loop.

Using a hash map when you need order

"Cheapest 20" or "between dates" means scanning and sorting everything.

Instead

A sorted structure: a B-tree index.

Optimising structures for tiny data

For 50 items it's microseconds, and simpler code wins.

Instead

Optimise large data or hot loops, after measuring.

07

Trade-offs

3 min
StructureFast atYou payCan't do
ArrayBy position; reading in orderScans to find by valueFast lookup unless sorted
Hash map / setGet by key, "is it here?"More memory per itemRanges, order
B-treeRanges, sorted readsSlower writes per indexBeat a map at exact lookups
Thursday, 11:00. Search is next.
  1. Karim · CTO
    Load all hotels, prices and rooms left into a Map at startup. No database trips. Reload it every minute.
  2. Lina · Senior engineer, your mentor
    Hotel names and photos, yes. But rooms left changes every few minutes.
  3. Karim · CTO
    Memory is cheap.
08

Your job as tech lead

4 min

Claude Code can write the code for this. You still own the decisions, and you have to know what good looks like to accept or reject its work.

Decisions you own
  • What the code mostly does with the data (by key, by range, "is it here?", in order), because that picks the structure.
  • How big the data will get, not how big it is today: 180 to 1,200 hotels turned 55 s into 41 minutes.
  • What counts as "the same" item: two guest objects with one email are one guest, so de-duplicate on the email.
Tell Claude Code
Our nightly price import takes 41 minutes (55 s in January). It applies 240,000 updates to 240,000 price rows, searching the whole list with rows.find for each. Build a Map keyed by "hotelId:date" once, then look each update up. Keep the output identical. First tell me the operation count before and after and the Map's memory. Then run it on last night's file on staging, compare with the old output row by row, and report the run time.
Check before you accept
  • Claude explains the counts: about 29 billion comparisons before, about 480,000 operations after.
  • The new import produces exactly the same 240,000 prices, not just "runs faster".
  • The key "hotelId:date" identifies one row; no two rows share a key.
Red flags
  • A bigger server or parallel batches, with find still inside the loop.
  • A speed-up measured on a 100-row test file.
  • A hash map used for "prices between €80 and €120".
09

Check yourself

2 min
Q1/3Debugging
This import takes 40 minutes for 200,000 guests. What's the best fix?
for (const g of incoming) {
  const existing = guests.find(x => x.email === g.email);
  if (!existing) guests.push(g);
}
How confident are you?

Next episode: a hotel chain with 10,800 hotels wants to join, taking us from 1,200 to 12,000 hotels. Karim asks what breaks, before the data even exists.

Finished?

Mark it complete to update your skill map.

Next: Big O intuition: how code slows down as data grows
Go deeper (optional)You don't need this to understand the lesson. Open it when a project needs the details: Technical deep dive, Interactive simulation, Visual diagram, Analogy, Check your understanding, Practice ladder, Explain it yourself.
10

Technical deep dive

From 41 minutes to under a second
StructureLookup by keyInsertOrdered / rangeGood for
ArrayO(n) unsorted · O(log n) sorted (binary search)O(1) at end · O(n) at frontOnly if kept sortedOrdered lists, small n
Hash map / setO(1) averageO(1) averageNoLookup by id, de-duplication, counting
Balanced tree / B-treeO(log n)O(log n)YesRanges, sorted reads, DB indexes
Queue (FIFO)n/aO(1)Arrival orderJobs, buffering, fairness
Stack (LIFO)n/aO(1)Reverse arrivalUndo, depth-first search
Heap (priority queue)O(1) peek minO(log n)Only the min/maxSchedulers, top-k
GraphDepends on representationO(1) add edgeNoRelationships, routes
O(1): flat, whatever the size. O(log n): grows very slowly. O(n): grows with the data. Next episode is all about these.
Worked example

Lina fixes the 41-minute import

The nightly import matches 240,000 price updates against 240,000 rows and takes 41 minutes. Make it fast without new hardware, and prove it.

  1. 1List the operations

    Write what the import does and how often: find a row by hotel + date (240,000 times), change its price (240,000 times), save all rows (once).

    Why: The structure follows from the most frequent operation. Here it's "get by exact key", by far.

  2. 2Count the work

    find checks about half the list per call: 240,000 × 120,000 ≈ 29 billion comparisons. In January: 36,000 × 18,000 ≈ 650 million.

    Why: Counting explains the 45× jump and tells you the fix must remove the scan, not speed it up.

  3. 3Pick the structure for that operation

    Exact-key lookup → a hash map. The key is what identifies a row: "h42:2026-11-03" (hotel and date together).

    Why: A map reaches a key in about the same time whatever its size. The key must be exactly what the update knows.

  4. 4Build once, look up many times

    Fill the map once, outside the loop, then use it inside.

    ts
    const byKey = new Map<string, Row>();
for (const r of rows) byKey.set(`${r.hotelId}:${r.date}`, r);   // 240,000 inserts, once

for (const u of updates) {
  const row = byKey.get(`${u.hotelId}:${u.date}`);            // one direct lookup
  if (row) row.priceCents = u.priceCents;
  else unknown.push(u);                                       // count, don't crash
}

    Why: Building the map inside the loop would cost as much as the scan. Once outside: about 480,000 operations in total.

  5. 5Check the cost

    The map holds 240,000 small entries: about 40 MB on a server with 8 GB. Writing to it is fast too.

    Why: Faster lookups always cost something, usually memory. Check that the bill is affordable before shipping.

  6. 6Measure again

    Run on last night's data: 0.4 s instead of 41 min. Add the unknown count to the import log.

    Why: A fix you haven't measured is a hope. The unknown count catches updates for hotels we don't have.

The whole thing in one line: Lina named the dominant operation (get a row by hotel and date), counted the 29 billion comparisons the array caused, and replaced the scan with a map built once: 41 minutes became 0.4 seconds for about 40 MB of memory.
sql
-- The same idea inside PostgreSQL: an index is a sorted structure (a B-tree)
CREATE INDEX idx_rooms_city_price ON rooms (city, price);
SELECT * FROM rooms WHERE city = 'Lisbon' AND price < 12000 ORDER BY price LIMIT 20;
Ranges and "cheapest first" need order. A hash map can't do that; a B-tree index can. Each index also slows every write a little.
11

Interactive simulation

12

Visual diagram

Click a component

One hotel platform, five access patterns, five structures (in memory and in infrastructure).

13

Analogy

  • At a hotelThe guest register, line by lineIn codeAn array (list)
  • At a hotelThe key rack: slot 314 for room 314In codeA hash map
  • At a hotelThe VIP list: on it or not?In codeA set
  • At a hotelReservations book sorted by dateIn codeA sorted tree
  • At a hotelThe line at check-inIn codeA queue
  • At a hotelThe concierge's city mapIn codeA graph

Where the analogy breaks: a key rack has a fixed number of slots. A hash map grows as you add keys, and it quietly uses extra memory to stay fast.

14

Check your understanding

Q1/3Reasoning
Binary search over 1,000,000 sorted records halves the range at each step. About how many comparisons does the worst case need?
comparisons
How confident are you?
15

Practice ladder

Step 1 · Trace

Trace the blocked-cards check

Scenario Warm-up

At payment, StayHub checks whether a card is on the fraud list:

const blocked: string[] = loadBlockedFingerprints(); // 50,000 fingerprints
function isBlocked(fp: string) { return blocked.includes(fp); }

StayHub takes about 400 payments a day. For one payment with a card that is not blocked, how many comparisons does isBlocked do? And for one day? Then say what changes if blocked becomes a Set.

Step 2 · Complete

Finish Lina's grouping code

Code Practice

Each morning, StayHub emails every hotel owner the list of yesterday's bookings. There are 1,200 hotels and about 400 bookings a day. The current code:

for (const hotel of hotels) {
  const theirs = bookings.filter(b => b.hotelId === hotel.id);
  if (theirs.length) sendDigest(hotel, theirs);
}

Lina's rewrite has gaps. Fill in the two ___ lines, and say how many comparisons the old and new versions do.

const byHotel = new Map<string, Booking[]>();
for (const b of bookings) {
  ___                       // get this hotel's list, or a new empty one
  ___                       // add the booking and store the list
}
for (const [hotelId, theirs] of byHotel) sendDigest(hotelsById.get(hotelId)!, theirs);
Step 3 · Solve

"Recently viewed hotels"

Design Practice

Maya: "On the home page, show each guest the last 5 different hotels they viewed, newest first."

Guests view about 20 hotels per visit, often the same hotel several times. Choose the data structure(s) for one guest's list, and explain what happens on each view and on each home-page load. Say what you'd do about duplicates and old entries.

Step 4 · Decide

Index every column?

Decision Stretch

The bookings table has 14 columns and gets about 400 inserts a day, plus updates when guests change dates. The slow queries Omar found:

  • find bookings by guest_email (guest support, 300 times a day)
  • latest bookings for one hotel by (hotel_id, created_at) (owner dashboard, 8,000 times a day)

A teammate proposes indexing all 14 columns "to be safe". Write your decision: "We chose X over Y because…, accepting the risk of…".

16

Explain it yourself

Explain how you'd choose between an array, a hash map and a tree for a new feature, using a hotel example.

0 words