Designing Node Types for B+Tree Implementation in Rust

⚓ Rust    📅 2025-07-03    👤 surdeus    👁️ 20      

surdeus

Warning

This post was published 172 days ago. The information described in this article may have changed.

Hi,

I'm relatively new to Rust (about six months of learning) and I'm trying to implement a B+Tree. I'm having difficulty finding a clean and idiomatic way to design my node types. Since B+Tree implementation is complex and most details are out of scope for this question, I'll first explain what I need to do, then show what I've tried so far and how I would approach it in an object-oriented language like C++, which is my background.

What I Need

I need two types: InternalNode and LeafNode. These types have very similar internal behavior:

  • Both have an ordered list of key/value pairs
  • Both can be searched by key
  • Both support insert and delete operations
  • (I'm omitting other common features to keep this simple)

However, there are also differences between them:

  • Both have fields (with getters/setters) specific to their type
  • Major difference: The types of keys and values differ
    • For LeafNode: both key and value types need to be generic
    • For InternalNode: the key must be generic, but values must be references (maybe Box<...>) to other nodes (either InternalNode or LeafNode)

I think this last requirement is what's causing me difficulties.

What I've Tried

I've thought of/tried many approaches, but nothing seems clean or idiomatic.

My most promising design was to have a NodeBase to implement the common functionality - the generic sorted key/value list:

// This is simplified code, implementations are omitted
struct NodeBase<K, V> {
    cells: Vec<Cell<K, V>>,
}

Then I have a Node enum with two variants for internal and leaf nodes:

type BoxedNode<K, V> = Box<Node<K, V>>;

enum Node<K, V> {
    InternalNode {
        base: NodeBase<K, Box<Node<K, V>>>,
    },
    LeafNode {
        base: NodeBase<K, V>,
    },
}

This seemed promising, but then I can't implement methods specific to InternalNode or LeafNode. In this scenario, I don't really have distinct InternalNode or LeafNode types.

How I Would Do This in a Classic OO Language

In a classic OO language, I would have a Node class that is inherited by LeafNode and InternalNode classes. The InternalNode class would hold some sort of pointer to a Node.

My Question

How can I design a set of types that would simulate or replace an inheritance relationship in a way that is both efficient and idiomatic in Rust?

Thanks for any guidance!

5 posts - 3 participants

Read full topic

🏷️ rust_feed