fossabot/bptree

In-memory B+ tree implementation for Go

rbytree

A B+ tree implementation for Go with byte-slice keys and values.

Installation

To install, run:

go get github.com/krasun/bptree

Quickstart

Feel free to play:

package main

import (
	"fmt"

	"github.com/krasun/bptree"
)

func main() {
	tree := bptree.New()

	tree.Put([]byte("apple"), []byte("sweet"))
	tree.Put([]byte("banana"), []byte("honey"))
	tree.Put([]byte("cinnamon"), []byte("savoury"))

	banana, ok := tree.Get([]byte("banana"))
	if ok {
		fmt.Printf("banana = %s\n", string(banana))
	} else {
		fmt.Println("value for banana not found")
	}

	tree.ForEach(func(key, value []byte) {
		fmt.Printf("key = %s, value = %s\n", string(key), string(value))
	})

	// Output: 
	// banana = honey
	// key = apple, value = sweet
	// key = banana, value = honey
	// key = cinnamon, value = savoury
}

You can use an iterator:

package main

import (
	"fmt"

	"github.com/krasun/bptree"
)

func main() {
	tree := bptree.New()

	tree.Put([]byte("apple"), []byte("sweet"))
	tree.Put([]byte("banana"), []byte("honey"))
	tree.Put([]byte("cinnamon"), []byte("savoury"))

	banana, ok := tree.Get([]byte("banana"))
	if ok {
		fmt.Printf("banana = %s\n", string(banana))
	} else {
		fmt.Println("value for banana not found")
	}

	for it := tree.Iterator(); it.HasNext(); {
		key, value := it.Next()
		fmt.Printf("key = %s, value = %s\n", string(key), string(value))
	}

	// Output: 
	// banana = honey
	// key = apple, value = sweet
	// key = banana, value = honey
	// key = cinnamon, value = savoury
}

An iterator is stateful. You can have multiple iterators without any impact on each other, but make sure to synchronize access to them and the tree in a concurrent environment.

Caution! Next panics if there is no next element. Make sure to test for the next element with HasNext before.

Use cases

1. When you want to use []byte as a key in the map.
2. When you want to iterate over keys in map in sorted order.

Limitations

Caution! To guarantee that the B+ tree properties are not violated, keys are copied.

You should clearly understand what []byte slice is and why it is dangerous to use it as a key. Go language authors do prohibit using byte slice ([]byte) as a map key for a reason. The point is that you can change the values of the key and thus violate the invariants of map:

// if it worked 
b := []byte{1}
m := make(map[[]byte]int)
m[b] = 1

b[0] = 2 // it would violate the invariants 
m[[]byte{1}] // what do you expect to receive?

So to make sure that this situation does not occur in the tree, the key is copied byte by byte.

Tests

Run tests with:

$ go test -cover .
ok  	github.com/krasun/bptree	0.245s	coverage: 100.0% of statements

License

rbytree is released under the MIT license.