btree

README

This btree module originally comes from github.com/cznic/b. It deals with interface{} but includes a make generic rule that replaces types with KEY and VALUE strings, which you are then supposed to replace with the types you want.

I have taken that and replaced KEY with generic.T and VALUE with generic.U.

Use gengen to generate a type-specific instance:

$ gengen btree int string > main/btree.go
$ go run main/*.go

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.