A fast in-memory prefix tree that uses uint64 for keys, interface{} for data, and allows for duplicate entries.
To start using celltree, install Go and run go get:
$ go get -u github.com/tidwall/celltreevar tr celltree.Tree
tr.Insert(10, nil)
tr.Insert(5, nil)
tr.Insert(31, nil)
tr.Insert(16, nil)
tr.Insert(9, nil)
tr.Scan(func(cell uint64, data interface{}) bool {
println(cell)
return true
})Outputs:
5
9
10
16
31
Single threaded performance comparing this package to google/btree.
$ go test
-- celltree --
insert 1,048,576 ops in 318ms 3,296,579/sec
scan 100 ops in 824ms 121/sec
range 1,048,576 ops in 144ms 7,245,252/sec
remove 1,048,576 ops in 244ms 4,281,322/sec
memory 40,567,280 bytes 38/entry
-- btree --
insert 1,048,576 ops in 1003ms 1,044,876/sec
scan 100 ops in 1195ms 83/sec
range 1,048,576 ops in 443ms 2,364,467/sec
remove 1,048,576 ops in 1198ms 874,723/sec
memory 49,034,992 bytes 46/entry
These benchmarks were run on a MacBook Pro 15" 2.8 GHz Intel Core i7 using Go 1.10
Josh Baker @tidwall
celltree source code is available under the MIT License.