Skip to content
A generic patricia trie (also called radix tree) implemented in Go (Golang)
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
patricia Add Clone() method Jan 17, 2019
.gitignore Add more tests and a couple of new methods Jan 17, 2014
LICENSE First somehow working version Jan 16, 2014 README: Remove the Bitdeli badge Jul 4, 2017


Documentation: GoDoc
Test Coverage: Coverage Status


A generic patricia trie (also called radix tree) implemented in Go (Golang).

The patricia trie as implemented in this library enables fast visiting of items in some particular ways:

  1. visit all items saved in the tree,
  2. visit all items matching particular prefix (visit subtree), or
  3. given a string, visit all items matching some prefix of that string.

[]byte type is used for keys, interface{} for values.

Trie is not thread safe. Synchronize the access yourself.

State of the Project

Apparently some people are using this, so the API should not change often. Any ideas on how to make the library better are still welcome.

More (unit) testing would be cool as well...


Import the package from GitHub first.

import ""

You can as well use thingie:

import ""

Then you can start having fun.

printItem := func(prefix patricia.Prefix, item patricia.Item) error {
	fmt.Printf("%q: %v\n", prefix, item)
	return nil

// Create a new default trie (using the default parameter values).
trie := NewTrie()

// Create a new custom trie.
trie := NewTrie(MaxPrefixPerNode(16), MaxChildrenPerSparseNode(10))

// Insert some items.
trie.Insert(Prefix("Pepa Novak"), 1)
trie.Insert(Prefix("Pepa Sindelar"), 2)
trie.Insert(Prefix("Karel Macha"), 3)
trie.Insert(Prefix("Karel Hynek Macha"), 4)

// Just check if some things are present in the tree.
key := Prefix("Pepa Novak")
fmt.Printf("%q present? %v\n", key, trie.Match(key))
// "Pepa Novak" present? true
key = Prefix("Karel")
fmt.Printf("Anybody called %q here? %v\n", key, trie.MatchSubtree(key))
// Anybody called "Karel" here? true

// Walk the tree in alphabetical order.
// "Karel Hynek Macha": 4
// "Karel Macha": 3
// "Pepa Novak": 1
// "Pepa Sindelar": 2

// Walk a subtree.
trie.VisitSubtree(Prefix("Pepa"), printItem)
// "Pepa Novak": 1
// "Pepa Sindelar": 2

// Modify an item, then fetch it from the tree.
trie.Set(Prefix("Karel Hynek Macha"), 10)
key = Prefix("Karel Hynek Macha")
fmt.Printf("%q: %v\n", key, trie.Get(key))
// "Karel Hynek Macha": 10

// Walk prefixes.
prefix := Prefix("Karel Hynek Macha je kouzelnik")
trie.VisitPrefixes(prefix, printItem)
// "Karel Hynek Macha": 10

// Delete some items.
trie.Delete(Prefix("Pepa Novak"))
trie.Delete(Prefix("Karel Macha"))

// Walk again.
// "Karel Hynek Macha": 10
// "Pepa Sindelar": 2

// Delete a subtree.

// Print what is left.
// "Karel Hynek Macha": 10


MIT, check the LICENSE file.

Gittip Badge

You can’t perform that action at this time.