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

A transactional storage engine prototype with ACID guarantees (atomicity, consistency, isolation, durability: the four properties a transaction is supposed to provide) needs five cooperating pieces: an in-memory buffer pool holding cached pages, a write-ahead log (WAL) for durability and crash recovery, a concurrency-control mechanism, locking or multi-version concurrency control (MVCC), that keeps concurrent transactions from corrupting each other's view of the data, a background checkpoint (periodically flushing recent changes to durable storage and marking how far crash recovery would need to replay from) and compaction process (merging accumulated on-disk files together so read cost does not grow unbounded) that bounds how much log has to be replayed after a crash, and a crash-recovery routine that rebuilds correct state from the WAL plus whatever made it to durable pages before the crash. The core design decision that shapes everything else is page-oriented in-place storage with a B-tree (favoring predictable read latency, higher per-write cost) versus log-structured storage with an LSM-tree (favoring high write throughput, higher and more variable read cost); this prototype describes the architecture in page and B-tree terms, since it generalizes cleanly to either.

Structured elaboration

graph TD
  C[Client transaction] --> BUF[Buffer pool: cached pages]
  C --> WAL[WAL: append change record + fsync at commit]
  WAL --> BUF
  BUF --> PAGES[Data pages / SSTables on disk]
  CK[Checkpoint process] -->|flushes dirty pages| PAGES
  CK -->|advances redo start point| WAL
  CC[Concurrency control: 2PL or MVCC] --> C
  CRASH[Crash recovery] -->|replay from last checkpoint| WAL
  CRASH -->|reconstruct| PAGES

Core data structures

• Pages: fixed-size units (commonly 4 to 16 KB) holding either index entries (a B-tree's internal and leaf pages) or row data; the unit of I/O and of the buffer pool's caching.
• Buffer pool: an in-memory hash table of page id to cached page, with a dirty flag per page (has this page been modified since it was last written to disk) and an eviction policy (commonly a variant of least-recently-used) to decide what to evict under memory pressure.
• WAL: an append-only log of transaction id, page or key change, and before/after or redo/undo information, plus commit and abort markers.
• Index and data files: a B-tree, or, in the LSM variant, a memtable (in-memory write buffer) plus immutable sorted files merged by compaction.

Transaction logging (WAL)

Every change is written to the WAL and fsynced (forced out of the OS's write buffer and confirmed durably on disk, not just handed to the kernel) before the transaction is allowed to report success: the in-memory page can be modified immediately, but the durability guarantee comes entirely from the log record having reached disk, not from the page write, which can happen later.

Concurrency control: locking versus MVCC

• Two-phase locking (2PL: every transaction acquires all the locks it needs before releasing any of them, guaranteeing serializability but making readers and writers block each other) is simpler to reason about and gives strong isolation directly, at the cost of read and write contention: a long-running writer blocks readers of the same rows, and vice versa.
• MVCC (multi-version concurrency control: each transaction sees a consistent snapshot of committed data as of when it started, while writers create new versions rather than overwriting in place) lets ordinary readers and writers proceed without blocking each other, at the cost of needing a mechanism to garbage-collect old versions and, depending on the isolation level chosen (the rule governing how much of other transactions' concurrent changes a transaction is allowed to see), still needing some locking or conflict detection to prevent write-write conflicts and anomalies like write skew (two transactions each reading a valid individual snapshot but together violating an invariant neither would have permitted alone).
• This prototype's default: MVCC for reads, non-blocking, since read-heavy contention is the common case, combined with row-level or key-range locking specifically for write-write conflicts, the same hybrid most production engines actually use rather than a pure implementation of either extreme.

Checkpointing and background compaction

A checkpoint periodically forces all dirty pages up to some WAL position out to disk and records that position; crash recovery then only needs to replay WAL from the most recent checkpoint forward, not from the beginning of the log, which is what bounds recovery time. In the LSM variant, this same role is partly played by memtable flushing, turning in-memory writes into an immutable file, after which the WAL for those writes can be discarded, plus background compaction merging files together to keep read cost from growing unbounded as more files accumulate.

Crash recovery algorithm

A standard three-phase approach: (1) analysis, scan forward from the last checkpoint to determine which transactions were in progress and which pages were dirty at crash time; (2) redo, replay every logged change from the checkpoint forward, regardless of whether its transaction eventually committed, to bring the data files back to exactly the state they were in at the moment of the crash; (3) undo, roll back the changes made by any transaction still in progress, never committed, at crash time, using the before-image or inverse-operation information the WAL recorded for exactly this purpose. Redoing everything first and undoing incomplete transactions second, rather than trying to skip redoing transactions that look uncommitted, is deliberate: it is simpler and more robust, because it does not require correctly identifying every in-flight transaction before touching any data, only after reconstructing the full crash-time state.

Worked example

Trace a single transaction through this design: begin; update a row, modifying the cached page in the buffer pool and appending a WAL record describing the change, not yet fsynced; commit, which fsyncs the WAL up through this transaction's commit record and only then reports success to the client; the modified page in the buffer pool stays dirty and gets written to disk later, either because it is evicted under memory pressure or because the next checkpoint flushes it. If the process crashes one second after that commit, before the page itself was ever written to disk: on restart, recovery's redo phase replays the WAL record for this transaction's change, since its commit record is present, and reconstructs the modified page in memory correctly, even though the on-disk page file never physically received the write, exactly the property that a WAL record is what is durable and the page write is a lazy optimization on top of it.

Trade-offs and pitfalls

Durability, latency, and throughput pull against each other at almost every decision point here: fsyncing every commit's WAL individually gives the strongest per-transaction durability guarantee but the worst latency and throughput under concurrent load, unless group commit, batching multiple transactions' WAL flushes into one fsync, is implemented; choosing 2PL over MVCC gives simpler correctness reasoning but worse concurrency for read-heavy workloads; a short checkpoint interval bounds recovery time tightly but adds continuous background I/O competing with foreground traffic. The common design mistake is picking each of these independently, tightest possible durability, most concurrent possible reads, shortest possible checkpoint interval, without recognizing they compound: a system tuned that way pays every latency and I/O cost simultaneously instead of choosing where it can actually afford to spend budget for the workload it is built for.

Direct answer

For a write-heavy, mixed workload on an LSM-based store (a design that buffers writes in memory and later merges, or compacts, them into larger sorted files in the background), the real decision is between leveled compaction and size-tiered compaction, and it is a straight trade: leveled compaction keeps read amplification and space amplification low (the extra bytes read, or extra disk space held, beyond the logical minimum) by maintaining at most one sorted run per level, at the cost of high write amplification (extra bytes physically written to disk beyond what the application logically wrote) from repeated merging; size-tiered compaction keeps write amplification low by merging whole batches of similarly sized files together instead of merging into a much larger target, at the cost of higher read and space amplification because multiple un-merged sorted runs can coexist within one tier. For most services, anything where point-lookup latency matters to a user, leveled compaction is the safer default; size-tiered earns its keep specifically when the workload is dominated by writes and reads are rare, batch, or can tolerate checking more files.

Structured elaboration

Leveled compaction

Each level (L0, L1, L2, and so on) has a target size, typically each level roughly T times bigger than the one above it (T, the level size ratio, commonly 10). When a level exceeds its target, its data is merged with the overlapping key range in the next level down, producing one sorted run in the target level. Because each level holds at most one sorted run (L0 is the practical exception, since memtable flushes land there before the first real merge), a point lookup checks at most one file per level: read amplification and space amplification stay bounded and low. The cost is write amplification: RocksDB's own compaction documentation states this plainly, "the usual write amplification of leveled compaction... is often larger than 10," and there is a first-principles reason why: compacting level i into level i+1 has to rewrite roughly the overlapping portion of level i+1, which is about T times bigger than what came in from level i, so each level a piece of data passes through costs roughly another T times rewrite.

Size-tiered compaction

Instead of merging into a much bigger target, size-tiered compaction waits until it has several, commonly T, similarly sized files at one tier, merges them together into one new file at the next tier, and repeats. Each byte gets rewritten roughly once per tier it passes through, not T times, so write amplification scales with the number of tiers, not with the size ratio between tiers. The cost shows up on the read side: before enough files accumulate to trigger a merge, a tier can hold up to T-1 un-merged sorted runs, and a point lookup that does not hit a Bloom filter (a compact structure that can cheaply rule a file out) has to check all of them.

A first-principles worked derivation, not a citation, an explicit model

Assume a level size ratio T = 10 and L = 6 levels beyond the memtable (L0 through L5).

$WA_{leveled} \approx T \times L = 10 \times 6 = 60$

That is consistent, in order of magnitude, with RocksDB's own documented figure of "often larger than 10" for leveled compaction. Size-tiered, same T and L, each of the 6 tiers contributing roughly one rewrite instead of T:

$WA_{tiered} \approx L = 6$

an order of magnitude lower than leveled's 60 under the same assumptions, at the cost of up to T - 1 = 9 un-merged runs per tier a lookup might have to check before a merge clears them.

Throttling under peak load

Compaction has to run continuously to keep read and space amplification bounded, but it competes with foreground reads and writes for the same disk and CPU budget. The standard mechanisms: rate-limit compaction I/O explicitly (a byte-per-second cap on compaction reads and writes, separate from foreground I/O); prioritize compacting the levels closest to overflowing (an L0 about to accumulate too many files is a bigger risk than a deep level slightly behind schedule) over a strict oldest-first order; and, as a last resort, deliberately slow or stall new writes when the backlog, number of un-compacted L0 files or pending compaction bytes, crosses a hard threshold, because letting writes keep outpacing compaction indefinitely turns a temporary backlog into unbounded read amplification and eventually unbounded disk usage.

SSD endurance and two levels of mitigation

High write amplification is not just a throughput (the volume of reads and writes a disk can service per second) problem: on solid-state storage it directly consumes the device's rated write-endurance budget, since flash wears out per physical write and erase cycle, not per logical write, so a store running LSM compaction at 40 to 60 times write amplification is burning through an SSD's endurance rating tens of times faster than its logical write volume alone would suggest. There are two independent levers to pull, and confusing them is a common mistake: algorithm-level mitigations change how much gets rewritten in the first place (choosing size-tiered over leveled compaction, widening the level size ratio to reduce level count, using Bloom filters so reads do not force extra compaction just to keep lookups fast); operational-level mitigations change how much endurance headroom absorbs the amplification that is still there (over-provisioning the SSD, keeping meaningfully more raw flash capacity than the logical data size so the drive's own wear-leveling has more room to spread writes, and scheduling heavy compaction windows away from peak traffic rather than running it continuously at full rate). A team under endurance pressure should reach for the algorithm-level fix first, since it reduces the underlying cost, and treat over-provisioning as a buffer, not a substitute.

What to monitor, and how to verify a fix does not quietly cost you something else

Pending compaction bytes or un-compacted file count per level (the leading indicator: this climbing means compaction is losing the race against incoming writes, before it becomes a user-visible problem); actual write-stall time or write-stall event count (the trailing indicator: compaction already lost badly enough to throttle foreground writes); and per-level read amplification, files checked per point lookup, because compaction falling behind at any level directly degrades read latency for keys landing there. When verifying a compaction-tuning change, alter one parameter at a time, for example only the level size ratio, and watch both write amplification and per-level read amplification on the same before-and-after window, not just the metric you were trying to improve. A fix that halves write amplification by doubling the level size ratio can simultaneously double how many un-compacted files pile up before a merge clears them, invisible if only the write side was monitored.

Worked example

The numeric derivation above, T=10, L=6 giving leveled about 60x and size-tiered about 6x write amplification under identical assumptions, is the worked example: it shows the two strategies' relative costs come from the same two inputs, size ratio and level count, and it reproduces, in order of magnitude, the "often larger than 10" figure RocksDB's own documentation reports for real leveled-compaction deployments.

Trade-offs and pitfalls

The pitfall in picking a compaction strategy is optimizing for the write path in isolation: a service that switches to size-tiered compaction purely to cut write amplification, without checking whether its read latency budget can absorb checking several un-merged files per lookup, trades a capacity problem (disk wear, I/O budget) for a latency problem (unpredictable point-lookup tail latency) that may be worse for the actual product. The second pitfall is treating a write stall as a bug to eliminate rather than a safety valve: removing or disabling it without first fixing whatever is causing compaction to fall behind just moves the failure from temporarily slower writes to read amplification and disk usage growing without bound until the disk fills or reads time out, a strictly worse outcome.

Direct answer

A B-tree index mutates data in place: it walks a balanced, sorted tree structure straight to the on-disk page holding a key and updates that page directly, so writes are scattered, random-access page updates. An LSM-tree (Log-Structured Merge-tree) index never mutates data in place: writes go into an in-memory sorted buffer first, then get flushed as new, immutable sorted files that a background process periodically merges. PostgreSQL's default index type is the B-tree; RocksDB is built entirely around an LSM-tree. For a high-ingest logging service, the LSM-tree is the right default, because the workload is almost pure appends and write throughput is the thing under pressure, not point-lookup latency.

Structured elaboration

How each one actually writes a record

B-tree write path: the engine traverses the tree from the root to find the one leaf page where a key belongs, loads that page into the buffer pool if it is not already resident, and mutates it directly (in place). The change becomes durable once the write-ahead log (WAL, the append-only file a database writes an intent-to-change record to before touching the real data) for that change is flushed; the actual data page itself is written back to disk later, in its own time. Every logical write touches one specific, essentially random location in the index file.

LSM-tree write path: the engine appends the change to an in-memory sorted structure (the memtable, commonly a skip list), plus its own WAL entry for durability, and returns. Nothing on disk changes yet. When the memtable fills, its entire contents are written out, unchanged, as one new immutable sorted file (an SSTable, short for "sorted string table"). Later, a background process called compaction merges multiple SSTables together, both to bound how many files a read has to check and to physically drop keys that were since overwritten or deleted.

Why that difference matters for a high-ingest workload

The recommendation, and what would flip it

For the stated workload (a high-ingest logging service), choose an LSM-tree-backed engine. Log lines are almost never updated after being written, the dominant operation is "append a new record," and the write path never has to do a random page mutation for that, only a sequential append to memory and, eventually, to a new file. A B-tree engine can certainly ingest logs too, but every insert is still a random-access page write under the hood, which is the more expensive pattern for this specific access shape.

This recommendation would flip if the service also needed frequent point lookups or short range scans on recent data under a tight p99 (99th percentile) latency target as a first-class requirement, not just occasional ad hoc queries, because a B-tree's read path is more uniformly fast and does not depend on compaction having kept up. It would also flip if log records needed frequent in-place correction after being written, which is unusual for logs but common for, say, a mutable event status field bolted onto the same table.

Worked example

At 50,000 log lines/sec averaging 300 bytes each, the ingest rate is 50,000 x 300 = 15,000,000 bytes/sec, about 15 MB/s. On the LSM-tree path, that is 15 MB/s of purely sequential writes (memtable, then flush), the pattern disks and SSDs are best at. On the B-tree path, if each insert dirties one index page independent of the others (a reasonable worst case when new rows do not cluster on the same page), that is roughly 50,000 random page writes/sec of demand placed on the storage layer, before accounting for any write-back batching the buffer pool manages to do. The B-tree engine is not incapable of this, modern SSDs and a well-tuned buffer pool absorb a lot of it, but the LSM-tree design converts the same logical write rate into the I/O pattern (sequential) that is cheapest to sustain, which is exactly why it is the standard choice for logging and telemetry systems (RocksDB itself began as a store for exactly this kind of write-heavy workload).

Trade-offs & pitfalls

• "LSM is faster" is only true for writes. A point read on an LSM-tree can be more expensive than on a B-tree, especially for older data buried under several compaction levels; a logging service that also needs fast recent-data dashboards should plan for that, typically by keeping a well-tuned Bloom filter and bounding how many SSTable levels a hot read has to check.
• Compaction is not free background maintenance, it is a second write of the same data. Under sustained heavy ingest, compaction can fall behind, which shows up as growing read latency (more files to check) and, if it falls far enough behind, as write stalls the engine imposes on purpose to let compaction catch up.
• B-tree engines are not one-size-fails-all for logging. If update volume is modest and the team already runs PostgreSQL everywhere, a B-tree-backed table with good partitioning can still work; the LSM-tree recommendation is about the shape of this specific workload, not a blanket rule.
• Several real engines are not purely one or the other. MySQL's InnoDB is B-tree based. WiredTiger, the storage engine MongoDB uses, has an LSM-tree table type in addition to its default B-tree tables, though that LSM mode is legacy and effectively unmaintained, so production MongoDB deployments run on WiredTiger's B-tree path in practice. Naming "PostgreSQL versus RocksDB" is a clean illustration of the two families, not a claim that every engine falls cleanly into one bucket.

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.