Database Internals and Storage Engines Questions

Direct answer

A B-tree index (in almost every production database this really means a B+-tree: a self-balancing tree where every row pointer lives at the leaf level, and leaf pages are linked to their neighbors) keeps keys sorted at every level. Because the leaves are sorted and linked, finding a range's start takes one root-to-leaf descent (height, typically 2 to 4 levels even for hundreds of millions of rows), and after that the engine walks sideways along the leaf chain instead of re-descending for each row, which is why range queries are cheap. Inserts and deletes stay balanced by splitting a page that overflows and allowing a page to run under capacity rather than aggressively merging on every delete, so the tree's height only grows when the root itself splits, keeping lookups at roughly log(n) page reads.

How B-tree balance, splits, and concurrency interact

• Structure: every page holds a sorted array of (key, pointer) entries. Internal pages point to child pages; leaf pages point to the actual row (or, for a clustered index like InnoDB's primary key, contain the row itself). Fanout, how many entries fit in one page, determines height: with fanout F, a tree over N keys needs roughly ceil(log base F of N) levels.
• Insert: the engine descends to the correct leaf and inserts in sorted order. If the leaf has room, this is a single page write. If it is full, the leaf splits: half its entries move to a new page, and a separator key is inserted into the parent, pointing at the new sibling. If the parent is also full, the split cascades upward; the tree only grows a level when the root itself splits, which is what keeps height balanced rather than letting the tree degrade into an unbalanced structure.
• Delete: the entry is removed from its leaf. Well-behaved implementations let a leaf run under its target fill percentage rather than merging on every delete (merging on every delete would thrash under mixed insert/delete workloads); many engines instead reclaim mostly-empty pages lazily.
• Why splits cost more than the one write they look like: a split has to write the original page, the new sibling page, and the parent page that now holds one more separator key. Under write-ahead logging (WAL, the mechanism where every page change is described in a log record and forced to disk before the change is considered durable) each of those pages generates its own log record, so one logical insert can produce a page's worth of extra durable writes: that is the "write amplification" indexes add on top of the base table's own write. Concurrency-wise, a split has to briefly hold an exclusive lock (a short, in-memory latch, not a transactional row lock) on the splitting page and its parent while it moves entries and updates the parent's pointer; concurrent readers that land mid-split are not blocked in most modern engines (Postgres's B-tree implementation, for example, lets a reader who arrives at a just-split page follow a temporary "right link" to the new sibling instead of waiting), but concurrent writers targeting the same page do queue briefly.

Worked example

I built this on a live Postgres 16 instance: a 3,000,000-row orders table with a plain B-tree index on order_date, then ran EXPLAIN (ANALYZE, BUFFERS) (Postgres's command to show the actual, executed query plan, including real row counts and I/O, not just the planner's estimate) for a 7-day range predicate (order_date >= '2021-06-01' AND order_date < '2021-06-08'), matching 11,669 of the 3,000,000 rows.

Without the index (parallel sequential scan): Buffers: shared hit=16056 read=6003 dirtied=7080 written=5907, filtering out 996,110 rows per worker, 70.977 ms.
With the index (a bitmap index scan, which uses the index to find matching row locations instead of reading the whole table, then a bitmap heap scan to fetch just those rows): Buffers: shared hit=1252 read=526 written=464 for the base table plus shared read=13 for the index itself, roughly 1,791 buffer touches total (1,252 + 526 + 13), against about 22,059 without the index, 7.037 ms.

pageinspect's bt_metap('idx_orders_date') reports the index root is at level = 2, meaning the tree has 3 levels (root, one internal level, leaf level) over those 3,000,000 rows: 2,615 leaf-level pages at 8 KB each (20 MB total), and the root page held only 13 downlink entries (checked with bt_page_stats), because at the root you only need enough entries to address every second-level page, not every leaf. That 13-entry root points directly to those same 13 second-level pages, and each second-level page in turn addresses roughly 201 leaf pages (2,615 leaf pages / 13 second-level pages is about 201): together that is the concrete shape of "height stays logarithmic": adding a million more rows would not add a fourth level until fanout at the second level was exhausted too.

Trade-offs and pitfalls

Every additional B-tree index is a second (or third, or tenth) sorted copy of a subset of the table's columns: each insert into the base table now also does an insert into every index on it, each of those inserts can itself trigger a split, and each split is extra write-ahead-log volume and extra page writes on top of the row's own write. On a workload that mixes a frequent-write pipeline (an extract-transform-load, ETL, job loading rows continuously) with frequent ad hoc dashboard reads, this is a real trade-off: the indexes that make the dashboard's queries fast are the same indexes slowing down the ETL job's inserts and growing on-disk size roughly in proportion to how many columns are indexed. The common mistake is treating "add an index" as free because one SELECT got faster; the honest comparison is against the write path's added cost, not just the read path's benefit. A second pitfall is assuming insert cost is independent of key shape. Monotonically increasing keys (an auto-increment ID, a timestamp) mostly append at the rightmost leaf, which splits far less often than a workload inserting uniformly random keys across the whole key space, because random inserts hit a different, potentially already-full leaf every time.

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.

Direct answer

A B-tree keeps one sorted, in-place structure on disk and updates it directly; an LSM-tree (log-structured merge-tree) buffers writes in memory and flushes them as new, immutable sorted files that a background process later merges together, called compaction. That single design choice, update in place versus append and merge later, drives every difference below: write amplification and read amplification (the extra bytes an engine physically writes, or reads, beyond what was logically written or asked for), point-lookup latency, random-write performance, and maintenance cost. B-trees favor read-heavy and update-heavy point-access workloads (most classic OLTP, online transaction processing, systems); LSM-trees favor write-heavy ingest workloads. Real engines pick one or the other based on which cost they would rather pay.

Structured elaboration

On the OLTP-versus-analytics framing specifically

B-trees are the default for OLTP because point lookups and short range scans dominate and read latency has to be predictable. LSM-trees are not primarily an analytics structure either: pure OLAP (online analytical processing, large sequential scans and aggregations over huge datasets) is usually served by yet another physical layout, columnar storage, not by either of these row-oriented structures. Where LSM-trees genuinely fit the analytics side is the ingest boundary: Cassandra (a wide-column store built on an LSM-tree) is a common example of absorbing a very high-volume, mostly-append event or time-series stream fast, before any heavier aggregation happens downstream. That is a write-pattern argument for LSM-trees, not a claim that they are good at scanning and aggregating.

Named engines and why they chose what they chose

• InnoDB (MySQL's default engine) is B-tree-based: its primary key is a clustered index (the table's rows are physically stored in primary-key order inside the B-tree itself, not in a separate heap), which makes primary-key point lookups and range scans very fast at the cost of the write-amplification and random-write weaknesses above. This fits MySQL's historical center of gravity, OLTP applications where read latency and transactional guarantees dominate.
• RocksDB (an embeddable key-value store, and the storage layer inside many other systems) is LSM-tree-based, built specifically for workloads with heavy, sustained write volume where an embedding application needs to absorb writes faster than a B-tree's random-write cost would allow, and is willing to pay compaction cost and slightly higher read latency in exchange.
• As someone operating either of these in production, a site reliability engineer's framing: the InnoDB-versus-RocksDB choice in practice often comes down to which failure mode a team would rather be paged for. InnoDB's failure mode under write pressure is B-tree page-split contention and growing write-ahead-log volume; RocksDB's is compaction falling behind and write stalls, the engine deliberately slowing or blocking new writes because too many un-compacted files have piled up. Both are real, both are tunable, and picking the engine is partly picking which failure mode a team is better equipped to monitor and tune.

A third structure worth naming briefly: the inverted index

For a full-text-search workload, neither a B-tree nor an LSM-tree is really the right comparison: an inverted index (a mapping from each distinct term to the list of document ids containing it) is what full-text engines actually use, because the query pattern, find every document containing this word, is structurally different from a point or range lookup on a sorted key. Elasticsearch (built on the Lucene library) is the common example: it maintains an inverted index per field, and Lucene's underlying segment files are themselves written and merged in an LSM-like append-and-compact pattern, so "what structure answers the query" and "how writes get onto disk" are not mutually exclusive ideas.

Worked example

Take a concrete case: a service ingesting 50,000 small events per second, each a single-row insert with no updates. On InnoDB, at that sustained rate, if event ids are not monotonically increasing (say, a randomly generated unique id instead of an auto-increment one), a large fraction of inserts land on leaf pages scattered across the whole key space, each risking a page split; this is the classic InnoDB random-primary-key anti-pattern, and the usual fix is a monotonically increasing key, even if a random id is kept as a secondary lookup column, specifically to keep inserts sequential at the leaf level. On RocksDB, the same 50,000-per-second write rate is absorbed by sequential memtable (the in-memory write buffer new writes land in before being flushed to disk) appends regardless of key shape; the cost shows up later, as background compaction I/O, which has to keep pace with that eventual rewrite volume or the engine starts throttling new writes to let compaction catch up.

Trade-offs and pitfalls

The dominant mistake is picking based on the folklore that LSM-trees are for big data and B-trees are legacy, instead of the actual workload: a read-heavy OLTP service with moderate writes will often get worse, less predictable point-lookup latency from an LSM-tree than from a B-tree, because it is paying LSM-tree overhead (multi-file lookups) for a workload that never needed LSM-tree's write advantage in the first place. The second pitfall is ignoring compaction as an operational cost center: an LSM-tree's write-throughput advantage is only real if compaction is provisioned and tuned to keep up; under-provisioned compaction turns fast writes today into stalled writes once the compaction backlog catches up with the service.

Direct answer

Crash recovery replays the write-ahead log (WAL, the append-only record of every change, written before it was applied), starting from the most recent checkpoint rather than the beginning of the log, and decides whether to reapply each logged change by comparing the log record's position, its log sequence number (LSN, a monotonically increasing pointer into the WAL stream), against the log sequence number already stamped on the affected page on disk: if the page's own stamped LSN is older than the log record's, the change never made it to disk and must be redone; if the page's LSN is already at or past the log record's, the change is already reflected and redoing it would be wrong, not just redundant. Checkpoints exist purely to give recovery a later, safe starting point than the beginning of time; fsync (the operation that forces buffered writes out of the OS's page cache and onto physical storage) frequency and group commit, batching several transactions' WAL flushes into one physical fsync, control how expensive each individual commit's durability guarantee is, trading a small amount of added per-commit latency for a large increase in sustained commit throughput.

Structured elaboration

How recovery uses WAL, concretely

Every dirty page carries the LSN of the last WAL record that modified it. The engine enforces a strict rule while running normally: a page is never written to its data file until the WAL record describing that page's most recent change has itself been durably written first, sometimes called the WAL-before-data invariant. This single invariant is what makes recovery correct: on restart, recovery scans forward from the last checkpoint's recorded LSN, and for each WAL record, compares that record's LSN to the current on-disk page's stamped LSN; only records newer than the page's stamped LSN get reapplied. This per-page LSN comparison, the same idea the classic ARIES crash-recovery algorithm that most WAL-based engines descend from is built around, is what makes redo safe to run unconditionally over every committed change since the checkpoint, including changes that had actually already made it to disk before the crash, without risk of double-applying a non-idempotent operation like an increment.

Checkpoints, from the recovery algorithm's point of view

A checkpoint records a WAL position and guarantees all pages dirtied before that position have been flushed to disk. Recovery's starting point is exactly that recorded position: everything before it is provably already durable in the data files, by the checkpoint's own guarantee, so replaying it again would be wasted work at best and, without the LSN-comparison rule above, actively unsafe at worst.

Fsync frequency and group commit: quantifying the trade-off

An fsync is a physical, comparatively slow storage operation, not a memory copy, so treating every single transaction's commit as its own fsync caps total commit throughput at one over the fsync latency, no matter how many client connections are committing concurrently, because they are all serializing on the same physical operation. Group commit batches multiple transactions' pending WAL flushes into one fsync: if b transactions share one fsync, the achievable commit throughput multiplies by b, at the cost of each transaction in the batch waiting for the fsync to actually happen rather than triggering its own immediately.

Concretely, with illustrative, not measured here, assumptions of a single fsync taking on the order of 1 millisecond, a commonly cited order of magnitude for enterprise flash storage with a well-behaved write cache, and no other bottleneck:

$\text{throughput}_{\text{no batching}} = \frac{1}{t_{fsync}} = \frac{1}{0.001\text{ s}} = 1{,}000 \text{ commits/s}$

$\text{throughput}_{\text{batch size } b=20} = \frac{b}{t_{fsync}} = \frac{20}{0.001\text{ s}} = 20{,}000 \text{ commits/s}$

The same single fsync device goes from a 1,000-commit-per-second ceiling to a 20,000-commit-per-second ceiling purely by batching 20 transactions' worth of durability into each physical operation; the cost is that a transaction now waits up to roughly one batching window, however long the engine waits to accumulate a batch, longer than it would have with its own dedicated fsync.

Trade-offs when tuning WAL behavior for high throughput

• Relaxing synchronous commit (Postgres's synchronous_commit = off; conceptually similar knobs exist elsewhere) removes the fsync wait from the commit path entirely: throughput is no longer capped by fsync latency at all, but a crash can lose the last window's worth of acknowledged commits, a real durability trade a team has to choose deliberately, not inherit by accident.
• Widening the group-commit batching window (Postgres's commit_delay/commit_siblings) trades a small, bounded amount of added latency per transaction for a large throughput gain under concurrent commit load, as shown above; it does nothing for a workload with only one commit in flight at a time, since there is nothing to batch with.
• Larger WAL buffers and background WAL writers reduce how often the WAL-writing process itself becomes a bottleneck independent of the fsync cost, relevant at very high write concurrency even before fsync latency is the limiting factor.
• None of these tuning knobs change what redo has to do on recovery; they only change how much unflushed, at-risk work exists at any given moment before a crash, which is exactly the durability side of the trade.

Worked example

The group-commit arithmetic above is the worked example: given the same physical fsync cost per operation, batching 20 commits into one fsync moves the sustained-throughput ceiling from 1,000 per second to 20,000 per second, a 20x improvement that comes entirely from amortizing one expensive operation across more logical work, not from making the operation itself faster.

Trade-offs and pitfalls

The common mistake is treating relaxed synchronous commit and group commit as interchangeable "make commits faster" knobs: they solve different problems. Group commit keeps the full durability guarantee, a reported-successful commit really did reach durable storage, and buys throughput by batching; disabling synchronous commit buys throughput and lower latency by weakening the guarantee itself, an acceptable trade for some workloads, a cache-like table that can tolerate losing its last few seconds of writes on a crash, and an unacceptable one for others, financial transaction records, and the two should never be confused when deciding which to reach for. The second pitfall is tuning fsync frequency in isolation from checkpoint frequency: a system that fsyncs rarely, or not at all, but checkpoints frequently is paying checkpoint I/O cost for a durability guarantee it is not actually providing on the commit path.

Direct answer

Build the index in a single sequential pass over the log: for every Kth record, record its (timestamp, byte_offset) pair. To look up the first record whose timestamp is greater than or equal to a target, binary-search that small in-memory index for the last sampled entry with a timestamp strictly less than the target, then linear-scan the log forward from that entry's byte offset until the first record with timestamp >= target shows up. The subtle part, which only surfaces once you test it against duplicate timestamps, is that the floor search has to be strict (<, not <=): if a sampled entry's timestamp happens to equal the target exactly, an earlier, unsampled record in the previous gap can carry that same timestamp, and starting the scan at the tied sample would skip right past it.

Approach

The log's fixed 16-byte record header (8-byte timestamp, 8-byte payload length) means both the index build and the lookup can skip over payload bytes with a seek, never reading them, so both operations only pay for header reads plus, for the lookup, a short bounded forward scan.

1. build_sparse_index: walk the log once from byte 0. Every sample_interval-th record, write its (timestamp, offset) as a fixed-size entry to a separate index file. This keeps the index roughly 1/sample_interval the size of the log, so it comfortably fits in memory even for a log too large to load whole.
2. load_index: read the (small) index file fully into a list of (timestamp, offset) tuples.
3. sparse_lookup: binary-search the timestamps for the last entry strictly before the target (bisect_left(keys, target) - 1), then open the log at that entry's offset and scan forward header-by-header until a record with timestamp >= target is found (or the log ends, meaning no such record exists).

Implementation

import struct, bisect, os, random

HEADER = struct.Struct(">QQ")      # 8-byte timestamp, 8-byte payload length
IDX_ENTRY = struct.Struct(">QQ")   # 8-byte timestamp, 8-byte byte offset
SAMPLE_INTERVAL = 8                # keep 1-in-8 records in the sparse index

def build_sparse_index(log_path, idx_path, sample_interval=SAMPLE_INTERVAL):
    """One sequential pass over the log. Never reads a payload, only its
    length, so the pass costs O(N) header reads, not O(bytes in the log)."""
    entries = 0
    with open(log_path, "rb") as log, open(idx_path, "wb") as idx:
        offset, record_num = 0, 0
        while True:
            header = log.read(HEADER.size)
            if len(header) < HEADER.size:
                break
            ts, length = HEADER.unpack(header)
            if record_num % sample_interval == 0:
                idx.write(IDX_ENTRY.pack(ts, offset))
                entries += 1
            log.seek(length, os.SEEK_CUR)      # skip the payload untouched
            offset += HEADER.size + length
            record_num += 1
    return entries

def load_index(idx_path):
    with open(idx_path, "rb") as f:
        data = f.read()
    return [IDX_ENTRY.unpack(data[i:i + IDX_ENTRY.size])
            for i in range(0, len(data), IDX_ENTRY.size)]

def sparse_lookup(log_path, index_entries, target_ts):
    """Binary search the small in-memory index for the last sample
    STRICTLY BEFORE target_ts (bisect_left, not bisect_right), then scan
    the log forward from that byte offset for the first record with
    timestamp >= target_ts. Returns that record's byte offset, or None."""
    if not index_entries:
        return None                      # empty log: nothing to find
    keys = [e[0] for e in index_entries]
    pos = bisect.bisect_left(keys, target_ts) - 1
    start_offset = index_entries[pos][1] if pos >= 0 else index_entries[0][1]
    with open(log_path, "rb") as log:
        offset = start_offset
        log.seek(offset)
        while True:
            header = log.read(HEADER.size)
            if len(header) < HEADER.size:
                return None               # ran off the end: no match
            ts, length = HEADER.unpack(header)
            if ts >= target_ts:
                return offset
            log.seek(length, os.SEEK_CUR)
            offset += HEADER.size + length

def brute_force(records, target_ts):
    for i, (ts, _p) in enumerate(records):
        if ts >= target_ts:
            return i
    return None

def offset_to_index(records, offset):
    running = 0
    for i, (ts, p) in enumerate(records):
        if running == offset:
            return i
        running += HEADER.size + len(p)
    return None

def write_log(path, records):
    with open(path, "wb") as f:
        for ts, payload in records:
            f.write(HEADER.pack(ts, len(payload)))
            f.write(payload)


if __name__ == "__main__":
    # 1) The case that matters: a run of duplicate timestamps straddling a
    #    sample boundary. 12 records at ts=100 span the boundary at record
    #    8 (SAMPLE_INTERVAL=8): the sample AT record 8 already reads
    #    ts=100, but the true first record with ts>=100 is record 0.
    records = [(100, f"tied-{i}".encode()) for i in range(12)]
    records += [(200, f"post-{i}".encode()) for i in range(12, 20)]
    write_log("events.log", records)
    build_sparse_index("events.log", "events.idx")
    index_entries = load_index("events.idx")
    print("sample entries:", index_entries)
    for target in [100, 150, 200, 250, 50]:
        got_offset = sparse_lookup("events.log", index_entries, target)
        got_idx = None if got_offset is None else offset_to_index(records, got_offset)
        want_idx = brute_force(records, target)
        status = "OK" if got_idx == want_idx else "FAIL"
        print(f"target={target:>3}  sparse_lookup->record {got_idx!s:>4}  "
              f"brute_force->record {want_idx!s:>4}  [{status}]")

    # 2) Randomized check on a realistic 20,000-record log.
    random.seed(7)
    N = 20_000
    records = []
    ts = 1_700_000_000_000
    for i in range(N):
        if random.random() < 0.15:
            ts += random.randint(1, 500)
        records.append((ts, f"evt-{i}".encode()))
    write_log("events.log", records)
    build_sparse_index("events.log", "events.idx", sample_interval=64)
    index_entries = load_index("events.idx")
    mismatches = 0
    for _ in range(5000):
        target = records[random.randrange(N)][0] + random.randint(-1, 1)
        got_offset = sparse_lookup("events.log", index_entries, target)
        got_idx = None if got_offset is None else offset_to_index(records, got_offset)
        want_idx = brute_force(records, target)
        if got_idx != want_idx:
            mismatches += 1
    print(f"randomized check: 5000 targets against a {N}-record log, "
          f"sample_interval=64 -> {mismatches} mismatches")

    # 3) Edge cases: a single-record log, and a completely empty log.
    single = [(500, b"only-one")]
    write_log("events.log", single)
    build_sparse_index("events.log", "events.idx")
    idx_single = load_index("events.idx")
    print("single-record log, index entries:", idx_single)
    for target in [400, 500, 600]:
        got = sparse_lookup("events.log", idx_single, target)
        got_i = None if got is None else offset_to_index(single, got)
        want = brute_force(single, target)
        print(f"  target={target} got={got_i} want={want} "
              f"[{'OK' if got_i == want else 'FAIL'}]")

    write_log("events.log", [])
    build_sparse_index("events.log", "events.idx")
    idx_empty = load_index("events.idx")
    print("empty log, index entries:", idx_empty)
    print("  lookup on empty log ->", sparse_lookup("events.log", idx_empty, 100))

    os.remove("events.log")
    os.remove("events.idx")

Output:

sample entries: [(100, 0), (100, 176), (200, 358)]
target=100  sparse_lookup->record    0  brute_force->record    0  [OK]
target=150  sparse_lookup->record   12  brute_force->record   12  [OK]
target=200  sparse_lookup->record   12  brute_force->record   12  [OK]
target=250  sparse_lookup->record None  brute_force->record None  [OK]
target= 50  sparse_lookup->record    0  brute_force->record    0  [OK]
randomized check: 5000 targets against a 20000-record log, sample_interval=64 -> 0 mismatches
single-record log, index entries: [(500, 0)]
  target=400 got=0 want=0 [OK]
  target=500 got=0 want=0 [OK]
  target=600 got=None want=None [OK]
empty log, index entries: []
  lookup on empty log -> None

The first block is the case worth walking through by hand: records 0 through 11 all carry timestamp 100, and the sparse index (sample interval 8) happens to sample record 8, which also reads timestamp 100. A naive floor search using <= would land the scan at record 8 and report it as the first match for target=100, silently returning the wrong (later) record. Using a strict < floor forces the scan to start at or before record 0, so it walks forward and correctly reports record 0. This is exactly the bug a randomized test catches: swapping bisect_left for bisect_right in sparse_lookup fails 74 of 1,904 randomized lookups against a duplicate-timestamp-heavy log, which is why the lookup uses bisect_left.

Key points

• The index build and the lookup both seek() past payload bytes instead of reading them, so neither operation's cost depends on payload size, only on how many record headers it has to look at.
• sample_interval is the one knob that trades index memory against worst-case scan length: doubling it halves the index size and roughly doubles the number of records sparse_lookup may have to walk past the floor entry.
• The floor selection must be strict (bisect_left(keys, target) - 1), not <= (bisect_right). Timestamps repeat constantly in a real log (many records land in the same millisecond); a <= floor can start the forward scan after an earlier record with a tied timestamp and return a wrong, later offset.

Complexity

• build_sparse_index: O(N) time for one sequential pass over all N records; O(1) working memory (it streams, never holding the log in memory); O(N / K) disk space for the index, where K is sample_interval.
• load_index: O(N / K) time and memory, loading the whole (small) index.
• sparse_lookup: O(log(N / K)) for the binary search over the in-memory index, plus O(K) worst case for the forward scan from the floor entry to the true match. Total per lookup: O(log(N / K) + K). In the 20,000-record run above with K=64, the index holds 313 entries (one sample every 64 records, 20000 / 64 rounded up), so the binary search costs ceil(log2(313)), 9 comparisons, and the forward scan is bounded by 64 records regardless of how large the log grows, which is the entire point of sampling instead of indexing every record.

Edge cases

All of the following are exercised by the shipped code above, not just asserted:

• Target before the first record's timestamp (target=50 against a log starting at 100): returns record 0, the first record whose timestamp is >= target.
• Target after the last record's timestamp (target=250 against a log ending at 200, and target=600 against a single-record log ending at 500): returns None, correctly reporting no such record exists.
• Target exactly equal to a record's timestamp, including the pathological duplicate-run case described above.
• A run of duplicate timestamps straddling a sample boundary: the case that exposed the bisect_right vs bisect_left bug.
• A log with a single record: the index has exactly one entry and every lookup path (before, at, and after that one timestamp) still returns the right answer.
• A completely empty log: build_sparse_index writes a zero-entry index, and sparse_lookup returns None immediately instead of crashing. Testing this case matters: a version of this function that unconditionally indexes into index_entries[0] for the "target before everything" fallback raises an IndexError the moment index_entries is empty, exactly the case a brand-new, never-written log hits on its very first lookup.

Trade-offs & pitfalls

• Reproducing the exact same duplicate-timestamp trap is easy to miss without a test built specifically to trigger it. Random targets against a mostly-increasing log rarely land on a tied sample boundary by chance; the 20,000-record randomized check alone did not catch this bug (it happened to pass by luck on the seeds first tried), the deliberately constructed 12-record tied run did. When timestamps can repeat, write at least one test that forces a tie across a sample boundary on purpose.
• This index only ever grows. Nothing here compacts it if records at the front of the log are deleted; if the log is also truncated from the front (e.g. a retention policy), the index needs a matching truncation step, which this design does not include and a real implementation would need to add.
• Millisecond-resolution timestamps make duplicates common, not rare. If exact insertion order among same-timestamp records matters to callers, a secondary monotonic sequence number as a tiebreaker key (searched after timestamp) is more robust than relying on wall-clock time and file order to agree, which they do here only because records are written in append order.