Labs

Hash table load factor: measure the hyperbola

Fill a linear-probing table to α = 0.5 … 0.95, count probes against the formulas, then time it against chaining.

B-tree key order: UUIDv4 versus UUIDv7

Insert 5 million rows under a random UUID key and under a time-ordered key into PostgreSQL; compare index size, page fill, insert time and WAL.

LSM versus B-tree write amplification, derived and measured

Write small rows and 8 KB rows into RocksDB and LMDB, measure device bytes per user byte, then turn on RocksDB blob files.

Monkey-style filter allocation

Split one Bloom-filter memory budget across LSM levels equally or Monkey-style, count wasted I/Os per million missing-key lookups.

Sparse index granule size

Index a sorted file of 100 million records every G records and time point lookups for G from 64 to 65,536.

Sliding maximum: naive, deque and panes

Compute a sliding maximum over a 10,000-value window naively, with a monotonic deque, and with panes; then feed the deque its best and worst shapes.

Top-k with a bounded heap versus a full sort

Find the top 10 of 20 million numbers with sort | head and with a bounded heap; compare time and peak memory, then read DuckDB's plan.

Bloom filter: measure the false-positive curve and the cache cost

Measure a Bloom filter's false-positive rate at 5 to 20 bits per key against the formula, then time lookups in a 10 MB, a 1 GB and a blocked 1 GB filter.

Count-Min Sketch: head versus tail

Count a Zipf stream of 10 million events with a Count-Min sketch, compare head and tail errors, then find heavy hitters with Misra-Gries and Space-Saving.

HyperLogLog: error, merge and the intersection trap

Check HyperLogLog's error over 20 runs, merge two sketches, then estimate a 1% intersection with HLL and with a Theta sketch.

Do not average percentiles

Compute the p99 of 100 shards by averaging shard p99s and by merging KLL, t-digest and REQ sketches, against the exact pooled p99.

Roaring versus plain bitmap versus sorted array

Size sets of row IDs at five densities as a plain bitmap, a sorted array and a Roaring bitmap, then time a 1% intersection in each.

Elias-Fano and the posting-list size

Store a million sorted doc IDs as int32, delta + varint and Elias-Fano; compare size and random-access time.

False sharing: measure the 64-byte penalty

Eight threads increment their own counters: packed in one line, padded to 64 and 128 bytes, and counted locally.

SPSC ring buffer: head and tail on one line, then on two

Move 100 million items through a single-producer single-consumer ring with head and tail on one line, on separate lines, and with batched publishing.

Persistent tree: measure the cost of path copying

Insert a million keys into a mutable and a persistent binary tree; compare time and memory, hold a snapshot, count shared nodes.

Reader-writer lock against plain mutex on a read-heavy workload

99% reads and 1% writes from 1 to 16 threads under a mutex, a reader-writer lock and an atomic snapshot pointer.

Build a pruning cascade and count rows touched

Prune 1,000 point-in-range queries over 10 million rows through a zone map, a Bloom filter and a sparse index; then shuffle the rows.