User tried to modify node that is frozen.
Index node in the tree.
An index node contains pairs of keys and references to other nodes (node ids, which are integers). The other nodes may be either index nodes or leaf nodes.
Find all children whose key is in the range.
minkey and maxkey are inclusive. Note that a child might be returned even if not all of its keys are in the range, just some of them. Also, we consider potential keys here, not actual keys. We have no way to retrieve the children to check which keys they actually have, so instead we return which keys might have the desired keys, and the caller can go look at those.
Return key for the child that contains key.
Leaf node in the tree.
A leaf node contains key/value pairs (both strings), and has no children.
Find pairs whose key is in desired range.
minkey and maxkey are inclusive.
Abstract base class for index and leaf nodes.
A node may be initialized with a list of (key, value) pairs. For leaf nodes, the values are the actual values. For index nodes, they are references to other nodes.
A node can be indexed using keys, and give the corresponding value. Setting key/value pairs cannot be done using indexing. However, key in node does work, as does iteration over a key’s values. len(node) returns the number if keys.
Two nodes compare equal if they have the same key/value pairs. The node ids do not need to match.
Nodes can be modified, bt only if the frozen property is false. If it is set to true, any attempt at modifying the node causes the FrozenNode exception to be raised.
Insert a key/value pair into the right place in a node.
Find pairs whose key is in desired range.
minkey and maxkey are inclusive.
We take into account that for index nodes, a child’s key really represents a range of keys, from the key up to (but not including) the next child’s key. The last child’s key represents a range up to infinity.
Thus we return the first child, if its key lies between minkey and maxkey, and the last child, if its key is at most maxkey.
Return smallest key in the node.
Return keys in the node, sorted.
Remove a key from the node.
Raise KeyError if key does not exist in node.
Remove keys given a range of indexes into pairs.
lo and hi are inclusive.
Return value in the node, in same order as keys.