Why architecture matters here
Skip lists fail on wrong probability tuning (memory blows up) or naive concurrency (lock contention). Architecture matters because the structure's simplicity is what makes concurrent implementations tractable.
The architecture: every piece explained
The top strip is the structure. Bottom level is a sorted linked list. Higher levels are express lanes with fewer nodes. Level selection uses coin flips (p=0.5 typical). Search starts at top, descends when it overshoots.
The middle row is operations + parallelism. Insert / delete update pointers at all held levels. Concurrency lock-free variants exist (CAS on next pointers + hazard pointers). Range iterators are cheap forward scans on the bottom level. Memory expected O(n) but constants matter.
The lower rows are use. Use cases: memtables, secondary indexes, order books. vs trees: simpler code, similar performance, easier concurrent. Ops: tuning + persistence.
End-to-end flow
End-to-end: RocksDB memtable uses skip list. Writes append + insert. Reads probe top level, descend. Range scans iterate bottom. Snapshots are cheap via versioned nodes. When memtable fills, it's flushed to an SSTable.