Database Internals and Storage Engines Questions

Direct answer

A Bloom filter is a compact, probabilistic structure that answers whether a key might be in a set using far less memory than storing the actual keys, at the cost of allowing false positives, it can wrongly say "maybe present" for a key that is not there, but never false negatives, it never wrongly says "definitely absent" for a key that is there. Databases use this asymmetry specifically to skip expensive work: check the Bloom filter first, and only pay for an actual disk read or file open when it says "maybe," which is exactly the shape of the read-amplification problem log-structured merge-tree (LSM-tree, a storage design that buffers writes in memory and periodically merges them into new sorted on-disk files rather than updating a file in place) engines have, checking whether a key exists in a given on-disk file before deciding whether to open it.

Structured elaboration

What it solves

Without a Bloom filter, checking whether a key exists in a given file means either scanning the file or at least opening it and checking an index; for a point lookup that might not even find the key, a true negative, that is pure wasted I/O. A Bloom filter, held entirely in memory, lets the engine skip opening files that provably do not contain the key, at the cost of occasionally, controlled by the false-positive rate, opening a file that turns out not to have it after all, a wasted read, but far rarer than checking every file unconditionally.

How it works and how the false-positive rate is derived

A Bloom filter is a bit array of size m, all initialized to 0. Inserting a key sets k bits, each chosen by a different hash function applied to the key. Checking a key reads the same k positions: if any bit is 0, the key is definitely not in the set, a bit can only be 0 if nothing ever set it; if all k bits are 1, the key is maybe in the set, because those bits could have all been set by some combination of other keys' insertions rather than this one. The probability of that false collision, the false-positive rate, follows directly from a fill-rate argument: after inserting n keys with k hash functions into m bits, the expected false-positive probability is:

$p \approx \left(1 - e^{-kn/m}\right)^k$

Choosing m and k given n and p

Solving that relationship for the parameters actually chosen, given a target false-positive probability p and an expected element count n, the standard closed-form sizing is:

$m = -\frac{n \ln p}{(\ln 2)^2}$

$k = \frac{m}{n}\ln 2$

Examples of how databases use Bloom filters

RocksDB and Cassandra (a distributed, wide-column NoSQL database built on an LSM-tree storage engine) both attach a Bloom filter to every on-disk sorted file, an SSTable, specifically to skip files during a point lookup; some analytic engines and block-level indexing tools use Bloom-filter-style structures at the storage-block or partition level to skip whole blocks or partitions that provably do not contain a value being filtered on. The common thread is always the same: a cheap, in-memory "definitely not here" check in front of an expensive I/O operation.

Worked example

Computed directly, not estimated, for n = 100,000 expected elements and a target false-positive probability p = 0.01:

$m = -\frac{100{,}000 \times \ln(0.01)}{(\ln 2)^2} \approx 958{,}506 \text{ bits} \approx 117.0\text{ KiB}$

$k = \frac{958{,}506}{100{,}000}\ln 2 \approx 6.64 \rightarrow 7 \text{ hash functions (rounded)}$

That is about 9.6 bits per element, roughly a hundred times less memory than storing even short string keys directly, for a 1 percent or better false-positive rate.

I then built and ran an actual Bloom filter with exactly these parameters, m = 958,506, k = 7, using two independent cryptographic hashes combined via double hashing to generate the k bit positions, rather than Python's built-in general-purpose hash function, which produced visibly correlated, worse-than-predicted results in an earlier draft of this same test, inserted 100,000 distinct keys, and probed it with 50,000 keys guaranteed absent from the inserted set:

import hashlib
import math

def bloom_params(n, p):
    """n = expected element count, p = target false-positive probability.
    Returns (m bits, k hash functions), both rounded to usable integers."""
    m = -(n * math.log(p)) / (math.log(2) ** 2)
    k = (m / n) * math.log(2)
    return math.ceil(m), max(1, round(k))

def proper_hashes(key, k, m_bits):
    # k bit positions via double hashing (Kirsch-Mitzenmacher): derive h1, h2 from two
    # independent cryptographic digests (md5/sha1) instead of Python's built-in hash(),
    # which is not designed for this and showed correlated collisions in an earlier draft.
    kb = key.encode()
    h1 = int.from_bytes(hashlib.md5(kb).digest()[:8], "big") % m_bits
    h2 = int.from_bytes(hashlib.sha1(kb).digest()[:8], "big") % m_bits
    if h2 == 0:
        h2 = 1  # avoid degenerate double-hashing when h2 == 0 mod m_bits
    return [(h1 + i * h2) % m_bits for i in range(k)]

def empirical_fp_rate(m_bits, k, inserted_keys, absent_probe_keys, hashfn=proper_hashes):
    # hashfn takes (key, k, m_bits) and returns the k bit positions to check/set;
    # it defaults to proper_hashes so the Worked example calls below need no change,
    # and it is exactly the seam the Trade-offs section below plugs naive_hashes into
    # to reproduce a correlated-hash failure with the identical m, k, and key sets.
    bitset = bytearray((m_bits + 7) // 8)

    def set_bit(i):
        bitset[i // 8] |= (1 << (i % 8))

    def get_bit(i):
        return (bitset[i // 8] >> (i % 8)) & 1

    for key in inserted_keys:
        for i in hashfn(key, k, m_bits):
            set_bit(i)

    false_positives = sum(
        1 for key in absent_probe_keys if all(get_bit(i) for i in hashfn(key, k, m_bits))
    )
    return false_positives / len(absent_probe_keys)

if __name__ == "__main__":
    n = 100_000
    p_target = 0.01
    m, k = bloom_params(n, p_target)
    print(f"n={n}, target p={p_target}  ->  m={m} bits ({m/8/1024:.1f} KiB), k={k} hash functions")
    print(f"bits per element (m/n) = {m/n:.2f}")

    inserted = [f"key-{i}" for i in range(n)]
    absent_probes = [f"absent-{i}" for i in range(50_000)]
    fp_rate = empirical_fp_rate(m, k, inserted, absent_probes)
    print(f"measured false-positive rate over 50,000 absent probe keys: {fp_rate:.4%}")

    print()
    print("how m and k move as the target false-positive rate changes (n fixed at 100,000):")
    for p in (0.10, 0.01, 0.001):
        m2, k2 = bloom_params(n, p)
        print(f"  p={p:<6} -> m={m2:>9} bits ({m2/8/1024:7.1f} KiB), k={k2}")

Output:

n=100000, target p=0.01  ->  m=958506 bits (117.0 KiB), k=7 hash functions
bits per element (m/n) = 9.59
measured false-positive rate over 50,000 absent probe keys: 0.9660%

how m and k move as the target false-positive rate changes (n fixed at 100,000):
  p=0.1    -> m=   479253 bits (   58.5 KiB), k=3
  p=0.01   -> m=   958506 bits (  117.0 KiB), k=7
  p=0.001  -> m=  1437759 bits (  175.5 KiB), k=10

0.966 percent measured against a 1 percent target, close agreement, and the small gap is expected sampling noise from probing with a finite number of keys rather than the formula's infinite-population assumption.

Trade-offs and pitfalls

Setting the false-positive rate too loosely, a bigger p, smaller m, saves memory but defeats the filter's purpose operationally: more false positives means more wasted I/O actually opening files that turn out empty, eroding exactly the read-amplification benefit the filter exists to provide. Too tight, a very small p, burns memory that could otherwise cache actual data, for a marginal improvement once the overwhelming majority of unnecessary reads are already being skipped. The sizing table above, for the same n = 100,000, shows tightening p by 10x roughly doubling m and adding a few more hash functions, a real cost for a shrinking marginal benefit.

A second pitfall: a Bloom filter's correctness depends on its k hash functions behaving close to independently, and a cheap or correlated hash scheme silently produces a worse real-world false-positive rate than the sizing formula promises, without any error or warning, because the formula's derivation assumes hash independence the implementation did not actually provide. This is not a hypothetical: swapping the same test's proper double hashing (two independent cryptographic hashes) for a scheme that derives all k positions from a single Python hash() call, multiplied by small integers, something that looks like double hashing but is not, since every position is then a linear function of the same one underlying value, reproduces the failure directly, for the identical m and k:

def naive_hashes(key, k, m_bits):
    # Looks like double hashing but is not: every position is a linear function
    # of the SAME single hash() call, so the k positions are correlated with
    # each other instead of behaving independently.
    h = hash(key)
    return [(h * (i + 1)) % m_bits for i in range(k)]

naive_fp = empirical_fp_rate(m, k, inserted, absent_probes, naive_hashes)
print(f"naive (single hash() multiplied by i) measured FP rate: {naive_fp:.4%}  (target {p_target:.2%})")
print(f"naive scheme is {naive_fp/p_target:.1f}x worse than the target, for identical m and k")

Output (this run; the exact figure moves a little run to run because Python randomizes string-hash seeding by default, but it lands in the same range every time, since the correlation is structural, not incidental):

naive (single hash() multiplied by i) measured FP rate: 14.3700%  (target 1.00%)
naive scheme is 14.4x worse than the target, for identical m and k

Same m, same k, same inserted and probed keys as the proper version above, roughly 14x the target false-positive rate instead of matching it, purely from how the k positions were derived. That is the concrete shape of the pitfall: nothing in the API surface of "call hash k times" tells you whether those k calls are actually independent, and the sizing formula's guarantee silently stops holding when they are not.

Direct answer

Binary search needs random access to comparable elements, which a naive whole-file compression scheme destroys, since it is not possible to decompress just the middle of a compressed stream without decompressing everything before it. The fix is to split the sorted array into fixed-size blocks, compress each block independently, and keep a small, always-in-memory sparse index mapping each block's first key to that block's byte offset in the file. A lookup binary-searches the tiny in-memory sparse index, never touching disk, to find the one block that could contain the target key, then decompresses and searches only that one block, which is the same layout idea behind a sorted-string table's (SSTable's) block index in engines like RocksDB (an embeddable key-value store built on a log-structured merge-tree, or LSM-tree, which buffers writes in memory and periodically merges them into new sorted files rather than updating in place) and LevelDB (the earlier, simpler LSM-tree key-value store RocksDB was originally forked from), and behind a full-text search library's term-dictionary blocks.

Structured elaboration

On-disk layout

The file is a sequence of independently compressed blocks, each holding a contiguous, sorted slice of the full key set, a fixed number of keys per block, or a fixed compressed-size budget per block. Each block is self-contained: decompressing block 400 never requires anything from block 399 or block 401.

The block index

For each block, record its first key and its byte offset, and length, in the file. Because there is one entry per block rather than one per key, this index is small, commonly a small fraction of a percent of the data size, and small enough to hold entirely in memory even for a very large underlying array, which is exactly what removes disk I/O from the binary-search step itself.

Lookup algorithm

1. Binary-search the in-memory sparse index for the last entry whose first key is less than or equal to the target key; that identifies the one block that could contain the target, since every other block's entire key range is provably on the wrong side.
2. Seek to that block's recorded offset, read exactly that block's bytes, and decompress only it.
3. Binary-search, or linear-scan for small blocks, inside the decompressed block for the target key.

Compression scheme considerations

Block-level, not element-level, compression is the key trade: compressing each block as one unit, rather than compressing each element individually, gets much better compression ratios, because compression algorithms exploit redundancy across nearby values, but it means the minimum unit of decompression work is one whole block, so block size is a direct trade between compression ratio (bigger blocks compress better) and wasted decompression work (bigger blocks mean more irrelevant data decompressed to find one key).

Worked example

Built and ran this exactly as described: 200,000 sorted integer keys, split into blocks of 128 keys each, each block's keys joined and compressed independently with a standard general-purpose compressor, plus a sparse index of first key, byte offset, and byte length per block.

import bisect, zlib, struct

def build_blocks(sorted_keys, block_size=128):
    blob, sparse_index = bytearray(), []
    for i in range(0, len(sorted_keys), block_size):
        block_keys = sorted_keys[i:i + block_size]
        raw = b"\x00".join(str(k).encode() for k in block_keys)
        compressed = zlib.compress(raw, level=6)
        offset = len(blob)
        blob.extend(struct.pack(">I", len(compressed)))
        blob.extend(compressed)
        sparse_index.append((block_keys[0], offset, len(compressed) + 4))
    return bytes(blob), sparse_index

def lookup(blob, sparse_index, target):
    first_keys = [e[0] for e in sparse_index]
    pos = bisect.bisect_right(first_keys, target) - 1
    if pos < 0:
        return False
    _, offset, _ = sparse_index[pos]
    (comp_len,) = struct.unpack(">I", blob[offset:offset + 4])
    raw = zlib.decompress(blob[offset + 4:offset + 4 + comp_len])  # only this block
    block_keys = [int(x) for x in raw.split(b"\x00")]
    lo = bisect.bisect_left(block_keys, target)
    return lo < len(block_keys) and block_keys[lo] == target

n = 200_000
sorted_keys = list(range(0, n * 2, 2))
blob, sparse_index = build_blocks(sorted_keys, block_size=128)
print(f"{n:,} keys -> {len(sparse_index):,} blocks, "
      f"sparse index = {len(sparse_index) * 16:,} bytes in memory")
print(f"compressed size {len(blob):,} bytes vs raw ~{sum(len(str(k))+1 for k in sorted_keys):,} bytes")
print("hit  40000 ->", lookup(blob, sparse_index, 40_000))
print("miss 40001 ->", lookup(blob, sparse_index, 40_001))

Output:

200,000 keys -> 1,563 blocks, sparse index = 25,008 bytes in memory
compressed size 349,987 bytes vs raw ~1,344,445 bytes
hit  40000 -> True
miss 40001 -> False

1,563 blocks for 200,000 keys at 128 keys per block, matching 200,000 divided by 128 exactly; the entire sparse index fits in about 25 KB, small enough to keep resident even for a much larger underlying array; the compressed file is about 26 percent of the raw size; and every lookup, hit or miss, decompresses exactly one of the 1,563 blocks, found via roughly 11 comparisons, log base 2 of 1,563 is about 10.6, against the in-memory index, never touching the other 1,562.

Trade-offs and pitfalls

The main tuning knob, block size, is a direct trade and there is no universally correct answer: smaller blocks mean less wasted decompression per lookup and a finer-grained, but bigger, sparse index; bigger blocks mean better compression ratios and a smaller sparse index, at the cost of decompressing more irrelevant data per lookup. The common mistake is picking a block size for compression ratio alone without checking what it does to point-lookup cost, or the reverse, picking a tiny block size for lookup speed and giving up most of the compression benefit the whole design exists to capture alongside fast access. A second pitfall specific to compressed blocks: a block's compressed length is not predictable from its uncompressed length, so the index must store each block's actual byte length and offset explicitly, as this design does, rather than assuming fixed-size blocks the way an uncompressed page-based layout could.

Direct answer

Structure this as a tiny log-structured merge (LSM) store: append(event) only ever writes to a small, size-bounded in-memory buffer, and once that buffer fills it is sorted and written out once as a new immutable, timestamp-sorted segment file on disk, so no on-disk data is ever mutated after it is written. A small in-memory manifest tracks each segment's (min_ts, max_ts) range, so range_query(start_ts, end_ts) can rule out every segment whose range does not overlap the query before opening a single file. Periodic compaction merges the oldest segments together, which bounds both the number of segment files (so the manifest itself stays small and fixed-size) and the number of files any one query has to open.

Approach

Three pieces working together keep the whole design under a fixed memory budget regardless of how much data has been appended:

1. A bounded write buffer. append adds to an in-memory list capped at max_buffer_events. Hitting the cap triggers a flush: the buffer is sorted by timestamp once (cheap, since it is small) and written to a new segment file, then cleared. Memory used by the buffer never grows past that cap.
2. A bounded manifest. Each flush adds one entry to an in-memory list of {id, path, min_ts, max_ts, count}, one entry per segment file on disk. If this list were left to grow forever, both its own memory footprint and the number of files a range query has to check would grow without bound as more data arrives. Compaction caps it: whenever the segment count crosses a threshold, the oldest segments are merged (via a k-way merge of already-sorted files, so no file is ever loaded fully into memory) into one new segment, and the old ones are deleted.
3. Range-query pruning via the manifest, not the files. A query first filters the small in-memory buffer directly (cheap, it is already in memory), then filters the manifest by [min_ts, max_ts] overlap to get a short list of candidate segments, and only opens those files. Because each segment is stored fully sorted by timestamp, scanning one is a straight sequential read with an early exit the moment a record's timestamp exceeds end_ts.

flowchart LR
    E["append(event)"] --> B["In-memory buffer
    bounded to N events"]
    B -->|"buffer full: sort by ts, write once"| S["New segment file
    header: min_ts, max_ts, count"]
    S --> M["Manifest (in memory)
    id, path, min_ts, max_ts, count"]
    M -->|"too many segments"| K["Compaction: k-way merge
    oldest segments into one"]
    K --> S
    Q["range_query(start_ts, end_ts)"] --> B
    Q --> M
    M -->|"prune: keep only overlapping segments"| R["Open only matching
    segment files, sorted scan"]
    R --> RES["Merged, sorted results"]
    B --> RES

Implementation

"""
Disk-backed, time-partitioned event store.

append(event)                       -> event is a (timestamp, payload) pair;
                                        buffers in memory, flushes to a new
                                        immutable, timestamp-sorted segment
                                        file once the buffer fills.
range_query(start_ts, end_ts)       -> merges matches from the live buffer
                                        with matches from only the segment
                                        files whose [min_ts, max_ts] overlaps
                                        the query range (read from a small
                                        in-memory manifest, not the segments).
compact()                           -> merges the oldest segments into one
                                        when the segment count crosses a
                                        threshold, bounding both segment
                                        count (manifest memory) and the
                                        number of files a query must open.

On-disk segment format (each segment file is fully sorted by timestamp,
written once, never mutated after flush):
    [0:8]   min_ts  (uint64 BE)   -- segment footer/header for pruning
    [8:16]  max_ts  (uint64 BE)
    [16:24] count   (uint64 BE)
    then `count` records, each:
        [0:8]  timestamp (uint64 BE)
        [8:12] payload length (uint32 BE)
        [12:12+len] payload bytes
"""
import struct
import os
import heapq

SEG_HEADER = struct.Struct(">QQQ")   # min_ts, max_ts, count
REC_HEADER = struct.Struct(">QI")    # timestamp, payload length


class TimePartitionedStore:
    def __init__(self, directory, max_buffer_events=200, max_segments=6):
        self.directory = directory
        os.makedirs(directory, exist_ok=True)
        self.max_buffer_events = max_buffer_events
        self.max_segments = max_segments
        self.buffer = []          # list[(ts, payload)], unflushed, in memory
        self.manifest = []        # list[dict(id, path, min_ts, max_ts, count)]
        self._next_seg_id = 0
        self.segments_opened_last_query = 0   # instrumentation for the demo

    # ---------- write path ----------

    def append(self, event):
        ts, payload = event               # event is a (timestamp, payload) pair
        self.buffer.append((ts, payload))
        if len(self.buffer) >= self.max_buffer_events:
            self._flush()

    def _flush(self):
        if not self.buffer:
            return
        batch = sorted(self.buffer, key=lambda e: e[0])
        self.buffer = []
        self._write_segment(batch)
        if len(self.manifest) > self.max_segments:
            self.compact()

    def _write_segment(self, sorted_events):
        seg_id = self._next_seg_id
        self._next_seg_id += 1
        path = os.path.join(self.directory, f"seg_{seg_id:06d}.dat")
        min_ts = sorted_events[0][0]
        max_ts = sorted_events[-1][0]
        with open(path, "wb") as f:
            f.write(SEG_HEADER.pack(min_ts, max_ts, len(sorted_events)))
            for ts, payload in sorted_events:
                f.write(REC_HEADER.pack(ts, len(payload)))
                f.write(payload)
        self.manifest.append({
            "id": seg_id, "path": path,
            "min_ts": min_ts, "max_ts": max_ts,
            "count": len(sorted_events),
        })

    # ---------- compaction ----------

    def compact(self, n_oldest=None):
        """Merge the n_oldest segments (oldest = earliest flushed, front of
        the manifest list) into a single new segment via a k-way merge of
        already-sorted inputs. Bounds len(self.manifest), which is the only
        thing scaling with total data volume in this design, so it bounds
        the store's fixed in-memory metadata footprint regardless of how
        much data has been appended."""
        if n_oldest is None:
            n_oldest = len(self.manifest) - self.max_segments // 2
        n_oldest = max(2, min(n_oldest, len(self.manifest)))
        victims = self.manifest[:n_oldest]
        merged = list(self._merge_segments([v["path"] for v in victims]))
        for v in victims:
            os.remove(v["path"])
        self.manifest = self.manifest[n_oldest:]
        if merged:
            # manifest order does not affect correctness: range_query
            # filters every manifest entry by [min_ts, max_ts] overlap
            # regardless of position, and the manifest is small (bounded
            # by max_segments) so that filter is cheap either way.
            self._write_segment(merged)

    @staticmethod
    def _merge_segments(paths):
        """k-way merge: each input file is already sorted, so this reads
        each sequentially once and yields events in global sorted order
        without loading any file fully into memory."""
        def gen(path):
            with open(path, "rb") as f:
                min_ts, max_ts, count = SEG_HEADER.unpack(f.read(SEG_HEADER.size))
                for _ in range(count):
                    ts, length = REC_HEADER.unpack(f.read(REC_HEADER.size))
                    payload = f.read(length)
                    yield (ts, payload)
        iterators = [gen(p) for p in paths]
        # key=lambda e: e[0] means heapq.merge compares only the extracted
        # timestamp, never the (ts, payload) tuples themselves, so payload
        # values are never compared at all and do not need to support
        # ordering; ties are broken by heapq.merge's own stable internal
        # bookkeeping, not by falling back to comparing the payload.
        yield from heapq.merge(*iterators, key=lambda e: e[0])

    # ---------- read path ----------

    def range_query(self, start_ts, end_ts):
        results = [(ts, p) for ts, p in self.buffer if start_ts <= ts <= end_ts]

        candidate_segments = [
            m for m in self.manifest
            if m["max_ts"] >= start_ts and m["min_ts"] <= end_ts
        ]
        self.segments_opened_last_query = len(candidate_segments)

        for m in candidate_segments:
            with open(m["path"], "rb") as f:
                min_ts, max_ts, count = SEG_HEADER.unpack(f.read(SEG_HEADER.size))
                for _ in range(count):
                    ts, length = REC_HEADER.unpack(f.read(REC_HEADER.size))
                    payload = f.read(length)
                    if ts > end_ts:
                        break                 # segment is sorted: nothing further qualifies
                    if ts >= start_ts:
                        results.append((ts, payload))

        results.sort(key=lambda e: e[0])
        return results


if __name__ == "__main__":
    import random
    import shutil

    random.seed(42)
    tmp_dir = "segment-store-demo"
    shutil.rmtree(tmp_dir, ignore_errors=True)

    store = TimePartitionedStore(tmp_dir, max_buffer_events=200, max_segments=6)

    # Generate 10,000 events with a little out-of-order jitter (realistic
    # for events arriving over a network), append them one at a time the
    # way a real ingest loop would.
    N = 10_000
    base_ts = 1_700_000_000_000
    all_events = []
    for i in range(N):
        ts = base_ts + i * 10 + random.randint(-5, 5)   # mild jitter
        payload = f"event-{i}".encode()
        all_events.append((ts, payload))

    for ts, payload in all_events:
        store.append((ts, payload))
    store._flush()  # flush whatever remains in the buffer at the end

    print(f"events appended:      {N}")
    print(f"segments after run:    {len(store.manifest)} "
          f"(bounded by max_segments={store.max_segments}, "
          f"compaction fired whenever it was exceeded)")
    print(f"segment files on disk: {len([f for f in os.listdir(tmp_dir) if f.endswith('.dat')])}")

    # Correctness: run 20 range queries at random windows and compare
    # against a brute-force filter of the original in-memory event list
    # (ground truth, independent of the store's internals).
    mismatches = 0
    total_candidates_checked = 0
    for _ in range(20):
        lo_i = random.randrange(N)
        window = random.randint(1, 2000)
        start_ts = all_events[lo_i][0]
        end_ts = start_ts + window

        got = sorted(store.range_query(start_ts, end_ts))
        want = sorted([(ts, p) for ts, p in all_events if start_ts <= ts <= end_ts])
        if got != want:
            mismatches += 1
        total_candidates_checked += store.segments_opened_last_query

    print(f"range queries checked: 20")
    print(f"mismatches:            {mismatches}")
    print(f"avg segments opened per query: {total_candidates_checked / 20:.1f} "
          f"out of {len(store.manifest)} total segments on disk at query time")

    # Show the pruning explicitly on one narrow, known window.
    probe_ts = all_events[N // 2][0]
    got = store.range_query(probe_ts, probe_ts + 50)
    print(f"narrow probe query opened {store.segments_opened_last_query} of "
          f"{len(store.manifest)} segments and returned {len(got)} events")

    # Edge cases.
    before_all = store.range_query(base_ts - 10_000, base_ts - 1_000)
    print(f"query entirely before all data: {len(before_all)} events, "
          f"opened {store.segments_opened_last_query} segments")

    after_all = store.range_query(all_events[-1][0] + 1_000, all_events[-1][0] + 2_000)
    print(f"query entirely after all data:  {len(after_all)} events, "
          f"opened {store.segments_opened_last_query} segments")

    empty_store = TimePartitionedStore(tmp_dir + "-empty", max_buffer_events=200, max_segments=6)
    print(f"query on a brand-new empty store: {empty_store.range_query(0, 10**15)}")

    unflushed_store = TimePartitionedStore(tmp_dir + "-unflushed", max_buffer_events=200, max_segments=6)
    for ts, payload in all_events[:50]:       # well under max_buffer_events: nothing flushed yet
        unflushed_store.append((ts, payload))
    unflushed_result = unflushed_store.range_query(all_events[0][0], all_events[49][0])
    print(f"query hitting only the unflushed in-memory buffer: "
          f"{len(unflushed_result)} events (expected 50), "
          f"segments opened: {unflushed_store.segments_opened_last_query} (expected 0)")

    shutil.rmtree(tmp_dir, ignore_errors=True)
    shutil.rmtree(tmp_dir + "-empty", ignore_errors=True)
    shutil.rmtree(tmp_dir + "-unflushed", ignore_errors=True)

Output:

events appended:      10000
segments after run:    5 (bounded by max_segments=6, compaction fired whenever it was exceeded)
segment files on disk: 5
range queries checked: 20
mismatches:            0
avg segments opened per query: 1.0 out of 5 total segments on disk at query time
narrow probe query opened 1 of 5 segments and returned 6 events
query entirely before all data: 0 events, opened 0 segments
query entirely after all data:  0 events, opened 0 segments
query on a brand-new empty store: []
query hitting only the unflushed in-memory buffer: 50 events (expected 50), segments opened: 0 (expected 0)

10,000 events were appended one at a time, which triggered 50 flushes (10000 / 200). Compaction kept the on-disk segment count at 5 the entire time (max_segments=6, so it fires the moment a flush would push the count to 7) instead of letting it climb to 50. The 20 randomized range queries all matched a brute-force scan of the original event list exactly, and on average each query opened only 1.0 of the 5 segments on disk, meaning the manifest pruning is doing its job: a query is not scanning the whole store, it is scanning the one segment (sometimes two, at a segment boundary) whose timestamp range actually overlaps the request.

Key points

• Segments are write-once. A flush sorts the buffer and writes it in one pass; nothing on disk is ever opened for modification again, only for reading or, during compaction, for reading followed by deletion of the whole file. This is what makes the design safe to reason about: a segment's [min_ts, max_ts] header, once written, is permanently accurate.
• The manifest, not the segment files, is what a query consults first. range_query filters self.manifest (a handful of small dictionaries) before touching disk at all; opening a segment file only happens for the segments that survive that filter.
• Compaction uses a k-way merge, not a full-file sort. Since every input segment is already internally sorted, heapq.merge produces the combined sorted output by always taking the smallest available head element across all inputs, without ever loading a whole file into memory, the same idea an LSM-tree's leveled compaction uses at a much larger scale.
• The buffer is part of the read path, not just the write path. A record that has not been flushed yet still has to be visible to a query that asks for it, which is why range_query filters self.buffer directly before ever consulting the manifest.

Complexity

Let N be total events appended, B the buffer cap (max_buffer_events), and S the number of segments at query time (bounded by max_segments because of compaction).

• append: amortized O(1); a flush is triggered once every B calls and costs O(B log B) to sort the batch, so the amortized per-event cost is O(log B).
• range_query: O(B) to filter the buffer, plus O(S) to filter the manifest, plus O(matching segments x records per segment) to scan the segments that survive pruning. Because S is bounded by max_segments (6 in the demo) regardless of how large N grows, the manifest-filtering part of every query costs the same no matter how much data the store holds; only the final segment scan scales with how much data actually falls in the query window, which is the expected, necessary cost of returning that data.
• compact: a k-way merge of n_oldest segments with a combined M records costs O(M log n_oldest) using a heap, run only when the segment count crosses the threshold, so its cost is amortized across the flushes that triggered it.
• Memory: O(B) for the buffer plus O(S) for the manifest, both bounded constants independent of N. This is the "fixed memory budget" the question asks for: nothing in this design holds a structure whose size is proportional to total data appended, except the data itself, which lives on disk.

Edge cases

All exercised by the shipped code and output above:

• Query entirely before any data exists: 0 events returned, 0 segments opened (the manifest filter rules out every segment immediately).
• Query entirely after all data: same, 0 events and 0 segments opened.
• Query against a brand-new, completely empty store: returns an empty list rather than erroring, since an empty buffer and an empty manifest both filter to nothing.
• Query that only the unflushed in-memory buffer can answer (fewer than max_buffer_events appended so far): returns all 50 matching events while opening 0 segment files, confirming the buffer is actually consulted, not just the segments.
• A query window that straddles two segments: the narrow probe query above returned 6 events by opening exactly 1 segment in this run, but a query positioned right at a segment boundary can legitimately need to open 2; the pruning filter handles that correctly because it is an overlap check, not an equality check, against each segment's [min_ts, max_ts].

Trade-offs & pitfalls

• The out-of-order jitter in the demo (up to 5 units either side of the nominal timestamp) is realistic and deliberately not zero. If events always arrived in strictly increasing timestamp order, segment ranges would never overlap and pruning would always open exactly one segment. Real network events do not arrive perfectly ordered, so segment ranges will occasionally overlap slightly at their edges, and the design has to be correct under that, not just under the easy strictly-sorted case; this implementation handles it because pruning is a range overlap check, not an assumption of global order across segments.
• Compaction here is a simple oldest-N merge (size-tiered in spirit), not a leveled scheme. It bounds segment count, which is the property this question asks for, but it does not try to minimize total bytes rewritten over the store's lifetime the way a production LSM-tree's leveled compaction does. That is a legitimate follow-on optimization, not a correctness gap: the two compaction families trade write amplification against compaction complexity, and size-tiered is the right starting point for a design exercise.
• A very bursty write pattern can force back-to-back compactions. If max_buffer_events is set too small relative to burst size, the store spends more time compacting than serving reads; sizing the buffer against the actual expected burst rate (the same kind of arithmetic used to size the segment in a comparable durable-queue design) matters in practice, not just picking a round number.
• This design does not persist the manifest itself. On a real crash, the manifest would need to be rebuilt by scanning the segment directory and re-reading each file's header (cheap, since headers are tiny and fixed-size), which this implementation does not include; it is an in-memory-only structure for the scope of this exercise.

Direct answer

A B+ tree (a sorted, disk-page-based index structure most database indexes use, so a lookup only has to read a handful of pages instead of scanning the table), the variant almost every B-tree index in practice actually is: all row-referencing data lives at the leaf level, internal pages hold only keys and child pointers, and leaf pages are linked to their neighbors, lays out on disk as fixed-size pages, and its lookup cost is entirely a function of how many pages must be read: one page read per level from the root down to the leaf holding the key, so cost is height, not row count directly, and height grows only logarithmically as rows grow because each level's fanout, how many child pointers fit on one page, multiplies reach.

Structured elaboration

Cost model: I/O per page

Reading one page costs one I/O regardless of how many keys are on it, so the fewer pages a lookup has to touch, the cheaper it is. For a tree with fanout F, entries per internal page, holding N keys, the height is approximately:

$\text{height} \approx \lceil \log_{F}(N) \rceil$

A point lookup costs one I/O per level, height I/Os in the worst, fully cold, case; a buffer pool (the in-memory page cache most engines keep) typically makes the top few levels effectively free after the first access, since they are small, hot, and reused by every lookup, leaving only the leaf-level read as the usual marginal cost in practice.

Random versus sequential I/O

A single point lookup's root-to-leaf descent is inherently a scatter of essentially random page reads, each level's page could be anywhere on disk relative to the last. A range scan is different once it reaches the leaf level: because leaf pages are linked in sorted-key order, continuing a scan means reading the next leaf page in the chain, which storage engines and prefetchers can often turn into effectively sequential I/O, far cheaper per byte than the same number of random reads, which is the concrete reason B-trees are good at range queries and comparatively expensive per row for scattered point lookups.

How page size, fanout, and clustering affect performance and memory

• Page size versus fanout: a bigger page holds more key/pointer entries, directly raising fanout, which lowers height for a given row count, which lowers worst-case point-lookup I/O count. The cost: a bigger page also means reading and caching more bytes than logically needed for a lookup that only wants one row, and a bigger unit of contention, since concurrent writers touching different rows on the same big page interfere with each other more than they would on a smaller page.
• Memory usage: buffer-pool memory is spent in page-sized units, so a bigger page size means fewer distinct pages fit in a fixed amount of cache memory, trading "each cached page covers more rows" against "fewer total rows are cacheable at all"; the net effect on hit rate depends on how clustered the access pattern actually is.
• Clustering: when the physical row order on disk matches, or nearly matches, the index's key order, a range scan's leaf-to-leaf walk also walks the underlying rows in physical order, turning the whole range scan into sequential I/O end to end. When the index order does not match physical row order, a secondary, non-clustering index, each matching leaf entry can point to a row on a completely different, unrelated page, turning what looked like an efficient range scan on the index into a scattered random-I/O pattern once the actual rows are fetched, unless the index alone, a covering index, one that contains every column the query needs, can answer the query without touching the base table at all.

Worked example

Computed with explicit, stated assumptions: Postgres's own 8 KB default page size, an 8-byte bigint key, an 8-byte child pointer, and a per-entry overhead estimate. Internal-page fanout works out to about 510 entries per page, and a leaf page holding roughly 30-byte entries, key plus row-pointer overhead, fits about 272 rows.

Height as row count grows, this fanout held fixed:

That height of 3 at 3,000,000 rows matches a live check on an actual Postgres 16 instance: a real B-tree index over 3,000,000 rows reported its root at level = 2 via pageinspect's bt_metap, meaning 3 physical levels, root, one internal level, leaf level, exactly what this model predicts. The real root page held only 13 downlink entries rather than the theoretical maximum of about 510, because a root only needs enough entries to address the actual number of second-level pages that exist, not the page's full theoretical capacity; a mostly-empty root page is normal, not a sign of a problem.

Effect of page size, same 3,000,000 rows: at Postgres's default 8 KB, height stays 3; doubling to 16 KB pushes fanout to about 1,022 and still gives height 3, the extra fanout does not buy a shorter tree until row count grows enough to need it. The difference actually shows at much larger scale: at 500,000,000 rows, 4 KB or 8 KB pages need height 4, while 16 KB or 32 KB pages, with roughly double or quadruple the fanout, stay at height 3, one fewer page read per lookup, purely from the larger page size.

Range-scan I/O, sequential leaf reads once positioned, versus what an uncovered index-then-row-fetch pattern costs in random reads: a 10-row range costs about 1 sequential leaf page; a 1,000-row range costs about 4; a 100,000-row range costs about 368, all sequential, against up to one random page read per matching row, 10, 1,000, or 100,000 respectively, if the index is not covering and the engine has to fetch the base row for every match.

Trade-offs and pitfalls

The common mistake is tuning page size purely to minimize height without weighing the memory and contention costs above: a bigger page size that shaves one level off a lookup's worst case can simultaneously halve how many distinct hot pages the buffer pool can hold, which can make cache-hit rate worse for a workload with a wide, non-clustered access pattern even though the levels-to-descend number improved. The second pitfall is assuming an index range scan is automatically sequential I/O: it is only sequential at the leaf level, and only end-to-end sequential, including the base-table rows, if the index is either covering or genuinely clustering; a non-clustering secondary index's range scan can still degrade into scattered random reads at the row-fetch step even though the index itself was read in perfect sorted order.

Direct answer

For (a) high-throughput time-series ingest, an LSM-tree-based engine (a design that buffers writes in memory and merges them into sorted files later, called compaction, rather than updating in place) is the right fit, because the workload is almost pure sequential append with few or no updates to old data, exactly what LSM-trees are built to absorb fast. For (b) low-latency OLTP (online transaction processing: many small, individually latency-sensitive reads and writes) with many small updates, a B-tree-based engine is the right fit, because point lookups and updates need predictable low latency, which is a B-tree's strength and an LSM-tree's weak spot once un-compacted files pile up.

Structured elaboration

Workload (a): time-series ingest, on each engine

• B-tree: every new data point is effectively a new row, and if timestamps are the, or part of the, key, inserts are mostly append-at-the-end, actually one of the better cases for a B-tree (few scattered page splits, since new keys land at the rightmost leaf). The problem is scale of sustained throughput: each insert still writes a page, and near a checkpoint boundary (the periodic point where the engine forces all recent changes out to durable storage) a full-page write-ahead-log image, so raw write throughput is bounded by page I/O, not by CPU or memory bandwidth, and there is no way to make an individual page write cheaper than it is.
• LSM-tree: inserts go to an in-memory buffer, the memtable, and are appended sequentially, with no page-level I/O per write at all; throughput scales with how fast the engine can flush full memtables and keep compaction from falling behind, not with per-row page cost. Indexing is essentially free on the write side, since the memtable is already sorted by key on flush; compaction cost is real but is background work, not inline with the write path, so it does not directly add to per-write latency the way a B-tree page split does.
• Operational consequences: an LSM-tree here trades a bounded, predictable per-write cost (the B-tree case) for a much higher raw write ceiling with a background cost, compaction I/O and potential write stalls if compaction falls behind, that has to be provisioned and monitored separately from the write path itself.

Workload (b): OLTP, many small updates, on each engine

• B-tree: an update finds the row via a direct root-to-leaf descent (2 to 4 I/Os for realistic table sizes) and rewrites it in place; latency is low and, importantly, consistent regardless of how many prior updates that row has had, because there is exactly one place the current value lives.
• LSM-tree: an update is a new version appended to the memtable, cheap on the write side, same as the ingest case, but a subsequent read for that key may have to check the memtable and then multiple on-disk sorted files, newest to oldest, before finding the current version, unless Bloom filters (compact structures that can cheaply rule out a file) and a well-maintained compaction schedule keep that file count low. Under heavy update churn on a small set of hot keys, this can produce read-latency tail spikes a B-tree simply does not have, because a B-tree never has more than one place to look.
• Operational consequences: choosing an LSM-tree here means accepting that read latency is coupled to compaction health in a way it is not with a B-tree; a compaction backlog directly degrades the read path, not just disk usage.

Worked example

Take concrete numbers for each. Workload (a) at 200,000 events per second, each a small append-only row keyed by timestamp: on a B-tree engine, at roughly one page write per insert in the worst case with no batching, sustained throughput is bounded by however many page writes per second the storage device can absorb, commonly a few tens of thousands of small random or semi-sequential writes per second on typical solid-state storage, which 200,000 per second would saturate, and which also burns through the device's write-endurance budget faster than necessary, since solid-state wear is a function of physical writes, not logical ones. Batching many events into one memtable flush, the LSM path, instead turns that into far fewer, larger sequential writes, which the same device handles far above 200,000 logical events per second. Workload (b) at, say, a hot key updated thousands of times per hour, tiny payload: on a B-tree, every update is still one predictable root-to-leaf descent regardless of how many times that key has already been updated; on an LSM-tree, the same hot key can accumulate several un-compacted versions across L0 and shallow levels between compaction passes, so a read for it, right after a burst of updates and before compaction has caught up, checks more files than a read for a cold key would, a real, if usually small, latency asymmetry a B-tree does not have.

Trade-offs and pitfalls

The recommendation above is a default, not a law: a time-series workload that also needs frequent point updates to recent, still-hot data, correcting the last few minutes of a metric stream, for instance, partially loses the LSM-tree's clean advantage, since those updates behave more like workload (b)'s hot-key case within workload (a)'s overall shape; many real time-series systems mitigate this by only allowing appends to a short recent window and treating anything older as immutable, restoring the pure-append pattern LSM-trees are best at. Conversely, an OLTP system that occasionally needs a very high-throughput bulk-load window, an overnight batch import, can get real benefit from LSM-tree-style bulk-load tricks even on an otherwise B-tree-shaped workload, which is why some engines, and some application-level designs, use one structure for steady-state traffic and a different ingestion path for bulk operations.