Range Scans and Tombstones in Bf-Tree

Hello, I'm Maneshwar. I'm building git-lrc, a Micro AI code reviewer that runs on every commit. It is free and source-available on Github. Star git-lrc to help devs discover the project. Do give it a try and share your feedback for improving the project.

Traditional point lookups are where Bf-Tree shines: a mini-page may satisfy reads without touching the underlying leaf page.

But range scans behave differently.

Why Range Scans Still Need Leaf Pages

Suppose we need all keys between 1000 and 2000.

A mini-page only contains recent modifications (insertions, updates, tombstones), not the complete ordered dataset.

To produce an accurate range result, Bf-Tree must:

1. Scan records inside the mini-page
2. Load and scan the corresponding leaf page
3. Merge both views
4. Return a consistent ordered result

This means mini-pages alone cannot eliminate I/O during range scans.

The merge ensures recent writes override stale leaf-page contents.

Growing Mini-Pages Into Full Cached Pages

The paper proposes an optimization for frequently scanned ranges.

Instead of repeatedly loading the leaf page, a hot mini-page can expand until it becomes a full-page cache inside the circular buffer.

At that point Bf-Tree behaves less like record caching and more like traditional page caching.

The benefit is subtle but important:

• Efficient repeated range scans
• Faster negative lookups ("record does not exist")
• Better handling of gaps between keys
• Support for mechanisms such as gap locking

Caching a page means caching both existing records and absence between records.

That absence matters.

Delete Is Just Inserting a Tombstone

Deletion in Bf-Tree does not immediately remove data from the leaf page.

Instead:

DELETE key=42

↓

Insert tombstone into mini-page

Future reads encounter the tombstone and return not found without loading the leaf page.

Later, when the mini-page merges back:

Leaf page + Tombstone
↓

Physical deletion

Deletes become deferred work.

Updates Behave Like Inserts

Updates follow the same idea.

Changing a value:

UPDATE key=42 -> new_value

↓

Write new record into mini-page

Subsequent reads see the updated version directly from memory.

Only during merge does the leaf page become permanently updated.

So in Bf-Tree:

• Insert → append to mini-page
• Update → append newer version to mini-page
• Delete → append tombstone to mini-page

Almost everything becomes "write now, reconcile later."

That design is one reason Bf-Tree reduces random writes while keeping reads fast.