Build a B-Tree and B+ Tree Index Engine

Build a B-tree and B+ tree from scratch in C# to learn how database indexes work.

Introduction

30 Second Summary

Every time you search for a product on a shopping site or look up a transaction in your bank app, the database behind the scenes is using a tree-shaped index to find your data in milliseconds instead of scanning millions of rows.

In this project, you will build two complete tree-based index engines from scratch in C#: a classic B-tree and a B+ tree. You will insert records, watch nodes split in real time, and run range queries to discover why every major database chose B+ trees.

What You'll Build

A C# console application containing two generic tree implementations that demonstrate how database indexes organize data for fast lookups and sequential scans.

By the end of this project, you'll have:

  • A working B-tree with insert, search, and in-order traversal that demonstrates node splitting and key promotion.
  • A working B+ tree with linked leaf nodes that supports efficient range queries.
  • A tree printer utility that visualizes the tree structure in the console so you can watch splits happen as keys are inserted.
  • Secret Mission: Add deletion with borrowing and merging to the B-tree implementation.

Are there any prerequisites?

You should be comfortable with C# generics and have a basic understanding of binary search trees. No prior knowledge of B-trees or database internals is needed.

Before We Start

Before We Start...

Set Up the Project

Before you can build two tree-based index engines, you need a C# project with the right file structure.

In this step, you will create a .NET 9 console application and add the class files that will eventually hold each component of your B-tree and B+ tree implementations.

In this step, get ready to:
  • Create a new Console App project in Visual Studio targeting .NET 9.
  • Add class files for each tree component.
  • Verify the project compiles with zero errors.
Create the Console App project

A .NET Console App is a command-line program that writes output to the terminal. This is the right project type because your B-tree engine will print tree structures to the console so you can watch splits happen in real time.

  • In Visual Studio, click File in the top menu bar.
  • Click New, then Project.
  • In the search box at the top, type Console App.
  • Select the Console App template tagged with C# (not the one marked Visual Basic or F#).
  • Click Next.
  • In the Project name field, enter BTreeIndexEngine.
  • Choose a location on your Desktop for the project, then click Next.
  • In the Framework dropdown, select .NET 9.0.
  • Leave Do not use top-level statements unchecked.
  • Click Create.

Visual Studio generates two files: BTreeIndexEngine.csproj (the project configuration) and Program.cs (with a default Hello World line).

What are top-level statements?

Top-level statements let you write C# code directly in Program.cs without wrapping it in a class and Main method. The compiler generates the boilerplate for you behind the scenes.

This keeps the entry point clean so you can focus on calling your tree classes directly.

Don't see .NET 9.0 in the dropdown?

Make sure you have the .NET 9 SDK installed. You can verify by opening a terminal and running dotnet --version. If you see a version starting with 9., the SDK is installed.

If not, download the SDK from the official .NET downloads page and restart Visual Studio after installing.

Why can't Visual Studio find .NET 9?

Add the class files

Your project needs separate files for each tree component. Splitting code into focused files makes each piece easier to reason about as you build up complexity.

  • In the Solution Explorer panel on the right, right-click the BTreeIndexEngine project.
  • Click Add, then Class....
  • Name the file BTreeNode.cs and click Add.
  • Repeat the same process to add four more files: BTree.cs, BPlusTreeNode.cs, BPlusTree.cs, and TreePrinter.cs.

Visual Studio auto-generates a class stub in each new file. You need to clean these up so only the namespace remains.

  • Open each of the five new files (BTreeNode.cs, BTree.cs, BPlusTreeNode.cs, BPlusTree.cs, TreePrinter.cs) and replace their contents with just the namespace declaration:
namespace BTreeIndexEngine;

Why clear the class stubs?

You will write each class from scratch in the following steps. Keeping the auto-generated stubs would create conflicts when you add your own generic class definitions later.

  • Open Program.cs and delete the default Console.WriteLine("Hello, World!"); line so the file is completely empty.
  • Save all files by pressing Ctrl+Shift+S.

Your Solution Explorer should now show 7 files: BTreeIndexEngine.csproj, Program.cs, BTreeNode.cs, BTree.cs, BPlusTreeNode.cs, BPlusTree.cs, and TreePrinter.cs.

Don't see all the files?

Make sure you added each file to the project (right-click the project name, not the solution). Files added at the solution level will not be part of the build.

Check that the file names match exactly, including capitalisation. C# is case-sensitive for namespaces and file references.

Help me find my missing class files in Visual Studio.

Build the project to verify your setup
  • Build the project by pressing Ctrl+Shift+B.

Check the Output panel at the bottom of Visual Studio. You should see a message ending with Build succeeded and 0 errors.

Seeing build errors?

If any file still has auto-generated class content, it may conflict with the empty namespace declaration. Open each file and confirm only namespace BTreeIndexEngine; remains (except Program.cs which should be completely empty).

Help me fix build errors in my BTreeIndexEngine project.

✔️ Awesome, I've got everything!

Great. Make sure you have saved all files before moving on.

ⓧ I'd like to double check the full code

Here is what each file should look like at the end of this step.

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net9.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>

</Project>
// Program.cs is intentionally empty - code will be added in a later step
namespace BTreeIndexEngine;
namespace BTreeIndexEngine;
namespace BTreeIndexEngine;
namespace BTreeIndexEngine;
namespace BTreeIndexEngine;

Your project skeleton is ready. Next up, you will build the B-tree node structure and implement insertion with node splitting.

Build the B-Tree Node and Insert with Splitting

Your project skeleton is ready and compiling cleanly. Now it is time to build the core data structure that powers database indexes.

A B-tree keeps data sorted across multiple levels of nodes, where each node can hold several keys. When a node gets too full, it splits in half and promotes its middle key upward. This splitting mechanism is what keeps the tree balanced without ever needing a full reorganization.

In this step, get ready to:
  • Create the B-tree node class that holds keys, values, and child pointers.
  • Implement insertion with automatic node splitting when nodes overflow.
  • Add a search method that navigates the tree to find any key.
Create the B-tree node class

Every B-tree is built from nodes. Each node stores a sorted list of keys, their associated values, and pointers to child nodes. A leaf node has no children. An internal node uses its children to route searches downward.

  • Open BTreeNode.cs in the editor.
  • Replace the file's contents with this code:
namespace BTreeIndexEngine;

public class BTreeNode<TKey, TValue> where TKey : IComparable<TKey>
{
    // Sorted list of keys stored in this node
    public List<TKey> Keys { get; set; }

    // Values corresponding to each key
    public List<TValue> Values { get; set; }

    // Child node pointers (empty for leaf nodes)
    public List<BTreeNode<TKey, TValue>> Children { get; set; }

    // True if this node has no children
    public bool IsLeaf { get; set; }

    public BTreeNode(bool isLeaf)
    {
        Keys = new List<TKey>();
        Values = new List<TValue>();
        Children = new List<BTreeNode<TKey, TValue>>();
        IsLeaf = isLeaf;
    }
}

What does this code do?

This class is generic, constrained by where TKey : IComparable<TKey>. That constraint ensures keys can be compared and sorted, which is essential for a search tree.

  • Keys holds the sorted key values within this node.
  • Values holds the data associated with each key (one value per key).
  • Children holds pointers to child nodes. A node with N keys has N+1 children.
  • IsLeaf distinguishes leaf nodes (which store data but have no children) from internal routing nodes.
  • Save BTreeNode.cs.
  • Build the project by pressing Ctrl+Shift+B. You should see Build succeeded in the Output window with 0 errors.

Seeing a build error?

  • Check that the namespace line reads namespace BTreeIndexEngine; with a semicolon (file-scoped namespace syntax).
  • Make sure the generic constraint says where TKey : IComparable<TKey> not IComparable<T>.
  • help me fix a build error in BTreeNode.cs

✔️ Awesome, I've got everything!

Great. Make sure you have saved BTreeNode.cs before moving on.

ⓧ I'd like to double check the full code

namespace BTreeIndexEngine;

public class BTreeNode<TKey, TValue> where TKey : IComparable<TKey>
{
    public List<TKey> Keys { get; set; }
    public List<TValue> Values { get; set; }
    public List<BTreeNode<TKey, TValue>> Children { get; set; }
    public bool IsLeaf { get; set; }

    public BTreeNode(bool isLeaf)
    {
        Keys = new List<TKey>();
        Values = new List<TValue>();
        Children = new List<BTreeNode<TKey, TValue>>();
        IsLeaf = isLeaf;
    }
}
Implement insertion with node splitting

The B-tree's defining behavior is how it handles overflow. When you insert a key into a node that is already full (holding 2t - 1 keys, where t is the tree's minimum degree), the node splits. The median key gets promoted to the parent, creating two smaller child nodes.

  • Open BTree.cs in the editor.
  • Replace the file's contents with the following code:
namespace BTreeIndexEngine;

public class BTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    // Public accessors for tree printing later
    public BTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    // Public insert: handles empty tree and root splits
    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            _root = new BTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        // If root is full, split it before inserting
        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    // Recursively find the correct leaf and insert the key
    private void InsertNonFull(BTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        int i = node.Keys.Count - 1;

        if (node.IsLeaf)
        {
            // Find the position to insert in sorted order
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            // Find the child that should receive this key
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            // Split the child if it is full before descending
            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }

    // Split a full child node into two halves, promoting the median key
    private void SplitChild(BTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BTreeNode<TKey, TValue>(fullChild.IsLeaf);

        // Move keys and values after median to new child
        for (int j = mid + 1; j < fullChild.Keys.Count; j++)
        {
            newChild.Keys.Add(fullChild.Keys[j]);
            newChild.Values.Add(fullChild.Values[j]);
        }

        // Move children after median to new child (if internal node)
        if (!fullChild.IsLeaf)
        {
            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));
        }

        // Promote median key to parent
        TKey medianKey = fullChild.Keys[mid];
        TValue medianValue = fullChild.Values[mid];

        // Remove keys/values from mid onward in full child
        fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
        fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

        // Insert median into parent
        parent.Keys.Insert(childIndex, medianKey);
        parent.Values.Insert(childIndex, medianValue);
        parent.Children.Insert(childIndex + 1, newChild);
    }
}

What does this code do?

The BTree class manages the entire tree through three cooperating methods:

  • Insert is the public entry point. It creates the root on first insert, and if the root is already full (2t - 1 keys), it splits the root before proceeding.
  • InsertNonFull recursively descends toward the correct leaf. At each level, if the target child is full, it splits that child first. This guarantees the leaf always has room.
  • SplitChild takes a full node, finds its median key, moves everything after the median into a new sibling node, and promotes the median up to the parent. This is the operation that grows the tree taller.

Why split before descending?

The algorithm splits full nodes on the way down, not on the way back up. This means you never need to backtrack after inserting. Each node you visit is guaranteed to have room for a promoted key from a child split.

  • Save BTree.cs.
  • Build the project (Ctrl+Shift+B). You should see Build succeeded with 0 errors.

Build failing with missing method errors?

  • Confirm that all three methods (Insert, InsertNonFull, SplitChild) are inside the class braces. A misplaced closing brace will cause errors.
  • Check that BTreeNode.cs is saved. The BTree class references BTreeNode throughout.
  • help me fix build errors in my BTree.cs file
Add the search method

Insertion is only useful if you can retrieve data afterwards. The search algorithm starts at the root and at each node compares the target key against the node's keys to decide which child to descend into.

  • In BTree.cs, find the closing brace of the SplitChild method.
  • Add the following two methods below it, inside the class:
    // Public search: returns the value for a key, or default if not found
    public TValue? Search(TKey key)
    {
        return SearchNode(_root, key);
    }

    // Recursively navigate the tree comparing keys at each level
    private TValue? SearchNode(BTreeNode<TKey, TValue>? node, TKey key)
    {
        if (node == null)
            return default;

        int i = 0;
        // Walk through keys until we find one >= target
        while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) > 0)
            i++;

        // Check if we found an exact match
        if (i < node.Keys.Count && key.CompareTo(node.Keys[i]) == 0)
            return node.Values[i];

        // If leaf, key does not exist in tree
        if (node.IsLeaf)
            return default;

        // Descend into the appropriate child
        return SearchNode(node.Children[i], key);
    }

What does this code do?

  • SearchNode walks through the current node's keys using CompareTo. If the key matches, it returns the value immediately.
  • If the key is not in this node and the node is a leaf, the key does not exist in the tree.
  • If the node is internal, the method descends into the child at position i. Position i is the gap between keys where the target would fall in sorted order.
  • Save BTree.cs.
  • Build the project (Ctrl+Shift+B). You should see Build succeeded with 0 errors and 0 warnings.

Seeing a duplicate definition error?

  • Make sure you added the Search and SearchNode methods inside the existing class braces, not after them. The closing } of the class should come after SearchNode.
  • Check that you have only one namespace BTreeIndexEngine; line at the top of the file.
  • help me fix a duplicate definition error in BTree.cs

✔️ Awesome, I've got everything!

Great. Double check you have saved BTree.cs with both the insertion and search methods in place.

ⓧ I'd like to double check the full code

namespace BTreeIndexEngine;

public class BTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    public BTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            _root = new BTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    private void InsertNonFull(BTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        int i = node.Keys.Count - 1;

        if (node.IsLeaf)
        {
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }

    private void SplitChild(BTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BTreeNode<TKey, TValue>(fullChild.IsLeaf);

        for (int j = mid + 1; j < fullChild.Keys.Count; j++)
        {
            newChild.Keys.Add(fullChild.Keys[j]);
            newChild.Values.Add(fullChild.Values[j]);
        }

        if (!fullChild.IsLeaf)
        {
            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));
        }

        TKey medianKey = fullChild.Keys[mid];
        TValue medianValue = fullChild.Values[mid];

        fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
        fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

        parent.Keys.Insert(childIndex, medianKey);
        parent.Values.Insert(childIndex, medianValue);
        parent.Children.Insert(childIndex + 1, newChild);
    }

    public TValue? Search(TKey key)
    {
        return SearchNode(_root, key);
    }

    private TValue? SearchNode(BTreeNode<TKey, TValue>? node, TKey key)
    {
        if (node == null)
            return default;

        int i = 0;
        while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) > 0)
            i++;

        if (i < node.Keys.Count && key.CompareTo(node.Keys[i]) == 0)
            return node.Values[i];

        if (node.IsLeaf)
            return default;

        return SearchNode(node.Children[i], key);
    }
}

Your B-tree can now insert keys and find them again. Next up, you will add a tree printer so you can actually watch the splits happen in real time as keys flow in.

Visualize the B-Tree and Observe Splits

Your B-tree can now insert keys and split full nodes. But all of that happens invisibly inside memory.

In this step, you will build a tree printer that shows you the structure level by level. You will watch nodes fill up, split, and promote median keys to the parent in real time.

In this step, get ready to:
  • Implement a tree printer that shows nodes at each tree level.
  • Write a demo that inserts keys one at a time and prints the tree after each insertion.
  • Add in-order traversal to confirm keys stay sorted.
Implement the tree printer

A BFS (breadth-first search) traversal visits the tree level by level, left to right. This is perfect for printing because it mirrors how you read the tree visually: root first, then its children, then their children.

  • Open TreePrinter.cs in Visual Studio and replace any existing content with the following code:
namespace BTreeIndexEngine;

public static class TreePrinter
{
    public static void PrintBTree<TKey, TValue>(BTreeNode<TKey, TValue>? root) where TKey : IComparable<TKey>
    {
        if (root == null)
        {
            Console.WriteLine("(empty tree)");
            return;
        }

        // Use a queue for level-order (BFS) traversal
        var queue = new Queue<(BTreeNode<TKey, TValue> Node, int Level)>();
        queue.Enqueue((root, 0));
        int currentLevel = -1;

        while (queue.Count > 0)
        {
            var (node, level) = queue.Dequeue();

            // Start a new line when we move to a deeper level
            if (level != currentLevel)
            {
                if (currentLevel >= 0) Console.WriteLine();
                Console.Write($"Level {level}: ");
                currentLevel = level;
            }
            else
            {
                Console.Write("  ");
            }

            // Print the node's keys in bracket notation
            Console.Write("[" + string.Join("|", node.Keys) + "]");

            // Enqueue children for the next level
            if (!node.IsLeaf)
            {
                foreach (var child in node.Children)
                    queue.Enqueue((child, level + 1));
            }
        }
        Console.WriteLine();
        Console.WriteLine();
    }
}

What does this code do?

The method uses a queue to visit nodes level by level. Each node is paired with its depth so the printer knows when to start a new output line.

  • Queue<(Node, Level)> tracks which node to print next and what depth it sits at.
  • When level changes, the printer moves to a new output line prefixed with the level number.
  • string.Join("|", node.Keys) formats keys like [5|10|17] so you can see exactly what each node holds.
  • Save TreePrinter.cs.

Seeing a compile error?

  • Check that the namespace is BTreeIndexEngine and matches the other files exactly.
  • Ensure the class is static and the method is public static. A non-static class would require instantiation.

Help me fix a compile error in TreePrinter.cs

✔️ Awesome, I've got everything!

Great. Make sure you have saved TreePrinter.cs before moving on.

ⓧ I'd like to double check the full code

namespace BTreeIndexEngine;

public static class TreePrinter
{
    public static void PrintBTree<TKey, TValue>(BTreeNode<TKey, TValue>? root) where TKey : IComparable<TKey>
    {
        if (root == null)
        {
            Console.WriteLine("(empty tree)");
            return;
        }

        var queue = new Queue<(BTreeNode<TKey, TValue> Node, int Level)>();
        queue.Enqueue((root, 0));
        int currentLevel = -1;

        while (queue.Count > 0)
        {
            var (node, level) = queue.Dequeue();

            if (level != currentLevel)
            {
                if (currentLevel >= 0) Console.WriteLine();
                Console.Write($"Level {level}: ");
                currentLevel = level;
            }
            else
            {
                Console.Write("  ");
            }

            Console.Write("[" + string.Join("|", node.Keys) + "]");

            if (!node.IsLeaf)
            {
                foreach (var child in node.Children)
                    queue.Enqueue((child, level + 1));
            }
        }
        Console.WriteLine();
        Console.WriteLine();
    }
}
Write the demo loop and observe splits

With degree t=3, each node can hold at most 2t-1 = 5 keys. After the 5th insertion fills the root, the 6th key triggers a split. The median key gets promoted to a new root node.

  • Open Program.cs and replace any existing content with the following demo code:
using BTreeIndexEngine;

Console.WriteLine("=== B-Tree and B+ Tree Index Engine ===");
Console.WriteLine();

int degree = 3; // Minimum degree t=3, max keys per node = 2t-1 = 5
var keys = new[] { 10, 20, 5, 6, 12, 30, 7, 17, 3, 8 };

// --- B-Tree Demo ---
Console.WriteLine("--- B-Tree (degree 3) ---");
Console.WriteLine("Data stored at EVERY level (internal + leaf nodes)");
Console.WriteLine();

var btree = new BTree<int, string>(degree);

// Insert each key and print the tree to visualize growth
foreach (var key in keys)
{
    btree.Insert(key, $"Record-{key}");
    Console.WriteLine($"Inserted {key}:");
    TreePrinter.PrintBTree(btree.Root);
}

// Test the Search method
Console.WriteLine("Search for key 12: " + (btree.Search(12) ?? "NOT FOUND"));
Console.WriteLine("Search for key 99: " + (btree.Search(99) ?? "NOT FOUND"));
Console.WriteLine();

What does this code do?

  • degree = 3 means each node holds between 2 and 5 keys. This makes splits frequent enough to observe with only 10 insertions.
  • The foreach loop inserts one key at a time and prints the entire tree structure after each insertion. You will see nodes grow, then split when they hit 5 keys.
  • The two Search calls confirm that existing keys return their value and missing keys return NOT FOUND.
  • Save Program.cs.
  • Run the program by pressing Ctrl+F5 (Start Without Debugging) in Visual Studio.

You should see the tree printed after each insertion. The first 5 keys fit in one node. On the 6th insertion, the node splits and the median key moves up to become the new root.

What should I see?

After inserting key 12 (the 5th key), the root shows all five keys in one node: [5|6|10|12|20]. After inserting 30 (the 6th key), the root splits. The tree jumps to two levels with a single routing key in the new root.

At the end, the search output shows Record-12 for key 12 and NOT FOUND for key 99.

Program won't compile or output looks wrong?

  • If you see a "type or namespace 'BTreeIndexEngine' could not be found" error, check that Program.cs starts with using BTreeIndexEngine; on the first line.
  • If you see an empty tree at every step, ensure btree.Root is passed to PrintBTree (not btree itself).
  • If you never see a split, confirm your degree is set to 3. A higher degree means nodes hold more keys before splitting.

Help me debug my B-tree print output

Add in-order traversal to confirm sorted output

A B-tree keeps all keys in sorted order by construction. An in-order traversal proves this by visiting each key in ascending sequence: recurse into the left child, visit the key, recurse into the right child.

  • Open BTree.cs and scroll to the bottom of the BTree<TKey, TValue> class, after the SearchNode method's closing brace.
  • Add the following two methods inside the class, before the final closing brace:
    public List<(TKey Key, TValue Value)> InOrderTraversal()
    {
        var result = new List<(TKey, TValue)>();
        InOrderTraversalNode(_root, result);
        return result;
    }

    private void InOrderTraversalNode(BTreeNode<TKey, TValue>? node, List<(TKey, TValue)> result)
    {
        if (node == null) return;

        for (int i = 0; i < node.Keys.Count; i++)
        {
            // Visit left child before the key
            if (!node.IsLeaf)
                InOrderTraversalNode(node.Children[i], result);
            // Visit the key itself
            result.Add((node.Keys[i], node.Values[i]));
        }

        // Visit the rightmost child
        if (!node.IsLeaf)
            InOrderTraversalNode(node.Children[node.Keys.Count], result);
    }

What does this code do?

  • InOrderTraversal() is the public entry point. It creates a results list and kicks off the recursive helper.
  • InOrderTraversalNode visits children interleaved with keys. For each key at index i, it first recurses into Children[i] (all smaller keys), then adds the key to the result.
  • The final Children[node.Keys.Count] call visits the rightmost subtree, which contains all keys larger than the last key in the node.
  • Save BTree.cs.

Now use the traversal in your demo to print the sorted output.

  • Return to Program.cs and add the following code at the very bottom of the file:
Console.WriteLine("In-order traversal (sorted):");
foreach (var (k, v) in btree.InOrderTraversal())
    Console.Write($"{k} ");
Console.WriteLine();
Console.WriteLine();

What does this code do?

This calls InOrderTraversal() to get every key-value pair in sorted order, then prints just the keys separated by spaces. If the tree is correctly structured, you will see all 10 keys in ascending order.

  • Save Program.cs.
  • Run the program again with Ctrl+F5. Scroll to the bottom of the console output.

You should see the in-order traversal output: 3 5 6 7 8 10 12 17 20 30. All 10 keys printed in ascending order, confirming the tree maintains correct ordering through every split.

Keys not in sorted order?

  • If keys are missing, check that InOrderTraversalNode recurses into Children[node.Keys.Count] after the loop. This rightmost child holds the largest keys.
  • If you get an index out of range exception, ensure the if (!node.IsLeaf) guards are present. Leaf nodes have no children to recurse into.

Help me fix my in-order traversal

✔️ Awesome, I've got everything!

Great. Double check you have saved both BTree.cs and Program.cs.

ⓧ I'd like to double check the full code

Here is the full BTree.cs with the new traversal methods at the bottom:

namespace BTreeIndexEngine;

public class BTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    public BTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            _root = new BTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    private void InsertNonFull(BTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        int i = node.Keys.Count - 1;

        if (node.IsLeaf)
        {
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }

    private void SplitChild(BTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BTreeNode<TKey, TValue>(fullChild.IsLeaf);

        // Move keys and values after median to new child
        for (int j = mid + 1; j < fullChild.Keys.Count; j++)
        {
            newChild.Keys.Add(fullChild.Keys[j]);
            newChild.Values.Add(fullChild.Values[j]);
        }

        // Move children after median to new child (if internal node)
        if (!fullChild.IsLeaf)
        {
            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));
        }

        // Promote median key to parent
        TKey medianKey = fullChild.Keys[mid];
        TValue medianValue = fullChild.Values[mid];

        // Remove keys/values from mid onward in full child
        fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
        fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

        // Insert median into parent
        parent.Keys.Insert(childIndex, medianKey);
        parent.Values.Insert(childIndex, medianValue);
        parent.Children.Insert(childIndex + 1, newChild);
    }

    public TValue? Search(TKey key)
    {
        return SearchNode(_root, key);
    }

    private TValue? SearchNode(BTreeNode<TKey, TValue>? node, TKey key)
    {
        if (node == null)
            return default;

        int i = 0;
        while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) > 0)
            i++;

        if (i < node.Keys.Count && key.CompareTo(node.Keys[i]) == 0)
            return node.Values[i];

        if (node.IsLeaf)
            return default;

        return SearchNode(node.Children[i], key);
    }

    public List<(TKey Key, TValue Value)> InOrderTraversal()
    {
        var result = new List<(TKey, TValue)>();
        InOrderTraversalNode(_root, result);
        return result;
    }

    private void InOrderTraversalNode(BTreeNode<TKey, TValue>? node, List<(TKey, TValue)> result)
    {
        if (node == null) return;

        for (int i = 0; i < node.Keys.Count; i++)
        {
            if (!node.IsLeaf)
                InOrderTraversalNode(node.Children[i], result);
            result.Add((node.Keys[i], node.Values[i]));
        }

        if (!node.IsLeaf)
            InOrderTraversalNode(node.Children[node.Keys.Count], result);
    }
}

Here is the full Program.cs:

using BTreeIndexEngine;

Console.WriteLine("=== B-Tree and B+ Tree Index Engine ===");
Console.WriteLine();

int degree = 3; // Minimum degree t=3, max keys per node = 2t-1 = 5
var keys = new[] { 10, 20, 5, 6, 12, 30, 7, 17, 3, 8 };

// --- B-Tree Demo ---
Console.WriteLine("--- B-Tree (degree 3) ---");
Console.WriteLine("Data stored at EVERY level (internal + leaf nodes)");
Console.WriteLine();

var btree = new BTree<int, string>(degree);

foreach (var key in keys)
{
    btree.Insert(key, $"Record-{key}");
    Console.WriteLine($"Inserted {key}:");
    TreePrinter.PrintBTree(btree.Root);
}

Console.WriteLine("Search for key 12: " + (btree.Search(12) ?? "NOT FOUND"));
Console.WriteLine("Search for key 99: " + (btree.Search(99) ?? "NOT FOUND"));
Console.WriteLine();

Console.WriteLine("In-order traversal (sorted):");
foreach (var (k, v) in btree.InOrderTraversal())
    Console.Write($"{k} ");
Console.WriteLine();
Console.WriteLine();

You can now see the B-tree growing in real time. Every split keeps the tree balanced. Next, you will build the B+ tree, which takes a fundamentally different approach to where data lives.

Build the B+ Tree with Linked Leaves

Your B-tree stores data at every level of the tree. That works, but it means range queries must bounce up and down through internal nodes to visit keys in order.

A B+ tree solves this by pushing all data down to the leaf level and linking leaves together in a chain. In this step, you will build a complete B+ tree with insert and search, implementing the structural differences that make B+ trees the standard for database indexing.

In this step, get ready to:
  • Define the B+ tree node with a Next pointer for leaf-to-leaf linking.
  • Implement insertion with separate splitting logic for leaf nodes and internal nodes.
  • Implement search that always traverses to a leaf node.
Create the B+ tree node class

The B+ tree node looks similar to the B-tree node, but with one critical addition: a Next pointer. This pointer links each leaf node to its right neighbor, forming a chain that enables fast sequential scanning.

  • In BPlusTreeNode.cs, replace the empty file contents with the following code:
namespace BTreeIndexEngine;

public class BPlusTreeNode<TKey, TValue> where TKey : IComparable<TKey>
{
    public List<TKey> Keys { get; set; }
    public List<TValue> Values { get; set; }
    public List<BPlusTreeNode<TKey, TValue>> Children { get; set; }
    public bool IsLeaf { get; set; }
    // Pointer to the next leaf node (forms the leaf chain)
    public BPlusTreeNode<TKey, TValue>? Next { get; set; }

    public BPlusTreeNode(bool isLeaf)
    {
        Keys = new List<TKey>();
        Values = new List<TValue>();
        Children = new List<BPlusTreeNode<TKey, TValue>>();
        IsLeaf = isLeaf;
        Next = null;
    }
}

What does this code do?

This class is nearly identical to BTreeNode, with one key addition.

  • Keys stores the keys in sorted order. In leaf nodes these are actual data keys. In internal nodes these are routing keys that guide searches.
  • Values only holds data in leaf nodes. Internal nodes use Children pointers instead.
  • Next is the new piece. It links each leaf to the next leaf on its right, creating a chain you can walk for range queries without climbing back up the tree.
  • Save BPlusTreeNode.cs.
  • Build the project by pressing Ctrl+Shift+B in Visual Studio. You should see Build succeeded in the Output window.

Build failing?

  • Check that the namespace is BTreeIndexEngine (matching your project name). A mismatched namespace prevents other files from finding this class.
  • Make sure BPlusTreeNode<TKey, TValue>? includes the ? for the nullable Next property. Without it, the compiler warns about uninitialized non-nullable references.

Help me debug my BPlusTreeNode class build error.

Implement insertion with leaf and internal node splitting

The Insert and InsertNonFull methods follow the same traversal logic as the B-tree. The key difference lives in SplitChild: when a leaf splits, the median key is copied up to the parent (not moved). When an internal node splits, the median is moved up, just like in a B-tree.

  • In BPlusTree.cs, replace the empty file contents with the class declaration, constructor, and the insertion traversal methods:
namespace BTreeIndexEngine;

public class BPlusTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BPlusTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    public BPlusTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BPlusTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            // First insertion: create a leaf root
            _root = new BPlusTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        // If root is full, split it before descending
        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BPlusTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    private void InsertNonFull(BPlusTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        if (node.IsLeaf)
        {
            // Insert directly into leaf in sorted position
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            // Find the correct child to descend into
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            // Split child if full before descending
            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }
}

What does this code do?

The traversal logic is nearly identical to your B-tree implementation. The tree navigates from the root, comparing keys to find the correct child, and inserts directly when it reaches a leaf.

  • Insert handles the special case where the root is full. It creates a new root and splits the old root before continuing.
  • InsertNonFull distinguishes between leaf nodes (insert directly) and internal nodes (find correct child, split if necessary, descend).

The real difference from the B-tree comes next, in the SplitChild method.

The project will not compile yet because SplitChild is referenced but not defined. You will add it next.

  • Add the SplitChild method inside the BPlusTree class, below the InsertNonFull method (but before the closing } of the class):
    private void SplitChild(BPlusTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BPlusTreeNode<TKey, TValue>(fullChild.IsLeaf);

        if (fullChild.IsLeaf)
        {
            // Leaf split: copy median key up, keep all data in leaves
            for (int j = mid; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
                newChild.Values.Add(fullChild.Values[j]);
            }

            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
            fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

            // Maintain leaf chain
            newChild.Next = fullChild.Next;
            fullChild.Next = newChild;

            // Copy first key of new child up to parent (not move)
            parent.Keys.Insert(childIndex, newChild.Keys[0]);
            parent.Children.Insert(childIndex + 1, newChild);
        }
        else
        {
            // Internal node split: move median key up (same as B-tree)
            for (int j = mid + 1; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
            }

            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));

            TKey medianKey = fullChild.Keys[mid];
            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);

            parent.Keys.Insert(childIndex, medianKey);
            parent.Children.Insert(childIndex + 1, newChild);
        }
    }

Why are leaf and internal splits different?

This is the core structural difference between B-trees and B+ trees.

  • Leaf split: the median key is copied up to the parent. The original key stays in the new right leaf because all data must remain in leaves. The Next pointer is rewired so the old leaf points to the new leaf, maintaining the chain.
  • Internal split: the median key is moved up to the parent (removed from the child). Internal nodes are pure routing. They do not store data, so no duplication is needed.

This design guarantees that a sequential scan of all leaf nodes (following Next pointers) visits every single record in the tree exactly once.

  • Save BPlusTree.cs.
  • Build the project by pressing Ctrl+Shift+B. You should see Build succeeded in the Output window.

Seeing a build error in BPlusTree.cs?

  • Make sure SplitChild is placed inside the BPlusTree class body (before the final closing brace). If it is outside the class, the compiler cannot find it.
  • Check that BPlusTreeNode (not BTreeNode) is used throughout. Mixing up the node types causes type mismatch errors.
  • Verify the RemoveRange calls use the correct index math. The first argument is the start index, the second is the count of elements to remove.

Help me fix my BPlusTree SplitChild build error.

Implement search that always reaches leaf nodes

In a B-tree, search can stop at any level if it finds the key in an internal node. In a B+ tree, all data lives in the leaves. Search must always traverse all the way down to a leaf, then scan that leaf for the key.

  • Add the Search method inside the BPlusTree class, below SplitChild (before the closing } of the class):
    public TValue? Search(TKey key)
    {
        if (_root == null)
            return default;

        var node = _root;

        // Always traverse to leaf (all data lives there)
        while (!node.IsLeaf)
        {
            int i = 0;
            while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) >= 0)
                i++;
            node = node.Children[i];
        }

        // Search within leaf
        for (int i = 0; i < node.Keys.Count; i++)
        {
            if (key.CompareTo(node.Keys[i]) == 0)
                return node.Values[i];
        }

        return default;
    }

What does this code do?

  • The while (!node.IsLeaf) loop navigates through internal nodes using routing keys. It compares the search key against each routing key to decide which child to follow.
  • Once at a leaf, a simple linear scan checks each key for an exact match.
  • This guarantees every search takes O(log n) steps regardless of where the data is. In a B-tree, searches for keys that happen to be in the root are O(1), but that inconsistency means B+ trees have more predictable I/O patterns for databases.
  • Save BPlusTree.cs.
  • Build the project by pressing Ctrl+Shift+B. You should see Build succeeded with 0 errors in the Output window.

Search method not compiling?

  • Make sure the return type is TValue? with the nullable marker. Without the ?, returning default may trigger a warning for value types.
  • Check that node.Children[i] is accessed after the while loop increments i. The index i points to the child subtree whose range contains the search key.

Help me fix my B+ tree Search method.

✔️ Awesome, I've got everything!

Great. Make sure both BPlusTreeNode.cs and BPlusTree.cs are saved and the project builds with zero errors.

ⓧ I'd like to double check the full code

Here is the complete BPlusTreeNode.cs:

namespace BTreeIndexEngine;

public class BPlusTreeNode<TKey, TValue> where TKey : IComparable<TKey>
{
    public List<TKey> Keys { get; set; }
    public List<TValue> Values { get; set; }
    public List<BPlusTreeNode<TKey, TValue>> Children { get; set; }
    public bool IsLeaf { get; set; }
    public BPlusTreeNode<TKey, TValue>? Next { get; set; }

    public BPlusTreeNode(bool isLeaf)
    {
        Keys = new List<TKey>();
        Values = new List<TValue>();
        Children = new List<BPlusTreeNode<TKey, TValue>>();
        IsLeaf = isLeaf;
        Next = null;
    }
}

Here is the complete BPlusTree.cs:

namespace BTreeIndexEngine;

public class BPlusTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BPlusTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    public BPlusTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BPlusTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            _root = new BPlusTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BPlusTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    private void InsertNonFull(BPlusTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        if (node.IsLeaf)
        {
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }

    private void SplitChild(BPlusTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BPlusTreeNode<TKey, TValue>(fullChild.IsLeaf);

        if (fullChild.IsLeaf)
        {
            // Leaf split: copy median key up, keep all data in leaves
            for (int j = mid; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
                newChild.Values.Add(fullChild.Values[j]);
            }

            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
            fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

            // Maintain leaf chain
            newChild.Next = fullChild.Next;
            fullChild.Next = newChild;

            // Copy first key of new child up to parent (not move)
            parent.Keys.Insert(childIndex, newChild.Keys[0]);
            parent.Children.Insert(childIndex + 1, newChild);
        }
        else
        {
            // Internal node split: move median key up (same as B-tree)
            for (int j = mid + 1; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
            }

            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));

            TKey medianKey = fullChild.Keys[mid];
            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);

            parent.Keys.Insert(childIndex, medianKey);
            parent.Children.Insert(childIndex + 1, newChild);
        }
    }

    public TValue? Search(TKey key)
    {
        if (_root == null)
            return default;

        var node = _root;

        // Always traverse to leaf
        while (!node.IsLeaf)
        {
            int i = 0;
            while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) >= 0)
                i++;
            node = node.Children[i];
        }

        // Search within leaf
        for (int i = 0; i < node.Keys.Count; i++)
        {
            if (key.CompareTo(node.Keys[i]) == 0)
                return node.Values[i];
        }

        return default;
    }
}

Your B+ tree can now insert and search. In the next step, you will add range queries that exploit the leaf chain and build a side-by-side comparison showing exactly why databases chose this structure.

Add Range Queries and Compare Both Trees

Your B+ tree can insert and search for individual keys. Now it is time for the payoff that justifies the extra complexity of linked leaves.

Range queries are the reason databases chose B+ trees over B-trees. Instead of backtracking up and down the tree to find every key in a range, you traverse to one leaf and follow the Next pointers forward. In this step, you will implement that range query and compare both trees side-by-side.

In this step, get ready to:
  • Add a RangeQuery method to the B+ tree that walks the linked leaf chain.
  • Build a PrintBPlusTree utility and a side-by-side comparison demo.
  • Run a range query and observe why B+ trees dominate database indexing.
Add the RangeQuery method to BPlusTree

A range query takes a start key and an end key, then returns every key-value pair between them in sorted order. The B+ tree's linked leaves make this efficient: find the starting leaf once (O(log n)), then walk forward through the chain without ever going back up the tree.

  • In BPlusTree.cs, add this RangeQuery method below the existing Search method:
    public List<(TKey Key, TValue Value)> RangeQuery(TKey start, TKey end)
    {
        var result = new List<(TKey, TValue)>();
        if (_root == null)
            return result;

        // Find the leaf that might contain 'start'
        var node = _root;
        while (!node.IsLeaf)
        {
            int i = 0;
            while (i < node.Keys.Count && start.CompareTo(node.Keys[i]) >= 0)
                i++;
            node = node.Children[i];
        }

        // Walk the leaf chain collecting keys in range
        while (node != null)
        {
            for (int i = 0; i < node.Keys.Count; i++)
            {
                if (node.Keys[i].CompareTo(start) >= 0 && node.Keys[i].CompareTo(end) <= 0)
                    result.Add((node.Keys[i], node.Values[i]));
                else if (node.Keys[i].CompareTo(end) > 0)
                    return result;
            }
            node = node.Next;
        }

        return result;
    }

What does this code do?

The method has two phases that exploit the B+ tree's structure.

  • Phase 1: Traverse from root to the leaf that could contain start. This is the same traversal as Search and costs O(log n).
  • Phase 2: Walk the Next linked list, collecting every key between start and end. Stop early the moment a key exceeds end.
  • Save BPlusTree.cs.
  • Press Ctrl+Shift+B to build. The project should compile with zero errors.

Seeing a compile error?

  • If you see an error about RangeQuery not returning on all paths, make sure the final return result; sits outside the while loop at the very end of the method.
  • Check that the method is placed inside the BPlusTree<TKey, TValue> class braces, not outside them.

Help me fix my RangeQuery compile error in BPlusTree.cs

✔️ Awesome, I've got everything!

Great. Make sure you have saved BPlusTree.cs before moving on.

ⓧ I'd like to double check the full code

namespace BTreeIndexEngine;

public class BPlusTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private BPlusTreeNode<TKey, TValue>? _root;
    private readonly int _degree;

    public BPlusTreeNode<TKey, TValue>? Root => _root;
    public int Degree => _degree;

    public BPlusTree(int degree)
    {
        if (degree < 2)
            throw new ArgumentException("Degree must be at least 2.");
        _degree = degree;
        _root = null;
    }

    public void Insert(TKey key, TValue value)
    {
        if (_root == null)
        {
            _root = new BPlusTreeNode<TKey, TValue>(true);
            _root.Keys.Add(key);
            _root.Values.Add(value);
            return;
        }

        if (_root.Keys.Count == 2 * _degree - 1)
        {
            var newRoot = new BPlusTreeNode<TKey, TValue>(false);
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, key, value);
    }

    private void InsertNonFull(BPlusTreeNode<TKey, TValue> node, TKey key, TValue value)
    {
        if (node.IsLeaf)
        {
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            node.Keys.Insert(i + 1, key);
            node.Values.Insert(i + 1, value);
        }
        else
        {
            int i = node.Keys.Count - 1;
            while (i >= 0 && key.CompareTo(node.Keys[i]) < 0)
                i--;
            i++;

            if (node.Children[i].Keys.Count == 2 * _degree - 1)
            {
                SplitChild(node, i);
                if (key.CompareTo(node.Keys[i]) > 0)
                    i++;
            }

            InsertNonFull(node.Children[i], key, value);
        }
    }

    private void SplitChild(BPlusTreeNode<TKey, TValue> parent, int childIndex)
    {
        var fullChild = parent.Children[childIndex];
        int mid = _degree - 1;

        var newChild = new BPlusTreeNode<TKey, TValue>(fullChild.IsLeaf);

        if (fullChild.IsLeaf)
        {
            for (int j = mid; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
                newChild.Values.Add(fullChild.Values[j]);
            }

            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);
            fullChild.Values.RemoveRange(mid, fullChild.Values.Count - mid);

            newChild.Next = fullChild.Next;
            fullChild.Next = newChild;

            parent.Keys.Insert(childIndex, newChild.Keys[0]);
            parent.Children.Insert(childIndex + 1, newChild);
        }
        else
        {
            for (int j = mid + 1; j < fullChild.Keys.Count; j++)
            {
                newChild.Keys.Add(fullChild.Keys[j]);
            }

            for (int j = mid + 1; j <= fullChild.Children.Count - 1; j++)
            {
                newChild.Children.Add(fullChild.Children[j]);
            }
            fullChild.Children.RemoveRange(mid + 1, fullChild.Children.Count - (mid + 1));

            TKey medianKey = fullChild.Keys[mid];
            fullChild.Keys.RemoveRange(mid, fullChild.Keys.Count - mid);

            parent.Keys.Insert(childIndex, medianKey);
            parent.Children.Insert(childIndex + 1, newChild);
        }
    }

    public TValue? Search(TKey key)
    {
        if (_root == null)
            return default;

        var node = _root;

        while (!node.IsLeaf)
        {
            int i = 0;
            while (i < node.Keys.Count && key.CompareTo(node.Keys[i]) >= 0)
                i++;
            node = node.Children[i];
        }

        for (int i = 0; i < node.Keys.Count; i++)
        {
            if (key.CompareTo(node.Keys[i]) == 0)
                return node.Values[i];
        }

        return default;
    }

    public List<(TKey Key, TValue Value)> RangeQuery(TKey start, TKey end)
    {
        var result = new List<(TKey, TValue)>();
        if (_root == null)
            return result;

        var node = _root;
        while (!node.IsLeaf)
        {
            int i = 0;
            while (i < node.Keys.Count && start.CompareTo(node.Keys[i]) >= 0)
                i++;
            node = node.Children[i];
        }

        while (node != null)
        {
            for (int i = 0; i < node.Keys.Count; i++)
            {
                if (node.Keys[i].CompareTo(start) >= 0 && node.Keys[i].CompareTo(end) <= 0)
                    result.Add((node.Keys[i], node.Values[i]));
                else if (node.Keys[i].CompareTo(end) > 0)
                    return result;
            }
            node = node.Next;
        }

        return result;
    }
}
Build the B+ tree printer and demo

To compare both trees visually, you need a printer that shows the B+ tree's structure and its leaf chain. The printer labels each node as I (internal) or L (leaf), then prints the linked leaf chain at the bottom.

  • In TreePrinter.cs, add this PrintBPlusTree method below the existing PrintBTree method:
    public static void PrintBPlusTree<TKey, TValue>(BPlusTreeNode<TKey, TValue>? root) where TKey : IComparable<TKey>
    {
        if (root == null)
        {
            Console.WriteLine("(empty tree)");
            return;
        }

        var queue = new Queue<(BPlusTreeNode<TKey, TValue> Node, int Level)>();
        queue.Enqueue((root, 0));
        int currentLevel = -1;

        while (queue.Count > 0)
        {
            var (node, level) = queue.Dequeue();

            if (level != currentLevel)
            {
                if (currentLevel >= 0) Console.WriteLine();
                Console.Write($"Level {level}: ");
                currentLevel = level;
            }
            else
            {
                Console.Write("  ");
            }

            string label = node.IsLeaf ? "L" : "I";
            Console.Write($"{label}[" + string.Join("|", node.Keys) + "]");

            if (!node.IsLeaf)
            {
                foreach (var child in node.Children)
                    queue.Enqueue((child, level + 1));
            }
        }
        Console.WriteLine();

        // Print leaf chain
        Console.Write("Leaf chain: ");
        var leaf = root;
        while (!leaf.IsLeaf)
            leaf = leaf.Children[0];
        while (leaf != null)
        {
            Console.Write("[" + string.Join("|", leaf.Keys) + "] -> ");
            leaf = leaf.Next;
        }
        Console.WriteLine("null");
        Console.WriteLine();
    }

What does this code do?

  • The BFS section works the same as PrintBTree, but prefixes each node with I or L so you can see which nodes hold data (leaves) and which are just routing (internal).
  • After the BFS, the method walks down to the leftmost leaf, then follows the Next pointers to print the full leaf chain. This is the same linked list that RangeQuery uses.
  • Save TreePrinter.cs.

✔️ Awesome, I've got everything!

Great. Make sure you have saved TreePrinter.cs before moving on.

ⓧ I'd like to double check the full code

namespace BTreeIndexEngine;

public static class TreePrinter
{
    public static void PrintBTree<TKey, TValue>(BTreeNode<TKey, TValue>? root) where TKey : IComparable<TKey>
    {
        if (root == null)
        {
            Console.WriteLine("(empty tree)");
            return;
        }

        var queue = new Queue<(BTreeNode<TKey, TValue> Node, int Level)>();
        queue.Enqueue((root, 0));
        int currentLevel = -1;

        while (queue.Count > 0)
        {
            var (node, level) = queue.Dequeue();

            if (level != currentLevel)
            {
                if (currentLevel >= 0) Console.WriteLine();
                Console.Write($"Level {level}: ");
                currentLevel = level;
            }
            else
            {
                Console.Write("  ");
            }

            Console.Write("[" + string.Join("|", node.Keys) + "]");

            if (!node.IsLeaf)
            {
                foreach (var child in node.Children)
                    queue.Enqueue((child, level + 1));
            }
        }
        Console.WriteLine();
        Console.WriteLine();
    }

    public static void PrintBPlusTree<TKey, TValue>(BPlusTreeNode<TKey, TValue>? root) where TKey : IComparable<TKey>
    {
        if (root == null)
        {
            Console.WriteLine("(empty tree)");
            return;
        }

        var queue = new Queue<(BPlusTreeNode<TKey, TValue> Node, int Level)>();
        queue.Enqueue((root, 0));
        int currentLevel = -1;

        while (queue.Count > 0)
        {
            var (node, level) = queue.Dequeue();

            if (level != currentLevel)
            {
                if (currentLevel >= 0) Console.WriteLine();
                Console.Write($"Level {level}: ");
                currentLevel = level;
            }
            else
            {
                Console.Write("  ");
            }

            string label = node.IsLeaf ? "L" : "I";
            Console.Write($"{label}[" + string.Join("|", node.Keys) + "]");

            if (!node.IsLeaf)
            {
                foreach (var child in node.Children)
                    queue.Enqueue((child, level + 1));
            }
        }
        Console.WriteLine();

        Console.Write("Leaf chain: ");
        var leaf = root;
        while (!leaf.IsLeaf)
            leaf = leaf.Children[0];
        while (leaf != null)
        {
            Console.Write("[" + string.Join("|", leaf.Keys) + "] -> ");
            leaf = leaf.Next;
        }
        Console.WriteLine("null");
        Console.WriteLine();
    }
}

Now wire up the B+ tree demo in Program.cs. You will insert the same 10 keys into the B+ tree, print its structure, and confirm search works.

  • In Program.cs, add the following code at the bottom of the file (after the existing B-tree in-order traversal output):
// --- B+ Tree Demo ---
Console.WriteLine("--- B+ Tree (degree 3) ---");
Console.WriteLine("Data stored ONLY in leaf nodes, leaves are linked");
Console.WriteLine();

var bPlusTree = new BPlusTree<int, string>(degree);

foreach (var key in keys)
{
    bPlusTree.Insert(key, $"Record-{key}");
}

Console.WriteLine("Final B+ Tree structure:");
TreePrinter.PrintBPlusTree(bPlusTree.Root);

Console.WriteLine("Search for key 12: " + (bPlusTree.Search(12) ?? "NOT FOUND"));
Console.WriteLine();

What does this code do?

  • This creates a BPlusTree<int, string> with the same degree and keys as the B-tree demo, so you can compare their structures directly.
  • Unlike the B-tree demo, it inserts all keys without printing after each one. You will see the final structure printed by PrintBPlusTree with I/L labels and the leaf chain.
  • Save Program.cs and build with Ctrl+Shift+B.
  • The project should compile with zero errors. If it does not, check that your using BTreeIndexEngine; directive is at the top of Program.cs.

Build failing after adding the B+ tree demo?

  • If you see an error about PrintBPlusTree not existing, make sure you saved TreePrinter.cs after adding the method in the previous chunk.
  • If you see an error about BPlusTree not containing a definition for Search, confirm that your BPlusTree.cs has the Search method from the previous step.

Help me fix my B+ tree demo build error

Run the range query and compare both trees

The final section of the demo runs a range query for keys 5 through 12, then prints a summary of why databases prefer B+ trees. This is where the leaf chain proves its worth.

  • In Program.cs, add this code directly below the B+ tree search output you just added:
// --- Range Query Demo ---
Console.WriteLine("--- Range Query: keys 5 to 12 ---");
Console.WriteLine("B+ Tree walks the linked leaf chain (fast sequential access):");
var rangeResults = bPlusTree.RangeQuery(5, 12);
foreach (var (k, v) in rangeResults)
    Console.Write($"{k}:{v}  ");
Console.WriteLine();
Console.WriteLine();

Console.WriteLine("--- Why Databases Use B+ Trees ---");
Console.WriteLine("1. All data in leaves = predictable I/O (always same depth)");
Console.WriteLine("2. Linked leaves = fast range scans (no backtracking)");
Console.WriteLine("3. Internal nodes are pure routing = more keys fit per page = shallower tree");

What does this code do?

  • RangeQuery(5, 12) finds the leaf containing 5, then walks forward through linked leaves collecting every key up to 12. No backtracking through parent nodes is needed.
  • The three printed reasons summarize why every major database (MySQL InnoDB, PostgreSQL, SQLite, MongoDB WiredTiger) uses B+ trees for on-disk indexes.
  • Save Program.cs.
  • Run the program by pressing Ctrl+F5 in Visual Studio (or run dotnet run in the terminal).

Scroll to the range query output. You should see 5:Record-5 6:Record-6 7:Record-7 8:Record-8 10:Record-10 12:Record-12 printed in sorted order.

What should I see?

The console output shows both tree structures. The B-tree prints data at every level (root and children all hold values). The B+ tree labels internal nodes with I (routing only) and leaf nodes with L (all data here).

The leaf chain at the bottom shows all leaves linked left-to-right. The range query result proves that walking this chain gives you every key between 5 and 12 in sorted order without backtracking.

Range query returning empty or incorrect results?

  • If the result is empty, check that your SplitChild method in BPlusTree.cs correctly sets fullChild.Next = newChild during leaf splits. Without this link, RangeQuery cannot walk between leaves.
  • If keys are missing or out of order, verify that your leaf split copies keys starting at index mid (not mid + 1) to keep all data in the leaves.

Help me debug my B+ tree range query

✔️ Awesome, I've got everything!

Great. Make sure you have saved Program.cs before moving on.

ⓧ I'd like to double check the full code

using BTreeIndexEngine;

Console.WriteLine("=== B-Tree and B+ Tree Index Engine ===");
Console.WriteLine();

int degree = 3; // Minimum degree t=3, max keys per node = 2t-1 = 5
var keys = new[] { 10, 20, 5, 6, 12, 30, 7, 17, 3, 8 };

// --- B-Tree Demo ---
Console.WriteLine("--- B-Tree (degree 3) ---");
Console.WriteLine("Data stored at EVERY level (internal + leaf nodes)");
Console.WriteLine();

var btree = new BTree<int, string>(degree);

foreach (var key in keys)
{
    btree.Insert(key, $"Record-{key}");
    Console.WriteLine($"Inserted {key}:");
    TreePrinter.PrintBTree(btree.Root);
}

Console.WriteLine("Search for key 12: " + (btree.Search(12) ?? "NOT FOUND"));
Console.WriteLine("Search for key 99: " + (btree.Search(99) ?? "NOT FOUND"));
Console.WriteLine();

Console.WriteLine("In-order traversal (sorted):");
foreach (var (k, v) in btree.InOrderTraversal())
    Console.Write($"{k} ");
Console.WriteLine();
Console.WriteLine();

// --- B+ Tree Demo ---
Console.WriteLine("--- B+ Tree (degree 3) ---");
Console.WriteLine("Data stored ONLY in leaf nodes, leaves are linked");
Console.WriteLine();

var bPlusTree = new BPlusTree<int, string>(degree);

foreach (var key in keys)
{
    bPlusTree.Insert(key, $"Record-{key}");
}

Console.WriteLine("Final B+ Tree structure:");
TreePrinter.PrintBPlusTree(bPlusTree.Root);

Console.WriteLine("Search for key 12: " + (bPlusTree.Search(12) ?? "NOT FOUND"));
Console.WriteLine();

// --- Range Query Demo ---
Console.WriteLine("--- Range Query: keys 5 to 12 ---");
Console.WriteLine("B+ Tree walks the linked leaf chain (fast sequential access):");
var rangeResults = bPlusTree.RangeQuery(5, 12);
foreach (var (k, v) in rangeResults)
    Console.Write($"{k}:{v}  ");
Console.WriteLine();
Console.WriteLine();

Console.WriteLine("--- Why Databases Use B+ Trees ---");
Console.WriteLine("1. All data in leaves = predictable I/O (always same depth)");
Console.WriteLine("2. Linked leaves = fast range scans (no backtracking)");
Console.WriteLine("3. Internal nodes are pure routing = more keys fit per page = shallower tree");

Why B+ trees over B-trees for databases?

You just built both and saw the difference firsthand. In a B-tree, data lives at every level, so a range scan must traverse up and down repeatedly. In a B+ tree, all data lives in the leaves and the leaves are linked.

This means internal nodes become pure routing with no data payload. More routing keys fit in a single disk page, making the tree shallower. Fewer levels means fewer disk reads per lookup.

Secret mission

Add B-Tree Deletion with Borrowing and Merging

Insertion was the warm-up. Deletion is where B-trees get truly interesting. When you remove a key and a node drops below the minimum key count, the tree must rebalance itself through borrowing from siblings or merging nodes together. Implement full deletion with all three cases and watch the tree heal itself.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files for future reference or delete them entirely.

Resources you used:

  • BTreeIndexEngine project folder (local files on your machine).

Keep everything running

No action needed. Choose this if you want to keep experimenting with your B-tree and B+ tree implementations.

  • Your project files remain in the BTreeIndexEngine folder wherever you created them.
  • You can reopen the solution in Visual Studio at any time by double-clicking the BTreeIndexEngine.sln file.

Pause - I'll come back to this later

Close Visual Studio to free up memory. Your project files stay on disk and are ready to reopen whenever you come back.

  • Close Visual Studio.
  • Your project folder stays on your machine. No processes are left running.

Delete - I don't want to use this again

Remove all project files from your machine.

  • Close Visual Studio if it is still open.
  • Delete the BTreeIndexEngine folder by running the appropriate command for your operating system.

macOS

  • Open Terminal and navigate to the parent folder where your project lives, then run:
rm -rf BTreeIndexEngine

Windows

  • Open PowerShell and navigate to the parent folder where your project lives, then run:
rmdir /s /q BTreeIndexEngine
  • Confirm the folder is gone by running ls (macOS) or dir (Windows) in the parent folder. You should no longer see BTreeIndexEngine listed.

That's a Wrap!

That's a Wrap!

Nice work! You just built two complete index engines from scratch in C#, the same data structures that power every major database from PostgreSQL to MySQL to SQLite.

You've learned how to:

  • Build a generic B-tree with insert, search, and node splitting that promotes median keys to keep the tree balanced.
  • Implement a B+ tree with linked leaf nodes and range queries that exploit sequential leaf scanning for fast data retrieval.
  • Visualize both tree structures side-by-side and understand why B+ trees dominate database indexing with predictable I/O, pure routing nodes, and fast range scans.
  • Secret Mission: Implement B-tree deletion with borrowing from siblings and merging underflowed nodes, the most complex B-tree operation.

Ready to quiz yourself?