B-Tree / B+Tree (Go & Python)

from typing import List, Optional, Tuple
class Node:
    """A single B+tree node. Internal nodes hold routing keys and child
    pointers only; leaf nodes hold keys and their associated values, plus a
    pointer to the next leaf for range scans."""
    def __init__(self, leaf: bool) -> None:
        self.leaf = leaf
        self.keys: List[int] = []
        self.children: List["Node"] = []  # internal nodes only
        self.values: List[int] = []  # leaf nodes only, parallel to keys
        self.next: Optional["Node"] = None  # leaf chain pointer, leaf nodes only
class BPlusTree:
    """An in-memory B+tree. order is the maximum number of children an
    internal node may have (== max keys + 1); real databases size this to
    the number of keys that fit in one disk page -- typically hundreds."""
    def __init__(self, order: int) -> None:
        if order < 3:
            raise ValueError("order must be >= 3")
        self.order = order
        self.root = Node(leaf=True)
    def _max_keys(self) -> int:
        return self.order - 1
    def search(self, key: int) -> Tuple[Optional[int], bool]:
        """Return (value, True) if key is present, else (None, False)."""
        n = self.root
        while not n.leaf:
            i = 0
            while i < len(n.keys) and key >= n.keys[i]:
                i += 1
            n = n.children[i]
        for i, k in enumerate(n.keys):
            if k == key:
                return n.values[i], True
        return None, False
    def insert(self, key: int, value: int) -> None:
        """Insert or update key/value, splitting nodes top-down as needed to
        keep every node within self._max_keys() keys."""
        promoted, new_right = self._insert(self.root, key, value)
        if new_right is not None:
            new_root = Node(leaf=False)
            new_root.keys = [promoted]
            new_root.children = [self.root, new_right]
            self.root = new_root
    def _insert(self, n: Node, key: int, value: int) -> Tuple[Optional[int], Optional[Node]]:
        """Recurse to the correct leaf, insert, and split any node (leaf or
        internal) that overflows. Returns a promoted key and new right
        sibling when the current node split, or (None, None) otherwise."""
        if n.leaf:
            i = 0
            while i < len(n.keys) and n.keys[i] < key:
                i += 1
            if i < len(n.keys) and n.keys[i] == key:
                n.values[i] = value  # update existing key in place
                return None, None
            n.keys.insert(i, key)
            n.values.insert(i, value)
            if len(n.keys) <= self._max_keys():
                return None, None
            return self._split_leaf(n)
        i = 0
        while i < len(n.keys) and key >= n.keys[i]:
            i += 1
        promoted, new_child = self._insert(n.children[i], key, value)
        if new_child is None:
            return None, None
        n.keys.insert(i, promoted)
        n.children.insert(i + 1, new_child)
        if len(n.keys) <= self._max_keys():
            return None, None
        return self._split_internal(n)
    def _split_leaf(self, n: Node) -> Tuple[int, Node]:
        """Split an overflowing leaf in two, relink the leaf chain, and
        return the new right leaf's first key as the promoted routing key --
        a copy, since the key must still live in the leaf for search() to
        find its value."""
        mid = len(n.keys) // 2
        right = Node(leaf=True)
        right.keys = n.keys[mid:]
        right.values = n.values[mid:]
        right.next = n.next
        n.keys = n.keys[:mid]
        n.values = n.values[:mid]
        n.next = right
        return right.keys[0], right
    def _split_internal(self, n: Node) -> Tuple[int, Node]:
        """Split an overflowing internal node. The middle key is removed and
        promoted, not copied -- an internal node holds only routing keys,
        never a value, so there's nothing left behind worth keeping."""
        mid = len(n.keys) // 2
        promoted = n.keys[mid]
        right = Node(leaf=False)
        right.keys = n.keys[mid + 1:]
        right.children = n.children[mid + 1:]
        n.keys = n.keys[:mid]
        n.children = n.children[:mid + 1]
        return promoted, right
    def range_scan(self, start: int, end: int) -> List[int]:
        """Return every value with start <= key <= end. Descends to the
        leftmost qualifying leaf exactly once, then walks the linked leaf
        chain -- never re-entering the tree from the root. This is the
        entire reason B+tree leaves are linked and plain B-tree leaves
        aren't."""
        n = self.root
        while not n.leaf:
            i = 0
            while i < len(n.keys) and start >= n.keys[i]:
                i += 1
            n = n.children[i]
        result: List[int] = []
        while n is not None:
            for i, k in enumerate(n.keys):
                if k > end:
                    return result
                if k >= start:
                    result.append(n.values[i])
            n = n.next
        return result
    def height(self) -> int:
        """Number of levels from root to leaf, inclusive."""
        n = self.root
        h = 1
        while not n.leaf:
            h += 1
            n = n.children[0]
        return h

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
// Node is a single B+tree node. Internal nodes hold routing keys and child
// pointers only; leaf nodes hold keys and their associated values, plus a
// pointer to the next leaf for range scans.
class Node<K, V> {
    List<K> keys = new ArrayList<>();
    List<Node<K, V>> children = new ArrayList<>(); // internal nodes only
    List<V> values = new ArrayList<>(); // leaf nodes only, parallel to keys
    boolean leaf;
    Node<K, V> next; // leaf chain pointer, leaf nodes only
    Node(boolean leaf) {
        this.leaf = leaf;
    }
}
// BPlusTree is an in-memory B+tree. order is the maximum number of children
// an internal node may have (== max keys + 1); real databases size this to
// the number of keys that fit in one disk page -- typically hundreds.
public class BPlusTree<K extends Comparable<K>, V> {
    // SplitResult holds the outcome of a node split: the promoted key and
    // the new right sibling.
    private static class SplitResult<K, V> {
        final K promotedKey;
        final Node<K, V> newRight;
        SplitResult(K promotedKey, Node<K, V> newRight) {
            this.promotedKey = promotedKey;
            this.newRight = newRight;
        }
    }
    Node<K, V> root;
    private final int order;
    public BPlusTree(int order) {
        if (order < 3) {
            throw new IllegalArgumentException("order must be >= 3");
        }
        this.order = order;
        this.root = new Node<>(true);
    }
    private int maxKeys() {
        return order - 1;
    }
    // search returns the value stored for key, or Optional.empty() if not found.
    public Optional<V> search(K key) {
        Node<K, V> n = root;
        while (!n.leaf) {
            int i = 0;
            while (i < n.keys.size() && key.compareTo(n.keys.get(i)) >= 0) {
                i++;
            }
            n = n.children.get(i);
        }
        for (int i = 0; i < n.keys.size(); i++) {
            if (n.keys.get(i).equals(key)) {
                return Optional.of(n.values.get(i));
            }
        }
        return Optional.empty();
    }
    // insert adds or updates key/value, splitting nodes top-down as needed
    // to keep every node within maxKeys() keys.
    public void insert(K key, V value) {
        SplitResult<K, V> result = insert(root, key, value);
        if (result != null) {
            Node<K, V> newRoot = new Node<>(false);
            newRoot.keys.add(result.promotedKey);
            newRoot.children.add(root);
            newRoot.children.add(result.newRight);
            root = newRoot;
        }
    }
    // insert recurses to the correct leaf, inserts, and splits any node
    // (leaf or internal) that overflows maxKeys(). It returns a promoted
    // key and new right sibling when the current node split, or null
    // otherwise.
    private SplitResult<K, V> insert(Node<K, V> n, K key, V value) {
        if (n.leaf) {
            int i = 0;
            while (i < n.keys.size() && n.keys.get(i).compareTo(key) < 0) {
                i++;
            }
            if (i < n.keys.size() && n.keys.get(i).equals(key)) {
                n.values.set(i, value); // update existing key in place
                return null;
            }
            n.keys.add(i, key);
            n.values.add(i, value);
            if (n.keys.size() <= maxKeys()) {
                return null;
            }
            return splitLeaf(n);
        }
        int i = 0;
        while (i < n.keys.size() && key.compareTo(n.keys.get(i)) >= 0) {
            i++;
        }
        SplitResult<K, V> childSplit = insert(n.children.get(i), key, value);
        if (childSplit == null) {
            return null;
        }
        n.keys.add(i, childSplit.promotedKey);
        n.children.add(i + 1, childSplit.newRight);
        if (n.keys.size() <= maxKeys()) {
            return null;
        }
        return splitInternal(n);
    }
    // splitLeaf splits an overflowing leaf into two, relinks the leaf chain,
    // and returns the first key of the new right leaf as the promoted
    // routing key -- a copy, since the key must still live in the leaf for
    // search() to find its value.
    private SplitResult<K, V> splitLeaf(Node<K, V> n) {
        int mid = n.keys.size() / 2;
        Node<K, V> right = new Node<>(true);
        right.keys.addAll(n.keys.subList(mid, n.keys.size()));
        right.values.addAll(n.values.subList(mid, n.values.size()));
        right.next = n.next;
        n.keys = new ArrayList<>(n.keys.subList(0, mid));
        n.values = new ArrayList<>(n.values.subList(0, mid));
        n.next = right;
        return new SplitResult<>(right.keys.get(0), right);
    }
    // splitInternal splits an overflowing internal node. The middle key is
    // removed and promoted, not copied -- an internal node holds only
    // routing keys, never a value, so there is nothing left behind worth
    // keeping.
    private SplitResult<K, V> splitInternal(Node<K, V> n) {
        int mid = n.keys.size() / 2;
        K promoted = n.keys.get(mid);
        Node<K, V> right = new Node<>(false);
        right.keys.addAll(n.keys.subList(mid + 1, n.keys.size()));
        right.children.addAll(n.children.subList(mid + 1, n.children.size()));
        n.keys = new ArrayList<>(n.keys.subList(0, mid));
        n.children = new ArrayList<>(n.children.subList(0, mid + 1));
        return new SplitResult<>(promoted, right);
    }
    // rangeScan returns every value with start <= key <= end. It descends to
    // the leftmost qualifying leaf exactly once, then walks the linked leaf
    // chain -- never re-entering the tree from the root. This is the entire
    // reason B+tree leaves are linked and plain B-tree leaves aren't.
    public List<V> rangeScan(K start, K end) {
        Node<K, V> n = root;
        while (!n.leaf) {
            int i = 0;
            while (i < n.keys.size() && start.compareTo(n.keys.get(i)) >= 0) {
                i++;
            }
            n = n.children.get(i);
        }
        List<V> result = new ArrayList<>();
        while (n != null) {
            for (int i = 0; i < n.keys.size(); i++) {
                K k = n.keys.get(i);
                if (k.compareTo(end) > 0) {
                    return result;
                }
                if (k.compareTo(start) >= 0) {
                    result.add(n.values.get(i));
                }
            }
            n = n.next;
        }
        return result;
    }
    // height reports the number of levels from root to leaf, inclusive.
    public int height() {
        Node<K, V> n = root;
        int h = 1;
        while (!n.leaf) {
            h++;
            n = n.children.get(0);
        }
        return h;
    }
}

from btree import BPlusTree
def test_search_found_and_missing() -> None:
    t = BPlusTree(order=4)
    for k in [10, 20, 5, 6, 12, 30, 7, 17]:
        t.insert(k, k * 100)
    for k in [10, 20, 5, 6, 12, 30, 7, 17]:
        v, ok = t.search(k)
        assert ok and v == k * 100, f"search({k}) = {v}, {ok}"
    v, ok = t.search(999)
    assert not ok, "search(999) should not be found"
def test_update_existing_key() -> None:
    t = BPlusTree(order=4)
    t.insert(1, 100)
    t.insert(1, 999)  # same key again -- must update in place, not duplicate
    v, ok = t.search(1)
    assert ok and v == 999, f"update failed: {v}, {ok}"
def test_split_sequence_order_4() -> None:
    # order=4 -> max 3 keys/node, deliberately tiny so splits happen
    # constantly. The final shape is exactly the split-then-promote-then-
    # split-again scenario the stepper in this file walks through by hand.
    t = BPlusTree(order=4)
    seq = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    for k in seq:
        t.insert(k, k)
    for k in seq:
        v, ok = t.search(k)
        assert ok and v == k, f"search({k}) after full sequence: {v}, {ok}"
    assert t.height() > 1, "tree should have split into multiple levels"
    assert t.root.keys == [70] and len(t.root.children) == 2, (
        f"expected root [70] with 2 children, got keys={t.root.keys} "
        f"children={len(t.root.children)}"
    )
def test_range_scan() -> None:
    t = BPlusTree(order=4)
    for k in range(1, 21):
        t.insert(k, k * 10)
    result = t.range_scan(5, 12)
    assert result == [k * 10 for k in range(5, 13)], result
def test_range_scan_no_match() -> None:
    t = BPlusTree(order=4)
    for k in [1, 2, 3]:
        t.insert(k, k)
    assert t.range_scan(100, 200) == []

import java.util.Arrays;
import java.util.List;
import java.util.Optional;
public class BPlusTreeTest {
    public static void main(String[] args) {
        testSearchFoundAndMissing();
        testUpdateExistingKey();
        testSplitSequenceOrder4();
        testRangeScan();
        testRangeScanNoMatch();
        System.out.println("All tests passed");
    }
    static void testSearchFoundAndMissing() {
        BPlusTree<Integer, Integer> t = new BPlusTree<>(4);
        int[] keys = {10, 20, 5, 6, 12, 30, 7, 17};
        for (int k : keys) {
            t.insert(k, k * 100);
        }
        for (int k : keys) {
            Optional<Integer> v = t.search(k);
            if (v.isEmpty() || v.get() != k * 100) {
                throw new AssertionError("search(" + k + ") = " + v);
            }
        }
        if (t.search(999).isPresent()) {
            throw new AssertionError("search(999) should not be found");
        }
    }
    static void testUpdateExistingKey() {
        BPlusTree<Integer, Integer> t = new BPlusTree<>(4);
        t.insert(1, 100);
        t.insert(1, 999); // same key again -- must update in place, not insert a duplicate
        Optional<Integer> v = t.search(1);
        if (v.isEmpty() || v.get() != 999) {
            throw new AssertionError("update failed: " + v);
        }
    }
    // testSplitSequenceOrder4 inserts 10,20,...,100 into an order-4 tree
    // (max 3 keys per node) -- deliberately tiny so splits happen
    // constantly. The final shape is exactly the split-then-promote-then-
    // split-again scenario the stepper in this file walks through by hand.
    static void testSplitSequenceOrder4() {
        BPlusTree<Integer, Integer> t = new BPlusTree<>(4);
        int[] seq = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        for (int k : seq) {
            t.insert(k, k);
        }
        for (int k : seq) {
            Optional<Integer> v = t.search(k);
            if (v.isEmpty() || v.get() != k) {
                throw new AssertionError("search(" + k + ") after full sequence = " + v);
            }
        }
        if (t.height() <= 1) {
            throw new AssertionError("tree should have split into multiple levels");
        }
        if (!t.root.keys.equals(List.of(70)) || t.root.children.size() != 2) {
            throw new AssertionError("expected root [70] with 2 children after this exact sequence, got keys="
                    + t.root.keys + " children=" + t.root.children.size());
        }
    }
    static void testRangeScan() {
        BPlusTree<Integer, Integer> t = new BPlusTree<>(4);
        for (int k = 1; k <= 20; k++) {
            t.insert(k, k * 10);
        }
        List<Integer> got = t.rangeScan(5, 12);
        List<Integer> want = Arrays.asList(50, 60, 70, 80, 90, 100, 110, 120);
        if (!got.equals(want)) {
            throw new AssertionError("rangeScan(5,12) = " + got + ", want " + want);
        }
    }
    static void testRangeScanNoMatch() {
        BPlusTree<Integer, Integer> t = new BPlusTree<>(4);
        for (int k : new int[]{1, 2, 3}) {
            t.insert(k, k);
        }
        List<Integer> got = t.rangeScan(100, 200);
        if (!got.isEmpty()) {
            throw new AssertionError("expected empty, got " + got);
        }
    }
}