Skip to content

Releases: RobbieMcKinstry/sdtrie

Initial Radix Trie Release

12 Nov 14:47
Compare
Choose a tag to compare
Pre-release

This release provides the first pass at a radix tree. The code has a sizable passing integration test, implying that it's likely correct.

Some observations about this release:

  • Lookup performs in O(n) time, verified empirically (where n is the number of keys in the tree.
  • The radix trie can handle around 8000-9000 lookups per minute.
  • The trie uses vastly more memory than the size of the strings it contains. Adding 1.7MB of data produces a trie of size 27 MB.

Future Plans:

  • Add a fuzzer
  • Add a DOT output so the trie can be visualized
  • Improve lookup performance from O(n) to O(lg n)
  • Extend this type to allow other values to be stored on the leaves beyond IDs.
  • Improve memory usage
  • Benchmark and graph both memory usage and runtime