Starting with a fundamentally wrong design

I started building a B+Tree as part of a database project in Rust, inspired by QuillSQL and CMU’s Bustub. The idea seemed straightforward: build a tree, support insert and search. How hard could it be?

So I wrote my first data structure:

struct Node {
    key: String,
    value: String,
    children: Vec<Node>,
}

One key, one value, a list of children. I looked at it and thought — a node has a key, a value, and children. A tree is made of nodes. Makes sense, right?

Wrong. Fundamentally wrong.

Inner nodes and leaf nodes in a B+Tree serve entirely different purposes. Inner nodes store keys to separate ranges — they don’t hold actual data. Leaf nodes map keys to real data rows. And inner nodes store multiple keys, not just one. Each key points to a child node range.

My one-key-one-value design didn’t even match the basic definition of a B+Tree.

Second attempt: let the struct tell the truth

After realizing the problem, I redesigned:

enum NodeValue {
    Data(String),           // leaf node: actual data
    Pointer(Box<Node>),     // inner node: points to child
}

struct Node {
    keys: Vec<String>,
    values: Vec<NodeValue>,
    next: Option<Box<Node>>, // leaf node linked list
}

Now keys and values are vectors. The value enum distinguishes between data and child pointers. Leaf nodes are linked via next for range scans.

Looked decent. Then I wrote tree.insert("hello") — and Rust’s compiler blew up in my face.

It expected a Value type, not &str. Fixing this dragged me into From/Into traits, the orphan rule, covered and uncovered types. I wrote a separate post just about that rabbit hole. All because I insisted on a single struct for both leaf and inner nodes.

But a much bigger problem was waiting.

The real problem: nodes aren’t toys in memory

This design has one fatal assumption: all nodes live in memory. Inner nodes hold Box<Node> pointers directly to child nodes. That works for a toy implementation, but it’s completely wrong for a real database.

B+Tree nodes are fundamentally database pages. Pages can be in memory or on disk. Which page is where, when to read it in, when to flush it out — that’s the Buffer Pool’s job, not the B+Tree’s.

Inner nodes cannot hold memory pointers to other nodes. They can only hold a page_id.

The entire design needed to be rebuilt.

Third iteration: page-oriented design

Inner nodes point to the page where the child node lives:

struct InnerPage {
    keys: Vec<Key>,
    children: Vec<PageId>,
}

Leaf nodes need to point to the exact location of the data — not just which page, but which slot within that page:

struct RecordId {
    page_id: PageId,
    slot: u16,
}

struct LeafPage {
    keys: Vec<Key>,
    records: Vec<RecordId>,
    next_page_id: Option<PageId>,
}

Every time you need to read an inner or leaf node, you don’t dereference a pointer. You go through the buffer pool:

// fetch a page from the buffer pool
let guard = buffer_pool.fetch_page(page_id)?;

// interpret raw bytes as an inner or leaf page
let inner = InnerPage::from_bytes(guard.data());

// unpin when done
drop(guard); // guard auto-unpins on drop

Pages are a fixed 8192 bytes (PAGE_SIZE). The buffer pool decides whether a page sits in a memory frame or needs to be read from disk. Your B+Tree code doesn’t care — it only deals with page_id.

Where do inner node keys come from?

One question that stuck with me: how are inner node keys determined?

Your instinct might say the B+Tree chooses them itself. In reality, inner node keys come from outside — specifically, from leaf node splits.

When a leaf node overflows and splits, the split process promotes a key up to the parent node. That promoted key becomes the boundary separating the two child node ranges in the inner node.

This clicked for me only after studying QuillSQL’s implementation. QuillSQL’s key type looks like this:

pub struct Tuple {
    pub schema: SchemaRef,
    pub values: Vec<ScalarValue>,
}

Not a simple String — a tuple carrying a schema and Vec<ScalarValue>. Why?

Because database keys can be composite — like (user_id, created_at). You can’t represent a compound index with a single String. Tuple is the general abstraction that works for any index key definition.

My String keys are essentially a placeholder. They’ll break the moment I need composite indexes or type-aware comparisons.

Current state

The B+Tree struct exists. The buffer pool layer underneath works — allocating pages, reading/writing via guards, flushing to disk. The insert function is still empty.

What’s left on the implementation plan:

  1. Binary search: finding key insertion points within nodes
  2. Buffer pool allocation: allocating new pages through the buffer pool, not OS malloc
  3. Split logic: leaf overflow → split → promote key to parent
  4. Locking: page-level locks for concurrent access
  5. Root handling: the root can also be a leaf; tree height increases only when the root itself overflows

Three key lessons

First, your data structure must reflect real responsibilities. Inner nodes and leaf nodes serve different roles. Cramming both semantics into one struct only creates pain. Rust’s type system won’t let you get away with it anyway.

Second, the storage model dictates the design. If nodes are database pages rather than memory objects, pointers become page_ids. This is a decision you need to make before writing the first line of code.

Third, study a reference implementation. Without QuillSQL’s code to learn from, I would have wandered around key design for much longer. A good reference shows not just “how” but “why.”

The B+Tree has been around since the 1970s. But building one from scratch is the only way to truly understand what those database textbooks are saying in their deceptively short paragraphs.

This article draws from the author’s experience implementing a B+Tree in Rust, using QuillSQL as a reference. Follow “梦兽编程” for more Rust systems programming content.