README
¶
celltree
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.
Documentation
¶
Index ¶
- type Tree
- func (tr *Tree) Count() int
- func (tr *Tree) Delete(cell uint64, data interface{})
- func (tr *Tree) DeleteWhen(cell uint64, cond func(data interface{}) bool)
- func (tr *Tree) Insert(cell uint64, data interface{})
- func (tr *Tree) InsertOrReplace(cell uint64, data interface{}, ...)
- func (tr *Tree) Range(start uint64, iter func(cell uint64, data interface{}) bool)
- func (tr *Tree) RangeDelete(start, end uint64, ...)
- func (tr *Tree) Scan(iter func(cell uint64, data interface{}) bool)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a uint64 prefix tree
func (*Tree) DeleteWhen ¶
DeleteWhen removes an item from the tree based on it's cell and when the cond func returns true. It will delete at most a maximum of one item.
func (*Tree) Insert ¶
Insert inserts an item into the tree. Items are ordered by it's cell. The extra param is a simple user context value.
func (*Tree) InsertOrReplace ¶
func (tr *Tree) InsertOrReplace( cell uint64, data interface{}, cond func(data interface{}) (newData interface{}, replace bool), )
InsertOrReplace inserts an item into the tree. Items are ordered by it's cell. The extra param is a simple user context value. The cond function is used to allow for replacing an existing cell with a new cell. When the 'replace' return value is set to false, then the original data is inserted. When the 'replace' value is true the existing cell data is replace with newData.
Source Files