Documentation
¶
Overview ¶
Package b implements a B+tree.
Changelog ¶
2014-04-18: Added new method Put.
Generic types ¶
Keys and their associated values are interface{} typed, similar to all of the containers in the standard library.
Semiautomatic production of a type specific variant of this package is supported via
$ make generic
This command will write to stdout a version of the btree.go file where every key type occurrence is replaced by the word 'key' (written in all CAPS) and every value type occurrence is replaced by the word 'value' (written in all CAPS). Then you have to replace these tokens with your desired type(s), using any technique you're comfortable with.
This is how, for example, 'example/int.go' was created:
$ mkdir example $ $ # Note: the command bellow must be actually written using the words $ # 'key' and 'value' in all CAPS. The proper form is avoided in this $ # documentation to not confuse any text replacement mechanism. $ $ make generic | sed -e 's/key/int/g' -e 's/value/int/g' > example/int.go
No other changes to int.go are (strictly) necessary, it compiles just fine. In a next step, benchmarks from all_test.go were copied into example/bench_test.go without any changes. A comparator is defined in bench_test.go like this:
func cmp(a, b int) int {
return a - b
}
Running the benchmarks on a machine with Intel X5450 CPU @ 3 GHz:
Go release (1.1.2)
$ go test -bench . example/bench_test.go example/int.go testing: warning: no tests to run PASS BenchmarkSetSeq 5000000 590 ns/op BenchmarkSetRnd 1000000 1530 ns/op BenchmarkGetSeq 10000000 373 ns/op BenchmarkGetRnd 2000000 1109 ns/op BenchmarkDelSeq 5000000 672 ns/op BenchmarkDelRnd 1000000 1275 ns/op BenchmarkSeekSeq 5000000 552 ns/op BenchmarkSeekRnd 1000000 1108 ns/op BenchmarkNext1e3 200000 13414 ns/op BenchmarkPrev1e3 200000 13215 ns/op ok command-line-arguments 51.372s $
Go 1.2rc2
$ go test -bench . example/bench_test.go example/int.go testing: warning: no tests to run PASS BenchmarkSetSeq 5000000 535 ns/op BenchmarkSetRnd 1000000 1428 ns/op BenchmarkGetSeq 10000000 376 ns/op BenchmarkGetRnd 2000000 1105 ns/op BenchmarkDelSeq 5000000 618 ns/op BenchmarkDelRnd 1000000 1213 ns/op BenchmarkSeekSeq 5000000 538 ns/op BenchmarkSeekRnd 1000000 1088 ns/op BenchmarkNext1e3 200000 13410 ns/op BenchmarkPrev1e3 200000 13528 ns/op ok command-line-arguments 48.823s $
Note that the Next and Prev benchmarks enumerate 1000 items (KV pairs), so getting the next or previous iterated item is performed in about 13-14 ns. This is the nice O(1) property of B+trees usually not found in other tree types.
Index ¶
- type Cmp
- type Enumerator
- type Tree
- func (t *Tree) Clear()
- func (t *Tree) Delete(k string) (ok bool)
- func (t *Tree) First() (k string, v struct{})
- func (t *Tree) Get(k string) (v struct{}, ok bool)
- func (t *Tree) Last() (k string, v struct{})
- func (t *Tree) Len() int
- func (t *Tree) Put(k string, upd func(oldV struct{}, exists bool) (newV struct{}, write bool)) (oldV struct{}, written bool)
- func (t *Tree) Seek(k string) (e *Enumerator, ok bool)
- func (t *Tree) SeekFirst() (e *Enumerator, err error)
- func (t *Tree) SeekLast() (e *Enumerator, err error)
- func (t *Tree) Set(k string, v struct{})
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Enumerator ¶
type Enumerator struct {
// contains filtered or unexported fields
}
Enumerator captures the state of enumerating a tree. It is returned from the Seek* methods. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration at the proper key, if possible.
However, once an Enumerator returns io.EOF to signal "no more items", it does no more attempt to "resync" on tree mutation(s). In other words, io.EOF from an Enumaretor is "sticky" (idempotent).
func (*Enumerator) Next ¶
func (e *Enumerator) Next() (k string, v struct{}, err error)
Next returns the currently enumerated item, if it exists and moves to the next item in the key collation order. If there is no item to return, err == io.EOF is returned.
func (*Enumerator) Prev ¶
func (e *Enumerator) Prev() (k string, v struct{}, err error)
Prev returns the currently enumerated item, if it exists and moves to the previous item in the key collation order. If there is no item to return, err == io.EOF is returned.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a B+tree.
func TreeNew ¶
TreeNew returns a newly created, empty Tree. The compare function is used for key collation.
func (*Tree) Delete ¶
Delete removes the k's KV pair, if it exists, in which case Delete returns true.
func (*Tree) First ¶
First returns the first item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.
func (*Tree) Get ¶
Get returns the value associated with k and true if it exists. Otherwise Get returns (zero-value, false).
func (*Tree) Last ¶
Last returns the last item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.
func (*Tree) Put ¶
func (t *Tree) Put(k string, upd func(oldV struct{}, exists bool) (newV struct{}, write bool)) (oldV struct{}, written bool)
Put combines Get and Set in a more efficient way where the tree is walked only once. The upd(ater) receives (old-value, true) if a KV pair for k exists or (zero-value, false) otherwise. It can then return a (new-value, true) to create or overwrite the existing value in the KV pair, or (whatever, false) if it decides not to create or not to update the value of the KV pair.
tree.Set(k, v) conceptually equals
tree.Put(k, func(k, v []byte){ return v, true }([]byte, bool))
modulo the differing return values.
func (*Tree) Seek ¶
func (t *Tree) Seek(k string) (e *Enumerator, ok bool)
Seek returns an Enumerator positioned on a an item such that k >= item's key. ok reports if k == item.key The Enumerator's position is possibly after the last item in the tree.
func (*Tree) SeekFirst ¶
func (t *Tree) SeekFirst() (e *Enumerator, err error)
SeekFirst returns an enumerator positioned on the first KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.
func (*Tree) SeekLast ¶
func (t *Tree) SeekLast() (e *Enumerator, err error)
SeekLast returns an enumerator positioned on the last KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.
Source Files