datrie: a memory lean Trie for Python built on libdatrie

A Trie for Python that trades speed for memory

The problem datrie solves is narrow and real: a Python dict is a good general purpose map, but it stores every key as a separate object, and for a large vocabulary that overhead adds up. datrie stores keys in a shared character tree instead, so a hundred thousand words that share prefixes cost a fraction of the memory.

The package is a Cython extension. The build configuration lists Cython as a build requirement, and the setup script cythonizes src/datrie.pyx, src/cdatrie.pxd and src/stdio_ext.pxd against a set of C sources compiled from the bundled libdatrie directory. The repository carries a .gitmodules entry, so libdatrie comes in as a submodule rather than as a pip dependency, which means a source install has to fetch it. The library itself is a C implementation of the datrie structure, and the Python layer is a thin wrapper that exposes the mapping interface on top of it.

That layering is what gives the package its character. It is not a pure Python implementation with an optional accelerator. The trie is always the C one, and the Python side is Cython, which is why the package is classified under Programming Language :: Cython and why installing it means compiling something.

The README frames the package as a Trie for Python 2.x and 3.x, and the package classifiers list CPython from 3.9 through 3.13, with the project marked as Development Status :: 4 - Beta.

The character range you declare is not checked at runtime

This is the constraint that matters most in practice, and the documentation is unusually blunt about it. A warning in the guide says that for efficiency you must define the allowed character range or ranges when creating the trie, and that datrie does not check whether keys are in the allowed ranges at runtime, so be careful. Invalid keys are fine at lookup time, but the values will not be stored correctly for such keys.

So the failure is silent. A key containing a character outside your declared alphabet will appear to work, return a value on a read, and quietly fail to persist one on a write. There is no exception to catch and no log line to grep for.

The way the range is given is through the constructor, and the example uses the lowercase ASCII letters.

    >>> import string
    >>> import datrie
    >>> trie = datrie.Trie(string.ascii_lowercase)

Once that is done the trie behaves like a dict with unicode keys and arbitrary Python values, plus the prefix operations that motivated the package. Keys must be unicode strings, which the guide states when it introduces the assignment examples.

The practical advice is to derive the alphabet from the data rather than from habit. If your keys are lower case ASCII, string.ascii_lowercase is right. If they carry accents, digits, hyphens or Cyrillic, the declared range has to cover them, and a range built by hand from a fixed alphabet risks exactly the silent failure the warning describes.

prefixes, suffixes and longest prefix lookups

Once the alphabet is declared, the package is a dict with extra queries attached, and the extra queries are the reason to use it.

Prefix enumeration comes in two flavours, a list and an iterator. The example shows prefixes of a word, which returns the stored keys that are prefixes of the input string.

    >>> trie[u'foo'] = 5
    >>> trie[u'foobar'] = 10
    >>> trie[u'bar'] = 'bar value'
    >>> trie.setdefault(u'foobar', 15)
    10
    >>> trie.prefixes(u'foobarbaz')
    [u'foo', u'foobar']

The setdefault call returns the existing value, 10, rather than the 15 it was given, which is standard dict behaviour, so the mapping interface is complete enough that a trie can be dropped in where a dict was expected. The suffix methods work in the opposite direction, returning the tails of stored keys that begin with a given prefix.

The longest prefix lookup is the one with an edge case worth knowing. Calling it with a string that has no matching key raises a KeyError, and the documentation shows that behaviour explicitly.

    >>> trie.longest_prefix(u'gaz')
    KeyError: u'gaz'
    >>> trie.longest_prefix(u'gaz', default=u'vasia')
    u'vasia'

There is also a longest_prefix_item variant that returns the key and value pair, and a has_keys_with_prefix method that answers the yes or no question without building the list. The guide demonstrates it as a case sensitive check, so has_keys_with_prefix with an uppercase argument returns False against lowercase keys.

Trie and BaseTrie: values or speed, not both

There are two Trie classes in the package, and the choice between them is the first decision an adopter makes.

datrie.Trie stores any Python object as a value. datrie.BaseTrie is described as slightly faster and using less memory, but it can store only integer numbers in the range from -2147483648 to 2147483647. The guide puts it plainly: if you do not need values, or integer values are acceptable, use BaseTrie.

    import datrie
    import string
    trie = datrie.BaseTrie(string.ascii_lowercase)

The restriction is a 32 bit signed integer range, and the reason is structural rather than a policy choice. The C library underneath stores values in fixed width slots, so a general Python object has to be marshalled into that slot and a pointer kept alongside it. BaseTrie skips that indirection.

The custom traversal classes follow the same split. If you use datrie.BaseTrie then custom traversal needs datrie.BaseState and datrie.BaseIterator instead of datrie.State and datrie.Iterator. Mixing the two families is a runtime error rather than a silent wrong result, which is at least a clean failure mode.

For most workloads the practical difference between the two classes is small, because the memory win comes mostly from the shared prefix structure rather than from the value type. Where you are holding tens of millions of keys with integer payloads, BaseTrie is the one to benchmark first.

State and Iterator for traversal the built-in methods do not cover

The built-in methods cover the common cases. When they do not fit, the package exposes the underlying traversal so you can write your own.

The pattern is a two step one. You create a State from the trie, walk it along a key, then create an Iterator over that state and advance it.

    >>> state = datrie.State(trie)
    >>> state.walk(u'foo')
    >>> it = datrie.Iterator(state)
    >>> while it.next():
    ...     print(it.key())
    ...     print(it.data))
    o
    5
    obar
    10

The example walks the state to the position of the key foo and then iterates what lives below that node, printing the remaining key fragment and the value. The output shows the key parts as o and obar rather than the full words, which tells you the iterator reports the remainder relative to where the walk stopped.

This is the extension point for anyone who needs something between the built-in list returning methods and a raw C call. The cost is that you are now working with a stateful cursor rather than a function, so the traversal has to be driven correctly, and the walk call is a prerequisite that has to be understood rather than guessed. The documentation gives the example and leaves the rest to the reader.

Installing from pip or building the Cython extension yourself

The documented installation is a single pip command.

    pip install datrie

That path assumes a wheel is available for your platform and Python version, which is what the cibuildwheel configuration in pyproject.toml is for, with a build frontend of build[uv] and a SETUPTOOLS_SCM_PRETEND_VERSION environment variable passed through to the build.

Building from source is the interesting case. The pyproject build system requires setuptools of at least 40.8.0, wheel and Cython, and setup.py compiles the C files from the libdatrie directory and links them as a datrie library alongside the cythonized extension modules. The libdatrie directory is a git submodule, so a fresh clone that does not pull submodules will fail at the compile step rather than at install time.

The repository also carries a tox.ini, a tox-bench.ini, a dev-requirements.txt and a bench directory, so the project supports both a test run and a separate benchmark run as tox environments. A continuous_integration directory and an update_c.sh script sit alongside them, the latter presumably regenerating the C sources from the upstream library.

The package version in setup.py is 0.8.3, and the repository has no GitHub releases, so pip is the distribution channel rather than a build artefact you fetch yourself.

The measured trade: less memory, slower lookups

The performance section is the most useful part of the guide because the author is candid about the method. The numbers come from measuring datrie.Trie against a Python dict with 100k unique unicode words, English and Russian, as keys and the number 1 as values, and the text describes the results as unscientific tests.

On memory, the trie uses about 5M for 100k words where the dict uses about 22M under those conditions. That is the case for the package.

On speed, the trie implementation is 2 to 6 times slower than a dict on __getitem__, and the benchmark table gives the raw figures. For Python 3.3 the dict does 7.050M ops/sec against 2.755M ops/sec for the trie, with comparable ratios on 2.6, 2.7 and 3.2. These are old numbers on old interpreters, so treat them as an order of magnitude rather than a measurement on your machine.

The prefix operations are the interesting part, because they are what a dict cannot do at all. The table shows trie.iter_prefixes at 0.759M ops/sec on hits and 1.538M on misses, and trie.has_keys_with_prefix at 1.896M on hits and 2.590M on misses. A miss being faster than a hit is a good sign for autocomplete workloads, where most queries find nothing.

Enumerating everything under a prefix is a different story, and the guide explains why: it is mostly limited by the overall result count, and a lot of time is spent decoding strings from utf_32_le into Python unicode. The numbers fall as the result set grows, from trie.values at 96.456K ops/sec for a short result list down to 503.392K for an average result length of 1.4. The fix, the text says, is a decoding change for a future version, so today the cost of pulling many matches is the weak point.

Where a Trie is the wrong tool

The clearest case against datrie is a workload that does mostly single key lookups. The benchmarks put the trie at two to six times slower than a dict on __getitem__, so a mapping that is read far more often than it is enumerated is paying a memory bill for a capability it never uses. In that situation a plain dict uses less memory anyway, and the trie is pure overhead.

The second case is dynamic key sets with an unpredictable alphabet. The package requires the character range to be fixed when the trie is created, and it does not validate keys at runtime. A system whose keys are free text entered by users, with punctuation and symbols arriving without warning, will hit the silent storage failure the warning describes. That is a data corruption risk rather than a performance concern, and it is the reason to think twice before putting arbitrary user input into the key position.

The third is deployment. This is a compiled extension with a C dependency bundled as a submodule, and pip install needs a matching wheel or a working compiler toolchain including Cython. On a locked down platform, or on an architecture with no published wheel, you are compiling from source, and you own the result.

On the comparison, the honest framing is that a dict is not slower for the operations it supports, and a pure Python trie package gives you prefix queries without the C dependency and without the compile step. datrie is the choice when the memory figure is the binding constraint, not when the prefix query is.

The licence is LGPL-2.1-or-later, which carries obligations if you distribute a modified version of the library itself. That is a question for someone qualified to advise on it, and this review does not interpret the terms. The last push to the repository was on 2026-06-01, and with no GitHub releases published, you should check the state of the master branch and the CHANGES.rst file before depending on a specific version.

Editorial conclusion

datrie fits a memory constrained job that holds a large word list and needs prefix queries, such as autocomplete over a fixed vocabulary, and it does not fit a general purpose replacement for a dict because lookups are several times slower. Before you adopt it, measure the memory pressure on your own key set, and check that every key falls inside the character range you pass to datrie.Trie, since keys outside it are accepted at lookup time and stored incorrectly.

Frequently asked questions

Official sources

1. Issues
2. License: LGPL-2.1
3. Project website
4. pytries/datrie on GitHub
5. README