Individual nodes¶
-
exception
larch.nodes.
FrozenNode
(node)¶ User tried to modify node that is frozen.
-
class
larch.nodes.
IndexNode
(node_id, keys, values)¶ 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_children_in_range
(minkey, maxkey)¶ Find all children whose key is in the range.
minkey
andmaxkey
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.
-
find_key_for_child_containing
(key)¶ Return key for the child that contains
key
.
-
-
class
larch.nodes.
LeafNode
(node_id, keys, values)¶ Leaf node in the tree.
A leaf node contains key/value pairs (both strings), and has no children.
-
find_keys_in_range
(minkey, maxkey)¶ Find pairs whose key is in desired range.
minkey
andmaxkey
are inclusive.
-
-
class
larch.nodes.
Node
(node_id, keys, values)¶ 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 theFrozenNode
exception to be raised.-
add
(key, value)¶ Insert a key/value pair into the right place in a node.
-
find_potential_range
(minkey, maxkey)¶ Find pairs whose key is in desired range.
minkey
andmaxkey
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
andmaxkey
, and the last child, if its key is at mostmaxkey
.
-
first_key
()¶ Return smallest key in the node.
-
keys
()¶ Return keys in the node, sorted.
-
remove
(key)¶ Remove a key from the node.
Raise KeyError if key does not exist in node.
-
remove_index_range
(lo, hi)¶ Remove keys given a range of indexes into pairs.
lo and hi are inclusive.
-
values
()¶ Return value in the node, in same order as keys.
-