fbptree

README

fbptree

fbptree is a persistent key-value storage engine based on B+ tree with byte-slice keys and values.

Installation

To install, run:

go get github.com/krasun/fbptree

Usage

An example of usage:

package fbptree_test

import (
	"fmt"
	"io/ioutil"
	"os"
	"path"

	"github.com/krasun/fbptree"
)

func Example() {
	dbDir, err := ioutil.TempDir(os.TempDir(), "example")
	if err != nil {
		panic(fmt.Errorf("failed to create %s: %w", dbDir, err))
	}
	defer func() {
		if err := os.RemoveAll(dbDir); err != nil {
			panic(fmt.Errorf("failed to remove %s: %w", dbDir, err))
		}
	}()

	dbPath := path.Join(dbDir, "sample.data")

	tree, err := fbptree.Open(dbPath, fbptree.PageSize(4096), fbptree.Order(500))
	if err != nil {
		panic(fmt.Errorf("failed to open B+ tree %s: %w", dbDir, err))
	}

	_, _, err = tree.Put([]byte("Hi!"), []byte("Hello world, B+ tree!"))
	if err != nil {
		panic(fmt.Errorf("failed to put: %w", err))
	}

	_, _, err = tree.Put([]byte("Does it override key?"), []byte("No!"))
	if err != nil {
		panic(fmt.Errorf("failed to put: %w", err))
	}

	_, _, err = tree.Put([]byte("Does it override key?"), []byte("Yes, absolutely! The key has been overridden."))
	if err != nil {
		panic(fmt.Errorf("failed to put: %w", err))
	}

	if err := tree.Close(); err != nil {
		panic(fmt.Errorf("failed to close: %w", err))
	}

	tree, err = fbptree.Open(dbPath, fbptree.PageSize(4096), fbptree.Order(500))
	if err != nil {
		panic(fmt.Errorf("failed to open B+ tree %s: %w", dbDir, err))
	}

	value, ok, err := tree.Get([]byte("Hi!"))
	if err != nil {
		panic(fmt.Errorf("failed to get value: %w", err))
	}
	if !ok {
		fmt.Println("failed to find value")
	}

	fmt.Println(string(value))

	value, ok, err = tree.Get([]byte("Does it override key?"))
	if err != nil {
		panic(fmt.Errorf("failed to get value: %w", err))
	}
	if !ok {
		fmt.Println("failed to find value")
	}

	if err := tree.Close(); err != nil {
		panic(fmt.Errorf("failed to close: %w", err))
	}

	fmt.Println(string(value))
	// Output:
	// Hello world, B+ tree!
	// Yes, absolutely! The key has been overridden.
}

Tests

Run tests with:

$ go test .
ok  	github.com/krasun/fbptree	0.679s

License

fbptree is released under the MIT license.

Documentation

Overview

Example

dbDir, err := ioutil.TempDir(os.TempDir(), "example")
if err != nil {
	panic(fmt.Errorf("failed to create %s: %w", dbDir, err))
}
defer func() {
	if err := os.RemoveAll(dbDir); err != nil {
		panic(fmt.Errorf("failed to remove %s: %w", dbDir, err))
	}
}()

dbPath := path.Join(dbDir, "sample.data")

tree, err := Open(dbPath, PageSize(4096), Order(500))
if err != nil {
	panic(fmt.Errorf("failed to open B+ tree %s: %w", dbDir, err))
}

_, _, err = tree.Put([]byte("Hi!"), []byte("Hello world, B+ tree!"))
if err != nil {
	panic(fmt.Errorf("failed to put: %w", err))
}

_, _, err = tree.Put([]byte("Does it override key?"), []byte("No!"))
if err != nil {
	panic(fmt.Errorf("failed to put: %w", err))
}

_, _, err = tree.Put([]byte("Does it override key?"), []byte("Yes, absolutely! The key has been overridden."))
if err != nil {
	panic(fmt.Errorf("failed to put: %w", err))
}

if err := tree.Close(); err != nil {
	panic(fmt.Errorf("failed to close: %w", err))
}

tree, err = Open(dbPath, PageSize(4096), Order(500))
if err != nil {
	panic(fmt.Errorf("failed to open B+ tree %s: %w", dbDir, err))
}

value, ok, err := tree.Get([]byte("Hi!"))
if err != nil {
	panic(fmt.Errorf("failed to get value: %w", err))
}
if !ok {
	fmt.Println("failed to find value")
}

fmt.Println(string(value))

value, ok, err = tree.Get([]byte("Does it override key?"))
if err != nil {
	panic(fmt.Errorf("failed to get value: %w", err))
}
if !ok {
	fmt.Println("failed to find value")
}

if err := tree.Close(); err != nil {
	panic(fmt.Errorf("failed to close: %w", err))
}

fmt.Println(string(value))

Output:

Hello world, B+ tree!
Yes, absolutely! The key has been overridden.

Index

• func Order(order int) func(*config) error
• func PageSize(pageSize int) func(*config) error
• type FBPTree
  • func Open(path string, options ...func(*config) error) (*FBPTree, error)
  • func (t *FBPTree) Close() error
  • func (t *FBPTree) Delete(key []byte) ([]byte, bool, error)
  • func (t *FBPTree) ForEach(action func(key []byte, value []byte)) error
  • func (t *FBPTree) Get(key []byte) ([]byte, bool, error)
  • func (t *FBPTree) Iterator() (*Iterator, error)
  • func (t *FBPTree) Put(key, value []byte) ([]byte, bool, error)
  • func (t *FBPTree) Size() int
• type Iterator
  • func (it *Iterator) HasNext() bool
  • func (it *Iterator) Next() ([]byte, []byte, error)

Examples

• Package

Functions

func Order

func Order(order int) func(*config) error

Order option specifies the order of the B+ tree, between 3 and 1000.

func PageSize

func PageSize(pageSize int) func(*config) error

PageSize option specifies the page size for the B+ tree file.

Types

type FBPTree

type FBPTree struct {
	// contains filtered or unexported fields
}

FBPTree represents B+ tree store in the file.

func Open

func Open(path string, options ...func(*config) error) (*FBPTree, error)

Open opens an existent B+ tree or creates a new file.

func (*FBPTree) Close

func (t *FBPTree) Close() error

Close closes the tree and free the underlying resources.

func (*FBPTree) Delete

func (t *FBPTree) Delete(key []byte) ([]byte, bool, error)

Delete deletes the value by the key. Returns true if the key exists.

func (*FBPTree) ForEach

func (t *FBPTree) ForEach(action func(key []byte, value []byte)) error

ForEach traverses tree in ascending key order.

func (*FBPTree) Get

func (t *FBPTree) Get(key []byte) ([]byte, bool, error)

Get return the value by the key. Returns true if the key exists.

func (*FBPTree) Iterator

func (t *FBPTree) Iterator() (*Iterator, error)

Iterator returns a stateful iterator that traverses the tree in ascending key order.

func (*FBPTree) Put

func (t *FBPTree) Put(key, value []byte) ([]byte, bool, error)

Put puts the key and the value into the tree. Returns true if the key already exists and anyway overwrites it.

func (*FBPTree) Size

func (t *FBPTree) Size() int

Size return the size of the tree.

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator returns a stateful Iterator for traversing the tree in ascending key order.

func (*Iterator) HasNext

func (it *Iterator) HasNext() bool

HasNext returns true if there is a next element to retrive.

func (*Iterator) Next

func (it *Iterator) Next() ([]byte, []byte, error)

Next returns a key and a value at the current position of the iteration and advances the iterator. Caution! Next panics if called on the nil element.