A trie (pronounced either “tree” or “try”) is a data structure typically used to store a set of strings in a way that allows looking up by prefix efficiently - i.e. unlike a hashmap where the keys are randomly ordered - this makes it a reasonable choice for an autocompletion system. A possible advantage over binary trees is that the keys are not stored in full in each node - so if you have a large number of strings which often have overlapping prefixes (e.g. “cat”, “cats”, “catastrophe”) then you may be able to save memory.

I looked around the internet for examples of tries written in Golang, but many make use of Go “maps” within the nodes; maps are a complex data structure, and this feels like cheating! More precisely, it is harder to understand the size/speed of the map and whether this outweighs the space savings of using a trie in the first place. Similarly with Go slices - slices require a pointer and two ints, so while using them might be idiomatic, each one costs 16 extra bytes (on 64 bit systems), which seems like it might not be necessary.

Therefore, I wrote my own Golang trie to understand more of the details.

De la Briandais tries

Grabbing my copy of TAOCP vol 3 from the dusty shelf, I looked up tries and implemented the linked-list version, which apparently is known as a “de la Briandais” trie.

I made an assumption that we would break strings into UTF-8 runes. My original node definition was as follows:

type node struct {
	next      *node // 8 bytes (on 64-bit systems)
	children  *node // 8 bytes
	character rune  // 4 bytes
}

Initially I used a separate node with a sentinel value rune(-1) to indicate that a node ended a key, but later I added a “value” field and used the zero value. This allowed mapping keys to integers, but means that you cannot store the zero value against a key - a boolean field can be added to avoid this limitation.

Lookup performance

I made no attempt to keep the linked-list in any particular order.

If there are a large number of keys starting with the same prefix (e.g. if we are storing random binary bytes, or a large number of Chinese words with an “alphabet” of around 3000 characters) then the lookup may need to scan through a large number of nodes and this may not be an effective data structure. However for small alphabets like English text or UK postcodes, there can be only a relatively small number of nodes at each level.

My arbitrary benchmarks on random alphanumeric strings suggest this trie outperforms some of the competitors in both lookup time and memory usage, but it is worth testing on your data set to know for sure.

Memory usage

When benchmarking, I was surprised to find that each node seemed to allocate 32 bytes of memory, rather than 20 bytes. I ruled out struct alignment issues, and realised instead that Golang allocates small objects in fixed size classes, so the memory usage gets rounded up to a power of two.

I think it might be possible to reduce this by storing all nodes in a single slice (which would be 8 byte aligned, so each node would use 24 bytes), but I have not yet tried this.

Expanding strings to runes means that each character takes four bytes - for English text, often each character requires only one byte when stored within a string (ignoring the 16 byte string header). It is quite possible that a map or binary tree or another data structure will use less memory than this trie on your data set (but changing the node definition to use bytes would have no effect due to the allocation issue above).

Conclusion

Tries are a relatively basic data structure, but many implementations found in the wild have unexpected properties when you look under the hood! Writing my own trie has already taught me more about how Go handles memory, and I may experiment some more with different implementations to explore the trade-offs.

Assume nothing - always benchmark, and ensure your choice of data structure is appropriate for your specific use case.