Choose a lookup structure
You need to find records by key: rows by primary key in a storage engine, entries in an in-memory index, keys in a lookup service. Every structure bets on how keys arrive and how they are read; when the bet is wrong, performance falls off a cliff rather than degrading. Which structure fits your keys and your workload?
You will end with a lookup structure, the amplification arithmetic that justifies it, and its failure mode.
Each question removes more of the design space than the next.
Decide
Is the set of keys fixed once built?
A daily snapshot, a dictionary shipped with the code, a file that is never modified.
Why
If the keys never change, nothing needs to support inserts, so the structure can be packed far tighter and probed faster. Most people skip this question, and it is the one with the most leverage.
Do you need keys in order: ranges, prefixes or sorted iteration?
YesGo to 3
Why
A hash table gives constant-time point lookups but can never serve a range, at any price. Order cannot be added later for less than the cost of a sort.
Do many concurrent writers contend on the structure in memory?
Why
When concurrent writers dominate, the cost of coordinating them outweighs the cost of the lookup itself. A skip list uses randomness instead of rebalancing, so writers touch little shared state, even though its single-thread numbers are worse.
Which writes more bytes per byte of data: a B-tree or an LSM-tree?
A B-tree rewrites a whole page per row changed: page size ÷ row size. A leveled LSM-tree rewrites data about size ratio × number of levels times (10 × 3 = 30). With 16 KB pages: 200-byte rows give 80 for the B-tree; 8 KB rows give 2.
Why
Whether a structure is "write-optimized" depends on row size, not on its reputation. The crossover is arithmetic from two numbers you already know, compared against your write-to-read ratio.
Where you can land
A static structure
Use it when the key set is fixed once built.
A minimal perfect hash with a fingerprint per key (to reject keys not in the set), or a sorted run with a sparse index of every Nth key.
What it costs: any change means a rebuild. Immutability is the resource it spends.
Hash table
Use it when lookups are by exact key and order is never needed.
What it costs: no ranges, ever; performance depends on the hash spreading your real keys evenly, and resizing is a pause.
Skip list or lock-free structure
Use it when ordered access is needed and many writers contend in memory.
What it costs: worse single-thread speed and memory use than a balanced tree, bought back as less coordination.
LSM-tree
Use it when ordered access is needed and rows are small enough that a B-tree would rewrite more.
Writes go to memory, then to sorted files merged in the background (compaction).
What it costs: reads may check several files (one per level); range scans merge them all; compaction competes with foreground work. If rows are large: store values outside the tree so compaction rewrites only keys.
B-tree
Use it when ordered access is needed, rows are large, or reads dominate.
What it costs: a page rewrite per changed row; it loses badly when update rate × page/row ratio exceeds the device's write bandwidth.
Whichever you land on
Check the failure mode, not the happy path
What happens under skewed keys, when the structure outgrows memory, and to p99 latency while compaction or garbage collection runs? Every structure here fails as a cliff when its assumption breaks.