Page journals: replay committed index changes

Operational case

A committed page change rewrites P-19 as rebalanced and introduces P-26 as a new leaf. A later proposed split for P-52 has no commit record, representing an interrupted operation. Replay returns only P-19 and P-26 from the committed group. It does not manufacture P-52. The order of records is part of the structure: a page record without its begin or a commit without its begin raises. In a real storage engine, log durability must precede publishing dirty index pages, and recovery policy must account for any uncommitted changes that reached disk. This small replay model assumes they did not.

Working Python program

class PageRedoJournal:
    def __init__(self, checkpoint_pages):
        self.checkpoint_pages = dict(checkpoint_pages)
        self.records = []
        self.next_transaction = 47

    def record(self, page_changes, commit=True):
        transaction = self.next_transaction
        self.next_transaction += 1
        self.records.append(("begin", transaction))
        for page_id, contents in page_changes.items():
            self.records.append(("page", transaction, page_id, contents))
        if commit:
            self.records.append(("commit", transaction))
        return transaction

    def recover(self):
        pages = dict(self.checkpoint_pages)
        pending = {}
        for record in self.records:
            action, transaction, *details = record
            if action == "begin":
                pending[transaction] = {}
            elif action == "page":
                if transaction not in pending:
                    raise ValueError("page record without begin")
                page_id, contents = details
                pending[transaction][page_id] = contents
            elif action == "commit":
                if transaction not in pending:
                    raise ValueError("commit record without begin")
                pages.update(pending.pop(transaction))
            else:
                raise ValueError("unknown journal record")
        return pages


journal = PageRedoJournal({"P-19": "original"})
journal.record({"P-19": "rebalanced", "P-26": "new leaf"})
journal.record({"P-52": "unfinished split"}, commit=False)
print(journal.recover())

Output

{'P-19': 'rebalanced', 'P-26': 'new leaf'}

Time, space, and tradeoff

For R journal records and P checkpoint pages, replay scans O(R) records and copies O(P) pages; applying page updates costs O(U) for U committed update records, already bounded by R. The in-memory journal and pending transaction maps use O(R) additional space in the worst case, while the recovered page map uses O(P + U) entries. A production implementation needs durable write ordering, checksums or equivalent record validation, truncation or checkpointing, concurrency control, and an undo or no-steal policy consistent with its page-flush rules. This example establishes a replay invariant, not a database durability guarantee.

Common Mistakes

• Do not apply an uncommitted page record during redo-only recovery.
• Do not flush uncommitted data pages and assume this model can undo them.
• Do not claim a Python list models durable ordered writes or torn-record detection.
• Do not reuse transaction IDs in one untrimmed journal without a generation rule.

Connected lessons

• Trees and Heaps
• Data Structures
• B+ deletion: borrow, merge, and repair separators
• B+ trees: propagate leaf splits through multiple levels
• Index snapshots: publish related maps as one in-memory version
• Projects
• Quizzes

Apply this contract in the reversible depot release project, then check the operations quiz.

Framed journals: detect a torn tail before replay examines the next boundary.