system.indexes.christmas_tree module

Christmas tree index: a radix trie augmented with buffer-tree-style node buffers.

class system.indexes.christmas_tree.ChristmasTree(children_per_inner_node: int, descriptor: Descriptor, key_mapping: KeyMapping[Key, Value] = None, number_of_inner_node_levels: int = 0, inner_node_factory=<system.indexes.christmas_tree.ChristmasTree.InnerNodeFactory object>, leaf_factory=<system.indexes.christmas_tree.ChristmasTree.LeafFactory object>)

Bases: RadixTrie, Generic

A simple implementation of a Christmas tree data structure.

class BufferedInnerNode(key_mapping: KeyMapping[Key, Value] = None, parent_descriptor: Descriptor = None, max_buffer_size: int = 30)

Bases: InnerNode, Generic

A simple implementation of an inner node in a Christmas tree adding buffer tree-style buffers.

flush_all_buffers()

Flush all buffers in this node and its children.

put(key: Key, value: Value, level: int = 0) → None | PutInfo

See Index.put().

Buffer-tree variant: appends the pair to this node’s in-memory buffer instead of pushing it down immediately; when the buffer is full it is first flushed to the children. The extra level parameter is the current depth of this node in the trie.

get(key: Key, level: int = 0) → Iterator[Value]

See PointQueryMixIn.get().

Buffer-tree variant: yields matching values from this node’s buffer first and then chains in the values returned by the children, so pairs still sitting in the buffer are not missed. The extra level parameter is the current depth of this node in the trie.

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

See Drawable.draw().

In addition to the inner node drawn by the superclass, draws a red candle whose height is proportional to the current fill level of this node’s buffer.

show(indent: str = '') → None

See Index.show().

In addition to the inner node printed by the superclass, prints the key-value pairs currently held in this node’s buffer. The indent parameter is a prefix prepended to every printed line.

class CrystalBallBufferedInnerNode(key_mapping: KeyMapping[Key, Value] = None, parent_descriptor: Descriptor = None, max_buffer_size: int = 30)

Bases: BufferedInnerNode

Add a crystal ball to the buffered inner node.

get(key: Key, level: int = 0) → Iterator[Value]

See ChristmasTree.BufferedInnerNode.get().

Consults the bloom filter first: if the key’s bit is not set the key cannot be present, so an empty iterator is returned without descending; otherwise the buffered-node lookup is delegated to.

put(key: Key, value: Value, level: int = 0) → None | PutInfo

See ChristmasTree.BufferedInnerNode.put().

Additionally records the key in the bloom filter before delegating the insertion to the buffered node.

show(indent: str = '') → None

See ChristmasTree.BufferedInnerNode.show().

Additionally prints the contents of this node’s bloom filter.

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

See ChristmasTree.BufferedInnerNode.draw().

In addition to the buffered node drawn by the superclass, draws a “crystal ball” (a gradient-filled circle) whose opacity reflects how empty the bloom filter still is: the fuller the filter, the less useful it is and the fainter the ball.

class InnerNodeFactory(config: str = 'inner')

Bases: InnerNodeFactory, Generic

A factory for creating nodes in a Christmas tree.

new_instance(key_mapping=None, new_descriptor: Descriptor = None) → RadixTrie.AbstractNode[Key, Value]

Create a new instance of the node.

class LeafFactory

Bases: LeafFactory, Generic

A factory for creating leaf nodes in a Christmas tree.

new_instance(parent_descriptor, left_sibling=None) → RadixTrie.LeafNode[Key, Value]

Create a new instance of the leaf node.

show() → None

Show the Christmas tree.

flush_all_buffers()

Flush the buffer to the children. Makes sense only if the root is a buffered inner node.