Database Indexes & B-Tree Internals

// Python 3.10+ B+ Tree Node Traversal & Binary Search
import bisect

class BPlusTreeNode:
    def __init__(self, is_leaf: bool = False):
        self.is_leaf = is_leaf
        self.keys = []        # Sorted keys in 16KB page
        self.children = []    # Child page pointers (if internal)
        self.records = []     # Row data / RecordIDs (if leaf)
        self.next = None      # Horizontal linked list pointer

    def find_child(self, key):
        # O(log K) binary search to find child page index
        idx = bisect.bisect_right(self.keys, key)
        return self.children[idx]

    def search(self, key):
        curr = self
        # Descend from Root to Leaf
        while not curr.is_leaf:
            curr = curr.find_child(key)
        
        # Search within leaf page
        idx = bisect.bisect_left(curr.keys, key)
        if idx < len(curr.keys) and curr.keys[idx] == key:
            return curr.records[idx]
        return None

// C++17/20 B+ Tree Node Traversal using std::lower_bound
#include <vector>
#include <algorithm>

struct BPlusNode {
    bool is_leaf;
    std::vector<int> keys;
    std::vector<BPlusNode*> children; // child page pointers
    std::vector<std::string> values;  // row data if leaf
    BPlusNode* next_leaf = nullptr;   // horizontal leaf chain

    BPlusNode* findChild(int key) {
        // upper_bound finds first key strictly greater than target
        auto it = std::upper_bound(keys.begin(), keys.end(), key);
        int idx = std::distance(keys.begin(), it);
        return children[idx];
    }
};

// Java 17+ B+ Tree Node Traversal
import java.util.*;

public class BPlusNode<K extends Comparable<K>, V> {
    boolean isLeaf;
    List<K> keys = new ArrayList<>();
    List<BPlusNode<K, V>> children = new ArrayList<>();
    List<V> records = new ArrayList<>();
    BPlusNode<K, V> next = null;

    public V search(K key) {
        BPlusNode<K, V> curr = this;
        while (!curr.isLeaf) {
            int idx = Collections.binarySearch(curr.keys, key);
            int childIdx = (idx >= 0) ? idx + 1 : -idx - 1;
            curr = curr.children.get(childIdx);
        }
        int idx = Collections.binarySearch(curr.keys, key);
        return (idx >= 0) ? curr.records.get(idx) : null;
    }
}

// Go 1.20+ B+ Tree Node Search
package main

import "sort"

type BPlusNode struct {
    IsLeaf   bool
    Keys     []int
    Children []*BPlusNode
    Records  []string
    Next     *BPlusNode
}

func (n *BPlusNode) Search(key int) string {
    curr := n
    for !curr.IsLeaf {
        idx := sort.Search(len(curr.Keys), func(i int) bool {
            return curr.Keys[i] > key
        })
        curr = curr.Children[idx]
    }
    idx := sort.SearchInts(curr.Keys, key)
    if idx < len(curr.Keys) && curr.Keys[idx] == key {
        return curr.Records[idx]
    }
    return ""
}

// TypeScript B+ Tree Node Search
export class BPlusNode<T> {
    isLeaf: boolean;
    keys: number[] = [];
    children: BPlusNode<T>[] = [];
    records: T[] = [];
    next: BPlusNode<T> | null = null;

    constructor(isLeaf = false) { this.isLeaf = isLeaf; }

    search(key: number): T | null {
        let curr: BPlusNode<T> = this;
        while (!curr.isLeaf) {
            let idx = curr.keys.findIndex(k => k > key);
            if (idx === -1) idx = curr.keys.length;
            curr = curr.children[idx];
        }
        const recIdx = curr.keys.indexOf(key);
        return recIdx !== -1 ? curr.records[recIdx] : null;
    }
}