B-tree и B+ tree

<?php

declare(strict_types=1);

/**
 * Minimal B-tree node for teaching purposes.
 * Real implementations store nodes on disk and manage page I/O.
 */
final class BTreeNode
{
    /** @var list<int> */
    public array $keys = [];

    /** @var list<BTreeNode> */
    public array $children = [];

    public function __construct(public bool $isLeaf = true) {}

    public function isFull(int $order): bool
    {
        return count($this->keys) === $order - 1;
    }
}

final class BTree
{
    public BTreeNode $root;

    public function __construct(public readonly int $order = 5)
    {
        $this->root = new BTreeNode(isLeaf: true);
    }

    /** Search for a key; returns node + index if found, null otherwise. */
    public function search(int $key, ?BTreeNode $node = null): ?array
    {
        $node ??= $this->root;
        $i = 0;
        while ($i < count($node->keys) && $key > $node->keys[$i]) {
            $i++;
        }

        if ($i < count($node->keys) && $node->keys[$i] === $key) {
            return ['node' => $node, 'index' => $i];
        }

        if ($node->isLeaf) {
            return null;
        }

        return $this->search($key, $node->children[$i]);
    }

    public function insert(int $key): void
    {
        $root = $this->root;

        // If root is full, grow height by 1
        if ($root->isFull($this->order)) {
            $newRoot = new BTreeNode(isLeaf: false);
            $newRoot->children[] = $root;
            $this->splitChild($newRoot, 0);
            $this->root = $newRoot;
            $this->insertNonFull($newRoot, $key);
        } else {
            $this->insertNonFull($root, $key);
        }
    }

    private function insertNonFull(BTreeNode $node, int $key): void
    {
        $i = count($node->keys) - 1;

        if ($node->isLeaf) {
            // Shift keys right and insert
            while ($i >= 0 && $key < $node->keys[$i]) {
                $node->keys[$i + 1] = $node->keys[$i];
                $i--;
            }
            $node->keys[$i + 1] = $key;
            return;
        }

        // Find child to descend into
        while ($i >= 0 && $key < $node->keys[$i]) {
            $i--;
        }
        $i++;

        if ($node->children[$i]->isFull($this->order)) {
            $this->splitChild($node, $i);
            if ($key > $node->keys[$i]) {
                $i++;
            }
        }
        $this->insertNonFull($node->children[$i], $key);
    }

    private function splitChild(BTreeNode $parent, int $idx): void
    {
        $order = $this->order;
        $full = $parent->children[$idx];
        $mid = intdiv($order - 1, 2);

        $newNode = new BTreeNode(isLeaf: $full->isLeaf);
        $newNode->keys = array_slice($full->keys, $mid + 1);
        if (!$full->isLeaf) {
            $newNode->children = array_slice($full->children, $mid + 1);
            $full->children = array_slice($full->children, 0, $mid + 1);
        }

        // Promote middle key to parent
        $promoted = $full->keys[$mid];
        $full->keys = array_slice($full->keys, 0, $mid);

        array_splice($parent->keys, $idx, 0, [$promoted]);
        array_splice($parent->children, $idx + 1, 0, [$newNode]);
    }
}

package btree

// Order is the maximum number of children per node.
// A node can hold up to Order-1 keys.
const Order = 5

// Node is a B-tree node.
type Node struct {
	Keys     []int
	Children []*Node
	IsLeaf   bool
}

// IsFull reports whether the node has no room for new keys.
func (n *Node) IsFull() bool { return len(n.Keys) == Order-1 }

// Tree wraps the root pointer.
type Tree struct{ Root *Node }

// New returns an empty tree.
func New() *Tree { return &Tree{Root: &Node{IsLeaf: true}} }

// Search returns the node containing key and the index, or nil.
func (t *Tree) Search(key int) (*Node, int, bool) {
	return search(t.Root, key)
}

func search(n *Node, key int) (*Node, int, bool) {
	i := 0
	for i < len(n.Keys) && key > n.Keys[i] {
		i++
	}
	if i < len(n.Keys) && n.Keys[i] == key {
		return n, i, true
	}
	if n.IsLeaf {
		return nil, 0, false
	}
	return search(n.Children[i], key)
}

// Insert adds a key; splits full nodes on the way down.
func (t *Tree) Insert(key int) {
	root := t.Root
	if root.IsFull() {
		newRoot := &Node{IsLeaf: false, Children: []*Node{root}}
		t.splitChild(newRoot, 0)
		t.Root = newRoot
		t.insertNonFull(newRoot, key)
		return
	}
	t.insertNonFull(root, key)
}

func (t *Tree) insertNonFull(n *Node, key int) {
	i := len(n.Keys) - 1
	if n.IsLeaf {
		n.Keys = append(n.Keys, 0)
		for i >= 0 && key < n.Keys[i] {
			n.Keys[i+1] = n.Keys[i]
			i--
		}
		n.Keys[i+1] = key
		return
	}

	for i >= 0 && key < n.Keys[i] {
		i--
	}
	i++
	if n.Children[i].IsFull() {
		t.splitChild(n, i)
		if key > n.Keys[i] {
			i++
		}
	}
	t.insertNonFull(n.Children[i], key)
}

func (t *Tree) splitChild(parent *Node, idx int) {
	full := parent.Children[idx]
	mid := (Order - 1) / 2

	newNode := &Node{IsLeaf: full.IsLeaf}
	newNode.Keys = append(newNode.Keys, full.Keys[mid+1:]...)
	if !full.IsLeaf {
		newNode.Children = append(newNode.Children, full.Children[mid+1:]...)
		full.Children = full.Children[:mid+1]
	}

	promoted := full.Keys[mid]
	full.Keys = full.Keys[:mid]

	parent.Keys = append(parent.Keys, 0)
	copy(parent.Keys[idx+1:], parent.Keys[idx:])
	parent.Keys[idx] = promoted

	parent.Children = append(parent.Children, nil)
	copy(parent.Children[idx+2:], parent.Children[idx+1:])
	parent.Children[idx+1] = newNode
}

using System.Collections.Generic;

// Minimal B-tree for teaching purposes.
// Real implementations store nodes on disk and manage page I/O.
public sealed class BTreeNode(bool isLeaf)
{
    public List<int> Keys { get; } = [];
    public List<BTreeNode> Children { get; } = [];
    public bool IsLeaf { get; set; } = isLeaf;

    public bool IsFull(int order) => Keys.Count == order - 1;
}

public sealed class BTree(int order = 5)
{
    public int Order { get; } = order;
    public BTreeNode Root { get; private set; } = new(isLeaf: true);

    // Search returns the node holding the key and its index, or null.
    public (BTreeNode Node, int Index)? Search(int key)
    {
        var node = Root;
        while (true)
        {
            var i = 0;
            while (i < node.Keys.Count && key > node.Keys[i])
            {
                i++;
            }

            if (i < node.Keys.Count && node.Keys[i] == key)
            {
                return (node, i);
            }

            if (node.IsLeaf)
            {
                return null;
            }

            node = node.Children[i];
        }
    }

    // Insert adds a key, splitting full nodes on the way down.
    public void Insert(int key)
    {
        var root = Root;
        if (root.IsFull(Order))
        {
            var newRoot = new BTreeNode(isLeaf: false);
            newRoot.Children.Add(root);
            SplitChild(newRoot, 0);
            Root = newRoot;
            InsertNonFull(newRoot, key);
            return;
        }

        InsertNonFull(root, key);
    }

    private void InsertNonFull(BTreeNode node, int key)
    {
        var i = node.Keys.Count - 1;

        if (node.IsLeaf)
        {
            // List.Insert keeps keys sorted; O(k) shift inside one page.
            while (i >= 0 && key < node.Keys[i])
            {
                i--;
            }
            node.Keys.Insert(i + 1, key);
            return;
        }

        while (i >= 0 && key < node.Keys[i])
        {
            i--;
        }
        i++;

        if (node.Children[i].IsFull(Order))
        {
            SplitChild(node, i);
            if (key > node.Keys[i])
            {
                i++;
            }
        }

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

    private void SplitChild(BTreeNode parent, int idx)
    {
        var full = parent.Children[idx];
        var mid = (Order - 1) / 2;

        var newNode = new BTreeNode(isLeaf: full.IsLeaf);
        newNode.Keys.AddRange(full.Keys.GetRange(mid + 1, full.Keys.Count - mid - 1));
        if (!full.IsLeaf)
        {
            newNode.Children.AddRange(full.Children.GetRange(mid + 1, full.Children.Count - mid - 1));
            full.Children.RemoveRange(mid + 1, full.Children.Count - mid - 1);
        }

        // Promote the middle key to the parent.
        var promoted = full.Keys[mid];
        full.Keys.RemoveRange(mid, full.Keys.Count - mid);

        parent.Keys.Insert(idx, promoted);
        parent.Children.Insert(idx + 1, newNode);
    }
}

from __future__ import annotations

import bisect

class BTreeNode:
    """Minimal B-tree node for teaching purposes.

    Real implementations store nodes on disk and manage page I/O.
    """

    __slots__ = ("keys", "children", "is_leaf")

    def __init__(self, is_leaf: bool = True) -> None:
        self.keys: list[int] = []
        self.children: list[BTreeNode] = []
        self.is_leaf = is_leaf

    def is_full(self, order: int) -> bool:
        return len(self.keys) == order - 1

class BTree:
    def __init__(self, order: int = 5) -> None:
        self.order = order
        self.root = BTreeNode(is_leaf=True)

    def search(self, key: int) -> tuple[BTreeNode, int] | None:
        """Return (node, index) holding the key, or None."""
        node = self.root
        while True:
            i = bisect.bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                return node, i
            if node.is_leaf:
                return None
            node = node.children[i]

    def insert(self, key: int) -> None:
        """Add a key, splitting full nodes on the way down."""
        root = self.root
        if root.is_full(self.order):
            new_root = BTreeNode(is_leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_non_full(new_root, key)
            return

        self._insert_non_full(root, key)

    def _insert_non_full(self, node: BTreeNode, key: int) -> None:
        i = bisect.bisect_left(node.keys, key)

        if node.is_leaf:
            node.keys.insert(i, key)
            return

        if node.children[i].is_full(self.order):
            self._split_child(node, i)
            if key > node.keys[i]:
                i += 1

        self._insert_non_full(node.children[i], key)

    def _split_child(self, parent: BTreeNode, idx: int) -> None:
        full = parent.children[idx]
        mid = (self.order - 1) // 2

        new_node = BTreeNode(is_leaf=full.is_leaf)
        new_node.keys = full.keys[mid + 1:]
        if not full.is_leaf:
            new_node.children = full.children[mid + 1:]
            full.children = full.children[:mid + 1]

        # Promote the middle key to the parent.
        promoted = full.keys[mid]
        full.keys = full.keys[:mid]

        parent.keys.insert(idx, promoted)
        parent.children.insert(idx + 1, new_node)