system.indexes.btree module

B+-tree index implementation with node splitting.

class system.indexes.btree.NoSplit

Bases: PutInfo

Result of a put that did not cause a node to split.

class system.indexes.btree.SplitHappens(left_node: BPlusTree.AbstractNode, right_node: BPlusTree.AbstractNode, pivot: Key)

Bases: PutInfo, Generic

Result of a put that caused a node to split into two.

Wraps the two nodes produced by the split and the pivot key that separates them: left_node holds the keys below the pivot, right_node holds the keys at or above it, and pivot is the separating key propagated up to the parent.

left_node: BPlusTree.AbstractNode

right_node: BPlusTree.AbstractNode

pivot: Key

class system.indexes.btree.BPlusTree(inner_capacity: int = 3, leaf_capacity: int = 4)

Bases: AbstractBTree, Generic

A simple, educational B+tree implementation with support for inserts, splits, as well as point, and range queries. Deletes and merges are not supported. Note that this outside class is simply a wrapper around the actual tree which is held as a reference. So this is a Decorator Design Pattern. The only purpose of the outside wrapper is to keep track of basic capacity parameters AND handle the root node in case of a split.

class AbstractNode(capacity: int)

Bases: AbstractBTree, ABC

Abstract node API of a b+-tree. An abstract node can be either implemented as an inner node or a leaf node. An abstract node and all its subclasses are valid B-Tree Indexes.

abstractmethod put(key: Key, value: Value) → None | PutInfo

Insert the given key and value into the abstract node.

Parameters:

• key – The key to insert.

• value – The value to insert.

Returns:

A PutInfo instance: NoSplit if the pair fit without splitting, or SplitHappens (wrapping the two new nodes and the pivot) if this insertion caused a split.

abstractmethod split() → SplitHappens[Key]

Split-operation for nodes. Splits the keys and values of this node into two nodes.

Returns:

A SplitHappens instance wrapping the left node, the right node, and the new pivot if a split occurred

abstractmethod get(key: Key) → Iterator[Value]

See PointQueryMixIn.get().

abstractmethod get_all_in_range(min_key: Key, max_key: Key) → Iterator[Value]

See RangeQueryMixIn.get_all_in_range().

abstractmethod is_full() → bool

Returns true if the node is full, otherwise false.

abstractmethod size() → int

Returns the number of keys in the subtree.

abstractmethod dot(s: str) → str

Returns a string representation of the node in dot format.

abstractmethod consistency_check() → None

Check if the node is consistent, i.e., all keys are sorted and the number of children is correct.

delete(key: Key, value: Value = None) → None

See Index.delete().

Not supported for b+-tree nodes.

flush(key: Key | None = None) → None

See Index.flush().

Not supported for b+-tree nodes.

abstractmethod show() → None

Shows the content of the index.

class Inner(capacity: int, keys: list[Key], children: list[BPlusTree.AbstractNode])

Bases: AbstractNode

Inner node of a b+-tree. Inner nodes have keys and references to children subtrees, i.e. Nodes or Leaves. Inner Nodes in inself are an index structure.

show() → None

Shows the content of the inner node.

split() → SplitHappens[Key]

Split-operation for inner nodes. Splits the keys and children of this node into two inner nodes plus pivot. Note: No re-use of this instance, we are creating two new Inner-instances.

Returns:

A SplitHappens wrapping the left node, the right node, and the new pivot.

put(key: Key, value: Value) → PutInfo

Insert the given key and value into the inner node.

Parameters:

• key – The key to insert.

• value – The value to insert.

Returns:

A PutInfo instance: NoSplit if the pair fit without splitting, or SplitHappens (wrapping the two new nodes and the pivot) if this insertion caused a split.

get(key: Key) → Iterator[Value]

Finds the appropriate subtree to search for the given key and calls get on that subtree. :param key: The key to search for.

get_all_in_range(min_key: Key, max_key: Key) → Iterator[Value]

Finds the appropriate subtree to search for the given key range and calls get_all_in_range on that subtree.

Parameters:

• min_key – The minimum key to search for.

• max_key – The maximum key to search for.

Returns:

A list of values for all keys in the given range.

is_full() → bool

Returns true if the node is full, otherwise false.

size() → int

Returns the number of keys mapped by this subtree.

Returns:

The sum of the number of keys of this subtree.

dot(s: str) → str

Returns a string representation of the inner node in dot format.

consistency_check() → None

Check if this node is consistent, i.e., all keys are sorted and the number of children is correct, etc.

class Leaf(capacity: int, keys: list[Key] | None = None, values: list[Value] | None = None)

Bases: AbstractNode

Leaf node of a b-tree. Leaf nodes have keys and values.

show() → None

Shows the content of the leaf.

split() → SplitHappens[Key]

Split-operation for leaf nodes. Splits the keys and values of this Leaf into two Leaves. Note: No re-use of this instance, we are creating two new Leaf instances.

Returns:

A SplitHappens wrapping the left leaf, the right leaf, and the new pivot.

put(key: Key, value: Value) → PutInfo

Insert the given key and value into the leaf.

Parameters:

• key – The key to insert.

• value – The value to insert.

Returns:

A PutInfo instance: NoSplit if the pair fit without splitting, or SplitHappens (wrapping the two new nodes and the pivot) if this insertion caused a split.

get(key: Key) → Iterator[Value]

Returns the value for the given key if it exists. :param key: The key to search for.

get_all_in_range(min_key: Key, max_key: Key) → Iterator[Value]

Returns a list of values for all keys in the given range. Implements ISAM-like sequential scanning.

Parameters:

• min_key – The minimum key to search for.

• max_key – The maximum key to search for.

Returns:

A list of values for all keys in the given range.

is_full()

Returns true if the node is full, otherwise false.

size() → int

Returns the number of keys mapped by this leaf, i.e., the number of keys in the leaf.

dot(s: str) → str

Returns a string representation of the leaf node in dot format.

consistency_check() → None

Check if this node is consistent, i.e., all keys are sorted and the number of children is correct, etc.

class CountingLeaf

Bases: AbstractNode

A leaf node that does not store values but counts the number of put-calls.

put(key: Key, value: Value) → PutInfo | None

See Index.put().

Does not store the value; only increments the counter of put calls.

split() → SplitHappens[Key]

Counting leaves are never split: always raises NotImplementedError.

get(key: Key) → Iterator[Value]

See PointQueryMixIn.get().

Not supported for counting leaves: always raises NotImplementedError.

get_all_in_range(min_key: Key, max_key: Key) → Iterator[Value]

See RangeQueryMixIn.get_all_in_range().

Not supported for counting leaves: always raises NotImplementedError.

is_full() → bool

Not supported for counting leaves: always raises NotImplementedError.

size() → int

See Index.size().

Returns the number of put calls counted so far.

dot(s: str) → str

Returns a string representation of the leaf node in dot format.

consistency_check() → None

Not supported for counting leaves: always raises NotImplementedError.

show() → None

See Index.show().

Prints the number of put calls counted so far.

put(key: Key, value: Value) → None | PutInfo

See Index.put().

Copies the value before storing it and, if the root node split, replaces the root with a new inner node holding the two halves and the separating pivot.

get(key: Key) → Iterator[Value]

See PointQueryMixIn.get().

Note: this simple B+tree does not support multiple values for the same key.

get_all_in_range(min_key: Key, max_key: Key) → Iterator[Value]

See RangeQueryMixIn.get_all_in_range().

delete(key: Key, value: Value = None)

See Index.delete().

Not implemented in this simple B+tree.

flush(key: Key | None = None) → None

See Index.flush().

Not implemented in this simple B+tree.

bulkload(input_data: Iterator[tuple[Key, Value]])

Bulkloads the given list of key->value mappings into the index. Not overridden in this simple B+tree.

size() → int

See Index.size().

consistency_check() → None

Check if the B+tree is consistent, i.e., all keys are sorted and the number of children is correct.

show() → None

Displays the B+tree using graphviz.

convert_to_counting_leaf_tree() → None

Keeps all inner nodes but replaces all leaves with CountingLeafs.