I'm not familiar with Python, but would a C extension be the best way to implement a data structure like this, that requires high performance? Or is it possible to write efficient enough code in Python?
When algorithms matter, you do get a lot of performance out of a better algorithm. But I actually recently wrote an admittedly not production ready trie extension in C and it was about five lines of SWIG to use it from python.