Class BPlusTreeMap

python/bplustree/bplus_tree.py:33–637

B+ Tree implementation with Python dict-like API. A B+ tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in O(log n). Unlike B trees, all values are stored in leaf nodes, which are linked together

class BPlusTreeMap:
    """B+ Tree implementation with Python dict-like API.

    A B+ tree is a self-balancing tree data structure that maintains sorted data
    and allows searches, sequential access, insertions, and deletions in O(log n).
    Unlike B trees, all values are stored in leaf nodes, which are linked together
    for efficient range queries.

    Attributes:
        capacity: Maximum number of keys per node.
        root: The root node of the tree.
        leaves: The leftmost leaf node (head of linked list).

    Example:
        >>> tree = BPlusTreeMap(capacity=32)
        >>> tree[1] = "one"
        >>> tree[2] = "two"
        >>> print(tree[1])
        one
        >>> for key, value in tree.items():
        ...     print(f"{key}: {value}")
        1: one
        2: two
    """

    def __init__(self, capacity: int = DEFAULT_CAPACITY) -> None:
        """Create a B+ tree with specified node capacity.

        Args:
            capacity: Maximum number of keys per node (minimum 4).

        Raises:
            InvalidCapacityError: If capacity is less than 4.
        """
        if capacity < MIN_CAPACITY:
            raise InvalidCapacityError(
                f"Capacity must be at least {MIN_CAPACITY} to maintain B+ tree invariants"
            )
        self.capacity = capacity
        self._rightmost_leaf_cache: Optional[LeafNode] = None

        original = LeafNode(self.capacity)
        self.leaves: LeafNode = original
        self.root: Node = original

    @classmethod
    def from_sorted_items(
        cls, items, capacity: int = DEFAULT_CAPACITY
    ) -> "BPlusTreeMap":
        """Bulk load from sorted key-value pairs for 3-5x faster construction.

        Args:
            items: Iterable of (key, value) pairs that MUST be sorted by key.
            capacity: Node capacity (minimum 4).

        Returns:
            BPlusTreeMap instance with loaded data.