TinyTricia is a space-optimized Patricia Trie for storing keys with up to 256 bits (optionally: key/value pairs).

Low memory consumption.

As an example, for 16.78 million (2^24) 48-bit keys (IPv4 + port number), TinyTricia requires only between 134 MB (best case) and 268 MB (worst case) of memory space.

• Storage of values can be disabled using the keysOnly parameter (__init__).

• Nodes do not contain a link to their parent.

• An optimized Compact Mode is activated if keys are <= 57 bits and no values are stored.

• Compact Mode: Max 536,870,912 keys (2^29) in the best case; half in the worst case.

• Regular Mode: Max 268,435,455 keys (2^28-1) in the best case; half in the worst case.

• Best case: For each key there is another key where only the rightmost bit differs.

• Worst case: For no key there is another key where only the rightmost bit differs.

• Only keys with a fixed length are stored, thus only leaf nodes will contain a full key.
• Ints are used for the keys, thus the algorithm will require a little-endian machine to work correctly.

pip3 install .

This project is licensed under the MIT License.