74

GitHub - tidwall/celltree: A fast in-memory prefix tree that uses uint64 for key...

 6 years ago
source link: https://github.com/tidwall/celltree
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

README.md

celltree

GoDoc

A fast in-memory prefix tree that uses uint64 for keys, unsafe.Pointer for values, 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, 0)
tr.Insert(5, nil, 0)
tr.Insert(31, nil, 0)
tr.Insert(16, nil, 0)
tr.Insert(9, nil, 0)

tr.Scan(func(cell uint64, value unsafe.Pointer, extra uint64) 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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK