Probabilistic & Hybrid Data Structures: Bloom Filters, Skip Lists, and LSM-Trees

In undergraduate Computer Science, we grade students on $100%$ deterministic exactness. In hyper-scale distributed systems, however, insisting on $100%$ exactness in RAM can bankrupt your cloud infrastructure—while trading a $0.1%$ false-positive rate for $95%$ less memory is how systems like Redis, RocksDB, Apache Cassandra, and Google Chrome survive at scale.

---

Welcome to the tenth and final installment of our series, From Lecture Hall to Production.

Across the first nine articles, every data structure we analyzed—Dynamic Arrays, Linked Lists, Stacks, Ring Buffers, Hash Tables, AVL/B+ Trees, Heaps, Tries, and DAGs—shared a sacred guarantee: deterministic certainty. If set.has(key) returned true, that key was $100%$ present.

Now imagine you are architecting a distributed database or global API gateway facing three real-world scale walls:

1. The Cache Penetration / Negative Lookup Wall: Malicious bots or mistyped URLs query $50,000$ non-existent user IDs per second. Every single lookup misses your Redis cache and slams your primary disk database—only to discover the row doesn't exist! Storing all 1 billion existing 64-byte email strings in a RAM Hash Set would consume over $64\text{ GB}$ of memory (which you can calculate with our Data Size Converter).
2. The Concurrent Tree Lock Contention Wall: You need an in-memory sorted index (like Redis ZSET leaderboards) supporting $O(\log n)$ range queries across multiple threads—without complex global AVL/Red-Black tree rotation locks.
3. The Random Disk Write Wall: You need to ingest $500,000$ write events per second on SSDs, where B+ Tree random in-place page updates bottleneck on disk I/O.

Let us examine the three graduate-level structures that conquer these walls: Bloom Filters, Skip Lists, and Log-Structured Merge-Trees (LSM-Trees).

---

1. Bloom Filters: Answering "Is It Definitely Not Here?" in Bits per Key

Invented by Burton Howard Bloom in 1970, a Bloom Filter is a space-efficient probabilistic set backed by a compact bit array of $m$ bits (all initialized to 0) and $k$ independent hash functions $h_1(x), h_2(x), \dots, h_k(x)$.

How a Bloom Filter Works

• To add(item): Compute the $k$ hash positions $p_i = h_i(\text{item}) \bmod m$ and set bitArray[p_i] = 1 for all $i \in {1 \dots k}$.
• To mightContain(item): Check all $k$ bit positions bitArray[p_i]:
  • If any single bit is 0, the item was definitely NEVER inserted ($0%$ False Negatives!). You can immediately abort an expensive disk read or network RPC!
  • If all $k$ bits are 1, the item is probably present—with a mathematically tunable False Positive probability $p$ caused by bit overlap from other items.

flowchart TB
    subgraph InsertOp["1. add('user:42') sets k=3 bit positions to 1"]
        direction LR
        Key1["'user:42'"] -->|"h1=1, h2=4, h3=7"| Bits["Bit Array (m=8):<br/>[0:0 | 1:1 | 2:0 | 3:0 | 4:1 | 5:0 | 6:0 | 7:1]"]
    end

    subgraph QueryMiss["2. mightContain('user:99') -> h1=1 (1), h2=3 (0!), h3=7 (1)"]
        direction LR
        Key2["'user:99'"] -->|"Bit 3 is 0!"| DefNo["DEFINITELY NOT PRESENT (100% Certain)<br/>Skip Expensive Disk / DB Read!"]
    end

The Optimal Sizing Equations Taught in Graduate Systems Courses

Given an expected number of elements $n$ and a desired false-positive probability $p$ (e.g., $p = 0.01$ for $1%$), how many bits $m$ and how many hash functions $k$ are optimal?

$$m = -\frac{n \ln p}{(\ln 2)^2} \approx -2.08 \cdot n \ln p \qquad \text{and} \qquad k = \frac{m}{n} \ln 2 \approx 0.693 \frac{m}{n}$$

Put those numbers in perspective: to achieve a $1%$ false-positive rate, a Bloom Filter needs only $9.6\text{ bits}$ ($1.2\text{ bytes}$) per item—regardless of whether the original keys are 36-byte UUIDs or 2,000-byte URLs! Storing 100 million keys takes just $114\text{ MB}$ of RAM instead of $8\text{ GB}$!

---

2. Skip Lists: Probabilistic Express Lanes that Replace Balanced Trees

Invented by William Pugh in 1989, a Skip List achieves the exact same $O(\log n)$ search, insertion, deletion, and range-scan complexity as an AVL or Red-Black Tree—without a single tree rotation!

How a Skip List Works

1. Level 0 (Bottom Layer): A standard sorted Singly Linked List containing all $N$ elements.
2. Higher Levels ($1 \dots L_{\max}$): "Express lanes" that skip over intermediate nodes. When a new node is inserted at Level 0, we flip a fair coin (probability $p = 0.5$, or using our Random Generator concepts): as long as the coin lands Heads, we promote the node one level higher into the express tower!
3. Because half of Level $i$ nodes appear in Level $i+1$, the expected height is $\log_2 N$, and searching from the top-left express lane drops down staircase-style in $O(\log N)$ expected time.

flowchart LR
    subgraph SkipList["Multi-Level Probabilistic Skip List (Search Path for 45: H -> 20 -> 40 -> 45)"]
        direction TB
        L2["Level 2 (Express):  HEAD ------------------------> [20] ----------------------------------------> NIL"]
        L1["Level 1 (Fast):     HEAD ---------> [10] --------> [20] ----------------> [40] -----------------> NIL"]
        L0["Level 0 (All Keys): HEAD -> [05] -> [10] -> [15] -> [20] -> [30] -> [40] -> [45] -> [60] -> NIL"]
    end

Why did Salvatore Sanfilippo (antirez), creator of Redis, choose a Skip List (ZSET) over a Red-Black Tree?

• Range queries (ZRANGEBYSCORE) simply drop to Level 0 at the start key and walk linear next[0] pointers—matching B+ Tree leaf scan simplicity.
• Inserting or deleting a node only updates predecessor pointers in local levels—making Lock-Free Concurrent Skip Lists (ConcurrentSkipListMap in Java, RocksDB MemTable) vastly simpler than rebalancing a concurrent tree!

---

3. LSM-Trees (Log-Structured Merge-Trees): How Modern Databases Fuse All Three

How do write-intensive databases like RocksDB, Apache Cassandra, ScyllaDB, LevelDB, and InfluxDB ingest hundreds of thousands of writes per second? They combine an Append-Only Log, a Skip List, and Bloom Filters into an LSM-Tree:

flowchart LR
    Write["Incoming Write<br/>put(key, val)"] --> WAL["1. Append to Sequential Disk WAL<br/>(Write-Ahead Log: O(1) Sequential I/O)"]
    Write --> MemTable["2. Insert into In-Memory Skip List<br/>(MemTable: O(log N) in RAM)"]
    MemTable ==>|"Flush when full"| SSTable["3. Immutable Sorted String Tables (SSTables on Disk)<br/>Guarded by In-Memory Bloom Filters!"]

1. Writes never overwrite disk pages in place! They append sequentially to a disk Write-Ahead Log (WAL) and insert into an in-memory Skip List (MemTable).
2. When the MemTable fills up, it is flushed sequentially to disk as an immutable, sorted SSTable (Sorted String Table).
3. Reads check the MemTable first; before touching any disk SSTable, the database checks that SSTable's in-memory Bloom Filter—skipping $99%$ of disk files that don't contain the key!

---

4. Under the Hood: Testable Double-Hashing Bloom Filter & Skip List

Below is a complete, zero-dependency TypeScript implementation of both:

1. A Kirsch-Mitzenmacher Double-Hashing Bloom Filter (which mathematically generates $k$ independent hash probes from just two 32-bit hashes $h_1(x)$ and $h_2(x)$, plus theoretical vs. empirical false-positive verification).
2. A Probabilistic Sorted Skip List supporting $O(\log n)$ insert, get, and range(min, max) queries.

Copy and run this code directly in the JS/TS Playground:

/**
 * 1. Kirsch-Mitzenmacher Bloom Filter backed by a Compact Uint32Array Bitset
 * Uses double hashing: g_i(x) = (h1(x) + i * h2(x)) mod m
 */
class BloomFilter {
  private readonly bits: Uint32Array;
  private readonly bitCount: number;
  private readonly hashCount: number;
  private _insertedCount: number = 0;

  constructor(expectedItems: number, targetFalsePositiveRate: number = 0.01) {
    const ln2 = Math.LN2;
    // Optimal bit count m = -(n * ln(p)) / (ln(2)^2)
    this.bitCount = Math.max(
      64,
      Math.ceil((-expectedItems * Math.log(targetFalsePositiveRate)) / (ln2 * ln2))
    );
    // Optimal hash function count k = (m / n) * ln(2)
    this.hashCount = Math.max(1, Math.round((this.bitCount / expectedItems) * ln2));
    this.bits = new Uint32Array(Math.ceil(this.bitCount / 32));
  }

  public add(key: string): void {
    const [h1, h2] = this.hashPair(key);
    for (let i = 0; i < this.hashCount; i++) {
      const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.bitCount;
      this.setBit(bitIndex);
    }
    this._insertedCount++;
  }

  /**
   * Returns false -> 100% guaranteed NOT in set (Zero False Negatives).
   * Returns true  -> Present with (1 - FP_Rate) confidence.
   */
  public mightContain(key: string): boolean {
    const [h1, h2] = this.hashPair(key);
    for (let i = 0; i < this.hashCount; i++) {
      const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.bitCount;
      if (!this.getBit(bitIndex)) {
        return false;
      }
    }
    return true;
  }

  public telemetry() {
    // Theoretical FP rate: (1 - e^(-k * n / m))^k
    const theoreticalFp = Math.pow(
      1 - Math.exp((-this.hashCount * this._insertedCount) / this.bitCount),
      this.hashCount
    );
    return {
      insertedItems: this._insertedCount,
      bitCount: this.bitCount,
      byteSize: this.bits.byteLength,
      hashFunctionsK: this.hashCount,
      estimatedFalsePositiveRate: Number(theoreticalFp.toFixed(5)),
    };
  }

  private setBit(bitIndex: number): void {
    this.bits[bitIndex >>> 5] |= 1 << (bitIndex & 31);
  }

  private getBit(bitIndex: number): boolean {
    return (this.bits[bitIndex >>> 5] & (1 << (bitIndex & 31))) !== 0;
  }

  private hashPair(key: string): [number, number] {
    // Hash 1: FNV-1a 32-bit
    let h1 = 0x811c9dc5;
    // Hash 2: DJB2A 32-bit
    let h2 = 5381;
    for (let i = 0; i < key.length; i++) {
      const code = key.charCodeAt(i);
      h1 ^= code;
      h1 = Math.imul(h1, 0x01000193);
      h2 = (Math.imul(h2, 33) ^ code) >>> 0;
    }
    return [h1 >>> 0, (h2 | 1) >>> 0]; // Ensure h2 is odd (coprime to powers of 2)
  }
}

/**
 * 2. Multi-Level Sorted Skip List (Redis ZSET / RocksDB MemTable Architecture)
 */
class SkipListNode<K, V> {
  public readonly forward: Array<SkipListNode<K, V> | null>;
  constructor(
    public key: K,
    public value: V,
    level: number
  ) {
    this.forward = new Array<SkipListNode<K, V> | null>(level + 1).fill(null);
  }
}

class SkipList<K, V> {
  private readonly maxLevel: number = 12;
  private currentLevel: number = 0;
  private readonly head: SkipListNode<K, V>;
  private rngState: number = 0x12345678; // Deterministic xorshift32 seed for reproducible tests

  constructor(
    private readonly compare: (a: K, b: K) => number = (a, b) =>
      a < b ? -1 : a > b ? 1 : 0
  ) {
    this.head = new SkipListNode<K, V>(
      undefined as unknown as K,
      undefined as unknown as V,
      this.maxLevel
    );
  }

  /**
   * O(log n) Expected Insert/Update
   */
  public insert(key: K, value: V): void {
    const update = new Array<SkipListNode<K, V>>(this.maxLevel + 1);
    let curr = this.head;

    for (let i = this.currentLevel; i >= 0; i--) {
      while (
        curr.forward[i] !== null &&
        this.compare(curr.forward[i]!.key, key) < 0
      ) {
        curr = curr.forward[i]!;
      }
      update[i] = curr;
    }

    const candidate = curr.forward[0];
    if (candidate !== null && this.compare(candidate.key, key) === 0) {
      candidate.value = value;
      return;
    }

    const newLevel = this.randomLevel();
    if (newLevel > this.currentLevel) {
      for (let i = this.currentLevel + 1; i <= newLevel; i++) {
        update[i] = this.head;
      }
      this.currentLevel = newLevel;
    }

    const newNode = new SkipListNode(key, value, newLevel);
    for (let i = 0; i <= newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }

  /**
   * O(log n) Expected Exact Lookup via Express Lanes
   */
  public get(key: K): V | undefined {
    let curr = this.head;
    for (let i = this.currentLevel; i >= 0; i--) {
      while (
        curr.forward[i] !== null &&
        this.compare(curr.forward[i]!.key, key) < 0
      ) {
        curr = curr.forward[i]!;
      }
    }
    const target = curr.forward[0];
    if (target !== null && this.compare(target.key, key) === 0) {
      return target.value;
    }
    return undefined;
  }

  /**
   * O(log n + k) Sorted Range Scan (Drop to Level 0 at minKey and walk forward[0])
   */
  public range(minKey: K, maxKey: K): Array<{ key: K; value: V }> {
    let curr = this.head;
    for (let i = this.currentLevel; i >= 0; i--) {
      while (
        curr.forward[i] !== null &&
        this.compare(curr.forward[i]!.key, minKey) < 0
      ) {
        curr = curr.forward[i]!;
      }
    }

    curr = curr.forward[0]!;
    const out: Array<{ key: K; value: V }> = [];
    while (curr !== null && this.compare(curr.key, maxKey) <= 0) {
      out.push({ key: curr.key, value: curr.value });
      curr = curr.forward[0]!;
    }
    return out;
  }

  private randomLevel(): number {
    let lvl = 0;
    while (lvl < this.maxLevel && (this.nextRand() & 1) === 1) {
      lvl++;
    }
    return lvl;
  }

  private nextRand(): number {
    let x = this.rngState;
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    this.rngState = x >>> 0;
    return this.rngState;
  }
}

// ============================================================================
// Verification & Execution
// ============================================================================
// 1. Test Bloom Filter False-Negative Guarantee & False-Positive Rate
const bloom = new BloomFilter(1000, 0.01);
for (let i = 1; i <= 1000; i++) {
  bloom.add(`existing-user-${i}`);
}

let falseNegatives = 0;
for (let i = 1; i <= 1000; i++) {
  if (!bloom.mightContain(`existing-user-${i}`)) falseNegatives++;
}

let falsePositives = 0;
for (let i = 10001; i <= 20000; i++) {
  if (bloom.mightContain(`non-existent-user-${i}`)) falsePositives++;
}

console.log("Bloom Filter Telemetry:", bloom.telemetry());
console.log("False Negatives (Must be 0):", falseNegatives);
console.log("Empirical False Positives out of 10,000 unseen keys:", falsePositives);

// 2. Test Skip List Leaderboard / MemTable Range Scan
const leaderboard = new SkipList<number, string>();
leaderboard.insert(1450, "Player-Alpha");
leaderboard.insert(2890, "Player-Nova");
leaderboard.insert(920, "Player-Echo");
leaderboard.insert(2100, "Player-Vortex");
leaderboard.insert(3400, "Player-Zenith");

console.log("Skip List Lookup Score 2100:", leaderboard.get(2100)); // "Player-Vortex"
console.log("Leaderboard Range [1000..3000]:", JSON.stringify(leaderboard.range(1000, 3000)));

---

5. The Complete 10-Part Series Architecture Cheat Sheet

Congratulations on completing the From Lecture Hall to Production series! Here is the master decision matrix linking every data structure in our 10-part curriculum:

Topic & Article	Primary Strength	Asymptotic Sweet Spot	Canonical Production System
1. Dynamic Arrays	CPU L1/L2 cache spatial locality	$O(1)$ index, $O(1)$ amortized push	V8 Packed Arrays, React Hooks, Game ECS
2. Linked Lists	Pointer splicing without memory shifts	$O(1)$ unlink/move given node ref	Linux list_head, Redis LRU Eviction, React Fiber
3. Stacks & Frames	LIFO nested context & backtracking	$O(1)$ push/pop	CPU Call Stack, Wasm VM, Undo/Redo, Parsers
4. Queues & Ring Buffers	FIFO fairness & lock-free streaming	$O(1)$ modulo wrap-around	Browser Event Loop, Audio DSP, Go/Tokio Deques
5. Hash Tables	Unordered key-value lookup	$O(1)$ expected	V8 Maps, Python dict, Consistent Hashing Rings
6. BST, AVL & B+ Trees	Ordered keys & disk-page range scans	$O(\log N)$ strict	PostgreSQL / MySQL B+ Indexes, Linux CFS
7. Heaps & Priority Queues	Instant access to Min/Max deadline	$O(1)$ peek, $O(\log N)$ push/pop	React Concurrent Scheduler, OS Timers, Top-$K$
8. Tries & Radix Trees	Prefix search independent of $N$	$O(L)$ key-length lookup	Autocomplete, Fastify/Go URL Routers, CIDR IP
9. Graphs & DAGs	Dependency waves & shortest paths	$O(V + E)$ topological sort	Git Commit DAG, Vite/Webpack, V8 GC Reachability
10. Probabilistic & Hybrid	Hyper-scale RAM & write throughput	$O(k)$ bits, $O(\log N)$ lock-free	RocksDB / Cassandra LSM-Trees, Redis ZSET