github.com/zenhotels/btree-2d/util

Package btree2d implements a 2-dimensional B+tree data structure.


License
Other
Install
go get github.com/zenhotels/btree-2d/util

Documentation

btree-2d GoDoc

Package btree-2d implements a 2-dimensional B+tree data structure.
The B+tree implementation itself has been generated by http://github.com/cznic/b.

We leverage github.com/joeshaw/gengen here to provide a way to generate this data structure for any type you'd like.

This package has been created as an optimization for service and route maps syncing in AstraNet, currently it works fine under heavy loads and reduces the CPU overhead and GC pressure as well.

Getting

$ go get github.com/zenhotels/btree-2d

Do not forget to proceed with gengen. See example.go on how to simplify this process.

Example

A simple example with string and int types, see example.go and the corresponding example_test.go that yields the following:

$ go test

previous:
.
├── 1
│   └── [funcs: 1]  hello world
├── 2
│   └── two
└── 3
    └── three

next:
.
├── 3
│   └── replaced
└── 4
    └── four

added: [3(replaced) 4(four)]
deleted: [1(hello world) 2(two) 3(three)]
bye cruel world

after sync:
.
├── 3
│   └── replaced
└── 4
    └── four

PASS

For a more complex cases check out astranet/route and astranet/service, that are the primary reasons why this package even exists.

License

BSD/MIT