ibtree

ibtree is an implementation of generic immutable balanced binary trees in Go. This packages provides generic immutable AVL trees.

Why

Mutable btrees are all well and good, but sometimes you need a btree that can be updated and accessed at the same time in multiple different goroutines. Sure, you could invent a complicated locking scheme using ever more finegrained and deadlock prone locking schemes. There are libraries out there that provide that. This is not one of them.

Instead, this library provides immutable btrees. Any operation that would mutate the tree will instead make copies of any nodes that would be changed and return a new tree. The new tree and the old tree will share unchanged nodes. This library also provides bulk insert and delete operations that minimize the amount of node copying that happens under the hood.

Installation

go get https://github.com/VictorLowther/ibtree

Example

package main
import github.com/VictorLowther/ibtree
import fmt

func main() {
    tree := ibtree.New[int](func(a,b int) {return a < b})
    tree = tree.Insert(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    tree = tree.Reverse()
    iter := tree.Iterate(nil, nil)
    for iter.Next() {
        fmt.Println(iter.Item())
    }
}

Benchmarks:

On a Macbook Pro M1 Max:

% go test -bench .
goos: darwin
goarch: arm64
pkg: github.com/VictorLowther/ibtree
BenchmarkInsertIntSeqNocow-10           	 6181240	       224.5 ns/op	      32 B/op	       1 allocs/op
BenchmarkInsertIntSeqCow-10             	 3437576	       387.5 ns/op	      89 B/op	       1 allocs/op
BenchmarkInsertIntSeqReverseNocow-10    	 5719492	       233.2 ns/op	      32 B/op	       1 allocs/op
BenchmarkInsertIntSeqReverseCow-10      	 3429450	       381.8 ns/op	      89 B/op	       1 allocs/op
BenchmarkInsertIntRandCow-10            	 1542794	       837.5 ns/op	      66 B/op	       1 allocs/op
BenchmarkDeleteIntSeq-10                	 4191504	       295.0 ns/op	      32 B/op	       1 allocs/op
BenchmarkDeleteIntRand-10               	 1610540	       839.3 ns/op	      49 B/op	       1 allocs/op
BenchmarkInsertStringSeq-10             	 7300251	       193.7 ns/op	      48 B/op	       1 allocs/op
BenchmarkInsertStringRand-10            	 1592608	       926.7 ns/op	      48 B/op	       1 allocs/op
BenchmarkDeleteStringSeq-10             	 3384838	       348.7 ns/op	      48 B/op	       1 allocs/op
BenchmarkDeleteStringRand-10            	 1000000	        1066 ns/op	      73 B/op	       1 allocs/op
BenchmarkIntIterAll-10                  	203883426	       5.866 ns/op	       0 B/op	       0 allocs/op
BenchmarkFetch/btree_size_16-10         	100000000	       11.15 ns/op	       0 B/op	       0 allocs/op
BenchmarkFetch/map_size_16-10           	177492420	       6.677 ns/op
BenchmarkFetch/btree_size_256-10        	68811284	       17.10 ns/op	       0 B/op	       0 allocs/op
BenchmarkFetch/map_size_256-10          	140613560	       7.681 ns/op
BenchmarkFetch/btree_size_65536-10      	35249148	       34.58 ns/op	       0 B/op	       0 allocs/op
BenchmarkFetch/map_size_65536-10        	60658269	       19.38 ns/op
BenchmarkFetch/btree_size_16777216-10   	16971104	       70.74 ns/op	       0 B/op	       0 allocs/op
BenchmarkFetch/map_size_16777216-10     	21009904	       60.14 ns/op
PASS
ok  	github.com/VictorLowther/ibtree	80.137s

Interestingly enough, the slowdown on the random benchmarks appears to be due to branch misprediction rather than tree rebalancing performing more work — dealing with sorted data actually performs more rebalancing than random data.

GitHub

View Github