An immutable radix tree implementation in Golang

Overview

go-immutable-radix CircleCI

Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

As a radix tree, it provides the following:

  • O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
  • Minimum / Maximum value lookups
  • Ordered iteration

A tree supports using a transaction to batch multiple updates (insert, delete) in a more efficient manner than performing each operation one at a time.

For a mutable variant, see go-radix.

Documentation

The full documentation is available on Godoc.

Example

Below is a simple example of usage

// Create a tree
r := iradix.New()
r, _, _ = r.Insert([]byte("foo"), 1)
r, _, _ = r.Insert([]byte("bar"), 2)
r, _, _ = r.Insert([]byte("foobar"), 2)

// Find the longest prefix match
m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
if string(m) != "foo" {
    panic("should be foo")
}

Here is an example of performing a range scan of the keys.

// Create a tree
r := iradix.New()
r, _, _ = r.Insert([]byte("001"), 1)
r, _, _ = r.Insert([]byte("002"), 2)
r, _, _ = r.Insert([]byte("005"), 5)
r, _, _ = r.Insert([]byte("010"), 10)
r, _, _ = r.Insert([]byte("100"), 10)

// Range scan over the keys that sort lexicographically between [003, 050)
it := r.Root().Iterator()
it.SeekLowerBound([]byte("003"))
for key, _, ok := it.Next(); ok; key, _, ok = it.Next() {
  if key >= "050" {
      break
  }
  fmt.Println(key)
}
// Output:
//  005
//  010
Comments
  • SeekLowerBound not working correctly

    SeekLowerBound not working correctly

    I was trying to replace our custom Seek behavior in my fork with SeekLowerBound described in here https://github.com/hashicorp/go-immutable-radix/pull/29#issuecomment-627942830 but hit some issues.

    First thing I discovered was that an empty key (root) confuses the seeker. Tried to fix this in https://github.com/hashicorp/go-immutable-radix/commit/30c53379998b3a3fc23b26088546e455d5cd25f4

    But then I discovered some more cases that behave weirdly. Added tests for them in https://github.com/hashicorp/go-immutable-radix/commit/5bed3aa0fa9f25207cbbe490ebc97ce18aeae6d2

        --- FAIL: TestIterateLowerBound/case015 (0.00s)
            iradix_test.go:1712: keys=[ aaa bbb] search=aa want=[aaa bbb]
            iradix_test.go:1730: mis-match: key=aa
                  got=[]
                  want=[aaa bbb]
        --- FAIL: TestIterateLowerBound/case016 (0.00s)
            iradix_test.go:1712: keys=[ aaa bbb] search=aaab want=[bbb]
            iradix_test.go:1730: mis-match: key=aaab
                  got=[]
                  want=[bbb]
        --- PASS: TestIterateLowerBound/case017 (0.00s)
            iradix_test.go:1712: keys=[ aaa bbb] search= want=[ aaa bbb]
        --- FAIL: TestIterateLowerBound/case018 (0.00s)
            iradix_test.go:1712: keys=[a aa bbb] search=aa want=[aa bbb]
            iradix_test.go:1730: mis-match: key=aa
                  got=[bbb]
                  want=[aa bbb]
        --- FAIL: TestIterateLowerBound/case019 (0.00s)
            iradix_test.go:1712: keys=[a aaa bbb] search=aa want=[aaa bbb]
            iradix_test.go:1730: mis-match: key=aa
                  got=[bbb]
                  want=[aaa bbb]
    

    @banks @thaJeztah

    opened by tonistiigi 9
  • Fix SeekLowerBound where tree contains keys that are prefixes of each other

    Fix SeekLowerBound where tree contains keys that are prefixes of each other

    Fixes #37 #28.

    This seems like a trivial case to miss however it stemmed from some confusion (on my part) about whether iradix was ever intended to support keys that were prefixes. It's a long story and I don't even recall exactly why I thought this was the case now given that every other operation on iradix supports this and most even include this case in their test examples. We even had it in the README example!

    But some combination of:

    • I was working at the time on a related radix tree that did have the assumption of null-terminated keys
    • hashicorp/go-memdb always null terminates even for simpler string indexes

    Anyway the fix is simple and the examples now pass.

    In addition the fuzz test (which explicitly used the null-termination trick to never trigger this assuming it was necessary in general) now passes without null terminating keys every time I've run it.

    opened by banks 8
  • Added Clone method to Txn to create an independent copy of a transaction

    Added Clone method to Txn to create an independent copy of a transaction

    This PR adds a Clone method to Txn.

    A subsequent PR will add similar functionality to Txn in memdb (txn.Snapshot returning a read-only transaction), dependent on this one.

    opened by feldgendler 8
  • add regular seek

    add regular seek

    I'm not the original author of this patch, but trying to see if this patch can be upstreamed. BuildKit (https://github.com/moby/buildkit) has been using a fork of this project with this patch applied for the last 3 years; depending on a fork is not "ideal", so I'm opening this pull request to discuss the option of upstreaming this patch (also see the discussion on https://github.com/tonistiigi/go-immutable-radix/pull/1).

    I must admit that I don't have a lot of background around the purpose of this patch, so pinging @tonistiigi to provide more details if needed (also if tests are needed (happy to give you write access to my branch, or apply additional patches))

    opened by thaJeztah 6
  • iradix.go error: cannot use lru (type simplelru.LRUCache) as type *simplelru.LRU in assignment: need type assertion

    iradix.go error: cannot use lru (type simplelru.LRUCache) as type *simplelru.LRU in assignment: need type assertion

    Hi, I'm trying to install hugo, and this package is giving me an error:

    $ go get -v github.com/gohugoio/hugo                                                                                                                        
    github.com/hashicorp/go-immutable-radix                                                                                                                                                   
    # github.com/hashicorp/go-immutable-radix                                                                                                                                                 
    ../../../gocode/src/github.com/hashicorp/go-immutable-radix/iradix.go:139:14: cannot use lru (type simplelru.LRUCache) as type *simplelru.LRU in assignment: need type assertion
    

    I'm using go 1.9.3 on Debian testing amd64.

    opened by nikolas 5
  • Insert returns false even if an element was set

    Insert returns false even if an element was set

    I noticed that Insert method returns true even though a value was set under a given key. Looks like this problem is coming from Txn.insert method which returns bool is used by the Tree's Insert method. The code where a new edge is creating is here

    	// No edge, create one
    	if child == nil {
    		e := edge{
    			label: search[0],
    			node: &Node{
    				mutateCh: make(chan struct{}),
    				leaf: &leafNode{
    					mutateCh: make(chan struct{}),
    					key:      k,
    					val:      v,
    				},
    				prefix: search,
    			},
    		}
    		nc := t.writeNode(n, false)
    		nc.addEdge(e)
    		return nc, nil, false
    	}
    

    You can see that we return false on purpose.

    So I cannot understand if it's a bug or a flaw in the documentation.

    opened by olehgol260 4
  • After using iterator.SeekPrefix, the iterator stop working beyond the current element

    After using iterator.SeekPrefix, the iterator stop working beyond the current element

    func TestSeekPrefix(t *testing.T){
        index := iradix.New()
        index, _ , _ = index.Insert([]byte("aaa"),"aaa")
        index, _ , _ = index.Insert([]byte("bbb"),"bbb")
        index, _ , _ = index.Insert([]byte("ccc"),"ccc")
        index, _ , _ = index.Insert([]byte("ddd"),"ddd")
        index, _ , _ = index.Insert([]byte("eee"),"eee")
        iterator := index.Root().Iterator()
        k,v,got := iterator.Next()
        for got{
            t.Log(k,v)
            k,v,got = iterator.Next()
        }
        iterator.SeekPrefix([]byte("c"))
        k,v,got = iterator.Next()
        for got{
            t.Log("SF: ", k,v)
            k,v,got = iterator.Next()
        }
    }
    
    opened by asogor 4
  • Fix caching problem

    Fix caching problem

    My understanding is we should cache the newly copied node, otherwise the cache will never be used.

    Run the test TestTest_HugeTxn, with the fix it takes ~7.5 seconds to run, without the fix it takes ~9.4s.

    opened by EasonLiao 4
  • a panic risk of function SeekPrefixWatch in file

    a panic risk of function SeekPrefixWatch in file "iter.go"

    As following code, the variable "search" could be 0-length byte slice. But the last line of following code quote the "search[0]" directly.

    		// Consume the search prefix
    		if len(n.prefix) > len(search) {
    			search = []byte{}
    		} else {
    			search = search[len(n.prefix):]
    		}
    
    		// Otherwise, take the lower bound next edge.
    		idx, lbNode := n.getLowerBoundEdge(search[0])
    
    opened by xpineal 3
  • Go 1.10: iradix_test.go:176: Fatalf format %#v reads arg #2, but call has only 1 arg

    Go 1.10: iradix_test.go:176: Fatalf format %#v reads arg #2, but call has only 1 arg

    59b67882ec612f43b9d4c4fd97cebd507be4b3ee does not pas Go 1.10 unit tests. At least:

     GOPATH=/builddir/build/BUILD/go-immutable-radix-59b67882ec612f43b9d4c4fd97cebd507be4b3ee/_build:/usr/share/gocode
    + go test -buildmode pie -compiler gc -ldflags '-extldflags '\''-Wl,-z,relro  '\'''
    # github.com/hashicorp/go-immutable-radix
    ./iradix_test.go:176: Fatalf format %#v reads arg #2, but call has only 1 arg
    FAIL    github.com/hashicorp/go-immutable-radix [build failed]
    
    opened by nim-nim 2
  • Free notification channels upon overflow

    Free notification channels upon overflow

    This PR clears the notification channels as soon as we enter the overflow state. This is an optimization to allow earlier garbage collection of a large amount of channels.

    opened by dadgar 2
  • v2: use generics to enforce type invariants

    v2: use generics to enforce type invariants

    This PR introduces a v2 of go-immutable-radix, centered on utilizing generics.

    The major version bump is necessary because although the package is now generic, the exported type signatures have changed to be generic; rather than assuming interface{} in places.

    • sets minimum Go version to 1.18
    • module is bumped to github.com/hashicorp/go-immutable-radix/v2
    • CI is swapped from Circle to GitHub Actions
    • Exported types and their methods are now generic
    • minor code lint fixes

    Closes #42 Closes #36

    r := iradix.New[string]() // e.g.
    

    note: if this gets merged, be sure to tag with v2.0.0

    Adding some benchmarks (via this harness). I suspect in practice the performance difference is negligible - the differences here could just be luck with GC going one way or the other.

    Work/go/iradix-bench 24s
    ➜ go run main.go 
    Scenario   Type        Size           V1           V2        Delta      Pct
     insertion byte        1000   1.697583ms   1.140482ms   -557.101µs  -32.82%
     insertion byte       10000  11.958884ms   9.357029ms  -2.601855ms  -21.76%
     insertion byte      100000 105.298741ms 110.699253ms   5.400512ms    5.13%
     insertion byte     1000000 741.490742ms 733.548246ms  -7.942496ms   -1.07%
     insertion employee    1000   1.231465ms   1.193493ms    -37.972µs   -3.08%
     insertion employee   10000  13.319666ms  14.263141ms    943.475µs    7.08%
     insertion employee  100000 110.649808ms  98.866248ms  -11.78356ms  -10.65%
     insertion employee 1000000 748.178939ms 681.968127ms -66.210812ms   -8.85%
     insertion int64       1000    1.33419ms   1.126917ms   -207.273µs  -15.54%
     insertion int64      10000  10.679749ms  10.884198ms    204.449µs    1.91%
     insertion int64     100000 113.991954ms 113.522559ms   -469.395µs   -0.41%
     insertion int64    1000000 754.626542ms 723.907751ms -30.718791ms   -4.07%
     insertion string      1000    993.762µs    559.075µs   -434.687µs  -43.74%
     insertion string     10000   12.36633ms  11.791997ms   -574.333µs   -4.64%
     insertion string    100000  97.246453ms  99.044017ms   1.797564ms    1.85%
     insertion string   1000000 697.957946ms 656.948516ms  -41.00943ms   -5.88%
       iterate byte        1000     17.052µs     12.504µs     -4.548µs  -26.67%
       iterate byte       10000    312.355µs    192.366µs   -119.989µs  -38.41%
       iterate byte      100000   6.272204ms   6.321789ms     49.585µs    0.79%
       iterate byte     1000000  62.505377ms   60.94112ms  -1.564257ms   -2.50%
       iterate employee    1000      10.46µs     12.905µs      2.445µs   23.37%
       iterate employee   10000    292.166µs    306.554µs     14.388µs    4.92%
       iterate employee  100000   5.937789ms   6.243939ms     306.15µs    5.16%
       iterate employee 1000000  64.140997ms   80.17852ms  16.037523ms   25.00%
       iterate int64       1000     16.511µs     14.368µs     -2.143µs  -12.98%
       iterate int64      10000     262.46µs    126.381µs   -136.079µs  -51.85%
       iterate int64     100000   6.378087ms   6.439172ms     61.085µs    0.96%
       iterate int64    1000000  60.678524ms  60.375718ms   -302.806µs   -0.50%
       iterate string      1000      7.134µs      6.763µs       -371ns   -5.20%
       iterate string     10000     194.05µs     105.27µs     -88.78µs  -45.75%
       iterate string    100000   6.041565ms   6.171173ms    129.608µs    2.15%
       iterate string   1000000  64.068893ms  64.387791ms    318.898µs    0.50%
    
    opened by shoenig 0
  • Marshal

    Marshal

    Would it be possible to add Marshal/Unmarshal functions? I'm creating very large tries and it burns my lap to generate them 🔥 I'd like to save them to disk so I don't have to regen again.

    Would that be possible?

    opened by blacktop 5
  • Add a copyright / notice file

    Add a copyright / notice file

    This project doesn't appear to include any copyright information or a NOTICE file. Can you add one? This is desired to comply with the open source license conditions.

    opened by davidmateos 0
  • Add fuzzy prefixing tree walking

    Add fuzzy prefixing tree walking

    This allows trees to be walked with non-exact prefixes. The Levenshtein distance is used to determine how far the input can deviate, which is highly useful for tasks such as autocompletion or suggestions where the spelling is often not quite correct

    opened by mish15 2
Releases(v1.3.1)
Owner
HashiCorp
Consistent workflows to provision, secure, connect, and run any infrastructure for any application.
HashiCorp
A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

null 0 Nov 24, 2021
Golang implementation of Radix trees

go-radix Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Armon Dadgar 752 Sep 26, 2022
Exp-tree: go library for parsing expression tree

Vinshop expression tree Exp-tree is go library for parsing expression tree Installation go get -u github.com/vinshop/exp-tree Quick start Format Expre

VinShop 6 May 11, 2022
gtreap is an immutable treap implementation in the Go Language

gtreap gtreap is an immutable treap implementation in the Go Language Overview gtreap implements an immutable treap data structure in golang. By treap

Steve Yen 84 May 17, 2022
A radix sorting library for Go (golang)

zermelo A radix sorting library for Go. Trade memory for speed! import "github.com/shawnsmithdev/zermelo" func foo(large []uint64) zermelo.Sort(l

Shawn Smith 48 Jul 30, 2022
Adaptive Radix Trees implemented in Go

An Adaptive Radix Tree Implementation in Go This library provides a Go implementation of the Adaptive Radix Tree (ART). Features: Lookup performance s

Pavel Larkin 246 Sep 16, 2022
A generic Go library for implementations of tries (radix trees), state commitments and proofs of inclusion

trie.go Go library for implementations of tries (radix trees), state commitments and proof of inclusion for large data sets. It implements a generic 2

IOTA 5 Aug 3, 2022
Go-merkle - Merkle tree implementation in Golang

go-merkle go-merkle implements a simple merkle tree in Golang. It allows to obta

atomixwap 2 Aug 8, 2022
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 377 Sep 24, 2022
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 28 Aug 22, 2022
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Yasushi Saito 18 Apr 25, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 224 Sep 15, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 209 Sep 22, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 4 Mar 7, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

A.Samet İleri 15 Jul 1, 2022
Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Arun Shaji 3 Oct 6, 2021
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Arthur Abeilice 0 May 17, 2022
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

web_developer 1 Oct 9, 2021
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022