Skip to content
A fast in-memory prefix tree that uses uint64 for keys and allows for duplicate entries.
Go
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
LICENSE
README.md
celltree.go
celltree_test.go

README.md

celltree

GoDoc

A fast in-memory prefix tree that uses uint64 for keys, interface{} for data, and allows for duplicate entries.

Getting Started

Installing

To start using celltree, install Go and run go get:

$ go get -u github.com/tidwall/celltree

Example

var 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

Performance

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

Contact

Josh Baker @tidwall

License

celltree source code is available under the MIT License.

You can’t perform that action at this time.