How Bf-Tree Executes Reads and Writes Using Mini-Pages

Hello, I'm Maneshwar. I'm working on FreeDevTools online currently building **one place for all dev tools, cheat codes, and TLDRs* — a free, open-source hub where developers can quickly find and use tools without any hassle of searching all over the internet.*

Yesterday, we looked at how mini-pages, a specialized buffer pool, and a circular memory layout reshape the storage layer of a B-Tree.

Today, we move one level up.

Once mini-pages exist and memory is under control, the real question becomes:

How does Bf-Tree actually execute reads, writes, and scans using these pieces?

This post walks through the core operations of Bf-Tree—get, insert, range scans, and updates—and shows how mini-pages change the execution path of each operation.

Core Operations in Bf-Tree

At a high level, Bf-Tree splits responsibility cleanly:

• Inner nodes: pinned, pointer-based, fast traversal
• Mini-pages: in-memory working set for hot records
• Leaf pages: stable, on-disk base structure

Every operation starts with a traversal, but what happens after that is where Bf-Tree diverges from traditional designs.

Get: Read Optimized for the Common Case

A get operation begins by traversing the tree to locate:

• The leaf page
• Its corresponding mini-page (if one exists)

def get(key):
    (mini_page, leaf_page) = traverse(key)

    if mini_page:
        result = mini_page.binary_search(key)
        if result:
            # early terminate if found
            return result

    # otherwise, read from the leaf page
    result = leaf_page.binary_search(key)
    if rand() < 0.01:
        # with a small probability, cache it in the mini-page
        mini_page.insert_or_create(result)

    return result

Fast path: mini-page hit

If a mini-page exists, Bf-Tree first performs a binary search in the mini-page:

• If the record is found → return immediately
• No disk IO
• No page-level locks

This is the common case for hot records.

Slow path: leaf page lookup

If the record is not in the mini-page (or no mini-page exists):

1. The leaf page is loaded from disk
2. A binary search is performed on the leaf page
3. With a small probability (default ~1%), the record is cached into the mini-page

That probabilistic caching is deliberate:
it avoids polluting memory with cold records while still letting frequently accessed keys migrate into memory over time.

Key takeaway

Reads are optimized for early termination:
most hot reads never touch disk, and cold reads don’t automatically bloat memory.

Insert: Absorbing Writes in Memory

Insert follows the same initial traversal, but its behavior is more nuanced.

def insert(key, value):
    (mini_page, _leaf_page) = traverse(key)

    ok = mini_page.insert(key, value)
    if ok:
        # early terminate if insert succeeds
        return

    new_size = mini_page.next_size()
    if new_size == 0:
        # need to merge to the base page
        mini_page.merge()
        mini_page.insert(key, value)
        return
    else:
        # need to grow the mini-page
        mini_page.resize(new_size)
        mini_page.insert(key, value)
        return

Step 1: Insert into the mini-page

• If no mini-page exists, one is created
• The mini-page is sized just large enough to hold the new record
• This minimizes write amplification

If the insert fits:

• The operation terminates early
• No disk IO
• No leaf-page modification

Step 2: Mini-page growth

If the mini-page is full:

• Bf-Tree attempts to resize it
• A new memory chunk is allocated
• Contents are copied over
• The insert is retried

This growth happens incrementally, not eagerly.

Step 3: Merge to leaf page

If the mini-page has already grown large enough (e.g., page-sized):

• It is merged into the leaf page
• Dirty and cold records are flushed to disk
• The insert then proceeds again

Key takeaway

Most inserts never touch disk.
Writes are absorbed, batched, and reshaped before hitting the leaf page.

Range Scan: When Mini-Pages Aren’t Enough

Range scans are different.

A range scan must examine:

• Records in the mini-page
• Records in the leaf page
• Then merge the two views

This means disk IO is unavoidable.

Turning a weakness into a feature

Bf-Tree handles this by allowing a mini-page to:

• Grow to full page size
• Cache the entire leaf page inside the circular buffer

At that point, the buffer pool behaves as a page-level cache, not just a record cache.

This enables:

• Efficient repeated range scans
• Negative lookups
• Gap handling and locking
• Fewer disk reads for analytical workloads

Key insight

Mini-pages aren’t limited to record-level caching.
They dynamically adapt into page-level caches when access patterns demand it.

Delete and Update: Just Writes in Disguise

Deletes and updates reuse the same machinery.

Delete

• A delete inserts a tombstone into the mini-page
• Reads encountering the tombstone immediately return “not found”
• The leaf page is untouched

When the mini-page is eventually merged:

• The record is physically removed from the leaf page

Update

• An update simply inserts the new version into the mini-page
• Reads see the updated value immediately
• Disk is updated only during merge

Key takeaway

Deletes and updates are logical operations first, physical operations later.
This keeps hot paths fast and disk writes controlled.

Why This Execution Model Matters

Across all operations, the pattern is consistent:

• Early termination whenever possible
• Memory-first execution
• Disk writes delayed and batched
• Adaptation based on access patterns

Mini-pages are not just a cache.
They are an execution layer that reshapes how a B-Tree behaves under real workloads.

Combined with yesterday’s buffer pool design, Bf-Tree achieves:

• High read throughput
• Write absorption without lock contention
• Efficient range scans when needed
• Predictable eviction and memory usage

Where This Fits in the Bigger Picture

At this point, the separation is complete:

• Inner nodes → traversal
• Mini-pages → working set + write buffer
• Leaf pages → stable base state

Each layer is optimized for its own access pattern.

That separation and the discipline to keep it intact is what allows Bf-Tree to scale without collapsing under contention.

👉 Check out: FreeDevTools

Any feedback or contributors are welcome!

It’s online, open-source, and ready for anyone to use.

⭐ Star it on GitHub: freedevtools