Searching for a key is done the same way. The only difference is that the entire search string must be matched and the children of the matches are not considered. Accumulating results in an efficient way can be tricky. The most common approaches of recursion or using collections to build the results can perform poorly in C# (due to our lack of tail call optimization) or generate excessive garbage.

Radix Tree

A radix tree is a variant of a trie where some nodes are merged together. If a node has a child and that child doesn't have any children of its own, then it can be merged with its parent. Instead of storing a character, each node in the tree can contain a string. For example, if a radix tree contained only the keys 'alternate' and 'alter', it would have three nodes: the root node, a child with a key of 'alter' and it would have a single child of 'nate'. Later, if 'alt' was stored, then there would be nodes of 'alt', 'ter' and 'nate'. When insertions and removals are done from the graph, nodes are merged and split as needed.

This allows fewer nodes to be created and maintained, but requires more complicated logic for inserts and removals from the tree and requires string processing at each node which sometimes requires special consideration in C#.

Other Trie Variants

Many of the other trie variants utilize approaches to further compact the keys. This makes them perform well and require less storage when checking if a key exists, but makes them ill suited for searching by prefix. Some variants are the HAMT, the hash tree, and the patricia trie. The first two act more like dictionaries than a trie (as the keys are hashed). I have found conflicting information on the patricia trie, but as described in its original paper it does not store whole keys and can only be used to check for the existence of complete matches.

Typical Alternatives to Tries

The most common alternative for implementing a prefix lookup is a naive enumeration over a list. Typically this could be done with a LINQ Where query passing in a lambda to check if each key element StartsWith a given search text. This can perform well for smaller collections, but quickly becomes a hindrance with millions of items.

Database queries using a 'LIKE' clause are also quite common. While the latency can be quite bad compared to an in-memory collection and depends on networking stability, it usually has an advantage of simplifying concurrency concerns and ensuring the client always has access to the most recent data. For smaller projects its not uncommon for instances to contain a local database file to cache lookups (such as SQLite).

Another option is to use a dedicated text searching tool or system, such as ElasticSearch. These can perform well and can provide advanced searching capabilities (such as transforming the search text and analyzing it before searching, as well as fuzzy matches), but they can be quite complicated to properly setup and maintain, and still induce additional latency and networking concerns.

What's Currently Included In This Project

In TrieHard.Abstractions is an interface IPrefixLookup. All implementations in this project implement that interface. An IPrefixLookup has an indexer and can be enumerated for key value pairs like a Dictionary, but also exposes Search and SearchValues methods which take a key prefix and return enumerables of KeyValuePairs or the generic value results respectively.

SimpleTrie

This was implemented as a reference C# trie based on various articles that suggest using Dictionaries at each node to store keys and children. A number of nuget packages can be found that implement a similar approach.

RadixTree

This is similar to a trie, but key values that don't branch can be combined. When keys are longer and highly unique, then this approach can perform well. This particular implementation was tuned to reduce recursion and can can be modified by a single thread while reads are going on concurrently.

Indirect Trie

This trie uses readonly structs stored in arrays to represent nodes. The structs do not directly reference each other, instead referencing bucket and array index locations where connected nodes are stored instead. Nodes only store links to their parent, their first child and to their first in-order sibling. It has similar concurrency characteristics to the RadixTree.

Unsafe Trie

This Trie uses unmanaged memory as storage for nodes and utilizes Spans and inline arrays to reduce allocations during operations. It offers a few specialized APIs beyond the IPrefixLookup methods, such as a non allocation search operation that gives access to keys as UTF8 spans.

The string keys are converted to UTF8 bytes before they are stored and when retrieved. Performance is better when using the UTF8 specific search methods or when retrieving values.

It lives up to its name, as 0.1.3 this trie has a memory leak issue (related to memory management of native memory during search operations) and its use outside of experimentation is not recommended at this time.

Flat Trie

This Trie backs all of the node data in arrays and takes advantage of lower allocation patterns similar to the Compact Trie, such as the usage of structs and array pooling. Additional Key data is stored with each node to optimize for read heavy workloads. Several APIs unique to this trie also exist (such as paginating through page data).

rm.Trie

I found this library on nuget/github. It was one of the few trie libraries that had a reasonable number of downloads, was up to date, and contained functional code. An IPrefixLookup wrapper was implemented to include it as a comparison.

ListPrefixLookup (NaiveList)

Many devs will use LINQ on a List/Array to perform a StartsWith search to implement an autocomplete instead of using a specialized collection. This performs well for small lists, but can become a hindrance as the size increases. Lists are also not thread safe, which makes modifying them at runtime awkward.

SQLiteLookup

SQLite is a very common single file database and is often used within applications to store read-heavy data. Using a database is a common way to query data such as for an autocomplete or typeahead. Included is an IPrefixLookup wrapper that creates an in-memory SQLite connection and creates a table to contain keys and value indexes.

Searches are done using SQL queries. A real database would likely perform worse (involving networking and data retrieval). An advantage of this approach is that the queries involved are simple, and SQLite will handle concurrency issues for the developer (though it does not perform well when undergoing sustained concurrent write pressure). I don't recommend reusing this SQLiteLookup, as its not intended for use outside of these contrived benchmarks and it wasn't made to support updates.

Nuget Package PrefixLookup

Also included is a project for building a Nuget package. Currently this utilizes a wrapper around the RadixTree implementation. This package should be considered experimental at this time and plans are to target the most recent LTS of .NET

Benchmarks

Benchmarks are contained in TrieHard.Benchmarks. Most of the tests are contained in the LookupBenchmark.cs, but there are a few tests in CompatBench.cs which are specific to the UnsafeTrie.

Creating a lookup with a million sequential entries (strings for keys and values)

dotnet run -c Release --filter *Create*

Getting a value by key

dotnet run -c Release --filter *Get*

A plain list struggles a bit at one million records.

Setting a value by key

dotnet run -c Release --filter *Set*

Searching Key Value Pairs by prefix (100 results enumerated)

dotnet run -c Release --filter *SearchKVP*

Searching Values by prefix (100 results enumerated)

dotnet run -c Release --filter *SearchValues*

UTF8 Methods

dotnet run -c Release --filter *Utf8*

Several of these implementations store UTF8 data in the graph instead of strings or character arrays. These implementations have additional methods that are not part of the IPrefixLookup interface that should perform better when using UTF8 byte data instead of C# strings when searching or setting values.

Note on the Radix Tree results. It has search logic targeting nodes with 10 children, which is a legitimate improvement, but makes it perform unfairly on these benchmarks over sequential keys. On other child node counts its results are very similar to the Unsafe Trie.

Memory Usage of 5 Million Keys

The 'paths' keys look like URL subpaths and follow a format of /customer/{id}/entity/{id}/ with the ID being a sequential number. This is generated with the project TrieHard.ConsoleTest. The results for memory usage do not follow benchmarking best practices, and do not account for differences in steady state, the ordering of keys inserted, or other factors, so consider these as casual results.

It is enough to see that trie implementations become somewhat bloated with even moderate length keys (and that SQLite has a very compact in-memory format). For sequential integer keys, the unsafe trie takes less memory than putting the keys into a List (a side effect of storing the keys as UTF8).

Only the Radix Tree maintains decent size characteristics with longer keys and repeated patterns.