Skip to content
Rabin Poudyal
Page 5-1
5-1 Flashcards

5.16Cool but Lesser-Known Data Structures

Probabilistic filters and sketches, editor buffers, unusual trees, compact sets and replication structures: what each one solves, what it trades away, and where real systems use it.

  1. 1Note

    42 cards. Space to flip, 1 to 4 to grade, d to go deeper.

    Practise this deck as a timed round

  2. 2Study
    Loading your progress…

5.16.1Reading list

The works this deck draws on, in the order worth reading them. Cards point to a specific chapter or paper where one fits.

  1. BookDesigning Data-Intensive Applications · Martin KleppmannChapter 3 is the clearest practical account of log-structured merge trees against B-trees, with Bloom filters in their real job. Start here for the storage cards.
  2. PaperSpace/Time Trade-offs in Hash Coding with Allowable Errors · Burton H. Bloom, 1970The original Bloom filter paper in Communications of the ACM. Short, and the framing of trading a small error rate for space is the idea behind the whole probabilistic family.
  3. PaperCuckoo Filter: Practically Better Than Bloom · Bin Fan, David Andersen, Michael Kaminsky and Michael Mitzenmacher, 2014Section 3 explains the filter and its delete rule; the comparison table in section 2 is a good map of the alternatives.
  4. PaperHyperLogLog: the analysis of a near-optimal cardinality estimation algorithm · Philippe Flajolet, Eric Fusy, Olivier Gandouet and Frederic Meunier, 2007The introduction states the accuracy and memory claims; the analysis can be skipped on a first read.
  5. PaperThe Log-Structured Merge-Tree (LSM-Tree) · Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil, 1996The abstract alone explains why batching index writes beats updating a B-tree in place for insert-heavy data.
  6. PaperSkip Lists: A Probabilistic Alternative to Balanced Trees · William Pugh, 1990A short, readable paper with the full algorithms; the first two pages show how random levels replace rebalancing.
  7. EssayText Buffer Reimplementation · Peng Lyu, Visual Studio Code blog, 2018A real engineering story of moving an editor from an array of lines to a piece table backed by a balanced tree, with benchmarks.
  8. PaperConflict-free Replicated Data Types · Nuno Preguica, Carlos Baquero and Marc Shapiro, 2018An encyclopedia-length overview of CRDTs: the definition, state-based against operation-based designs, and the systems that use them.