data-structure-selectionlisted
Install: claude install-skill rustcircle/c101
# Data structure selection
Pick by operation mix, then by constants, then by availability, then measure. The hub
`cs-foundations` section 5 has the short table; storage engines (LSM vs B+tree) stay there.
Graph algorithms are in `graph-algorithms`, sketches in `randomized-algorithms-sketches`.
## 1. Selection procedure
1. **List operations** with frequencies, data size, key type and distribution (uniform, Zipf,
sequential, adversarial) and latency targets (mean vs p99).
2. **Derive required complexities**: e.g. 10^5 updates/s and 10^3 range queries/s over 10^7 keys
rules out O(n) per query.
3. **Shortlist** 2-3 candidates from the tables below.
4. **Compare constants**: a cache miss costs ~100 ns (vs ~1 ns for an L1 hit); one allocation
~20-100 ns plus fragmentation; pointer-chasing structures pay a miss per node, so a B-tree
with 16-64 keys per node beats a red-black tree at equal O(log n).
5. **Check availability**: a maintained library beats a hand-rolled structure unless profiling
proves otherwise.
6. **Microbenchmark** on realistic sizes and distributions (section 11), then decide.
RUM conjecture: of **R**ead cost, **U**pdate cost and **M**emory overhead you can optimise two at
the expense of the third (B-tree: reads; LSM: updates; sorted array: memory and reads). Say which
two you chose.
## 2. Dictionaries and sets
| Structure | Insert | Lookup | Delete | Ordered ops | Notes |
|---|---|---|---|---|---|
| hash table, chaining | O(1) exp | O(1) exp |