btree

Documentation

Overview

Package btree implements B-trees with fixed size keys are saved in a specified storage, http://en.wikipedia.org/wiki/Btree.

Index

• Variables
• type BTree
  • func (this BTree) Capacity() uint
  • func (this *BTree) Delete(key Key) (Key, error)
  • func (this *BTree) Enum(key Key) func() (Key, error)
  • func (this *BTree) Find(key Key) (Key, error)
  • func (this *BTree) Insert(key Key) (Key, error)
  • func (this BTree) KeySize() uint
  • func (this BTree) Magic() [16]byte
  • func (this *BTree) ReverseEnum(key Key) func() (Key, error)
  • func (this *BTree) Update(key Key) (Key, error)
• type Key
• type Tree
  • func NewBTree(storage io.ReadWriteSeeker, magic [16]byte, key Key, capacity uint) (Tree, error)
  • func OpenBTree(storage io.ReadSeeker, magic [16]byte, key Key) (Tree, error)
• Bugs

Variables

var (
	NoReader        = errors.New("reader is not specified")
	NoWriter        = errors.New("write operations are assumed - io.ReadWriteSeeker has to be specified insead of io.ReadSeeker")
	OddCapacity     = errors.New("capacity must be even")
	MagicMismatch   = errors.New("magic mismatch")
	KeySizeMismatch = errors.New("key size mismatch")
)

Errors in addition to IO errors.

Types

type BTree

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

an internal representation of B-tree.

func (BTree) Capacity

func (this BTree) Capacity() uint

Capacity returns a number of keys per node.

func (*BTree) Delete

func (this *BTree) Delete(key Key) (Key, error)

Delete deletes a key from the tree. It returns the key if it is deleted or nil if the key is not found and an error, if any.

func (*BTree) Enum

func (this *BTree) Enum(key Key) func() (Key, error)

Enum returns a function-iterator to process enumeration entire the tree from lower to bigger keys. Enumerating starts with key, if it is specified, or with lowest key otherwise. The iterator returns the key or nil if the end of the tree is reached and an error, if any.

func (*BTree) Find

func (this *BTree) Find(key Key) (Key, error)

Find searches a key in the tree. It returns the key if it is found or nil if the key is not found and an error, if any.

func (*BTree) Insert

func (this *BTree) Insert(key Key) (Key, error)

Find searches a key in the tree. It returns the key if it is already exists or nil if the key is inserted and an error, if any.

func (BTree) KeySize

func (this BTree) KeySize() uint

KeySize returns a size in bytes of the underlying key.

func (BTree) Magic

func (this BTree) Magic() [16]byte

Magic returns a magic of the B-tree storage.

func (*BTree) ReverseEnum

func (this *BTree) ReverseEnum(key Key) func() (Key, error)

ReverseEnum returns a function-iterator to process enumeration entire the tree from bigger to lower keys. Enumerating starts with key, if it is specified, or with biggest key otherwise. The iterator returns the key or nil if the end of the tree is reached and an error, if any.

func (*BTree) Update

func (this *BTree) Update(key Key) (Key, error)

Update updates a key in the tree. This is useful if the key is complex type with additional information. It returns an old value of the key if the key is updated or nil if the key is not found and an error, if any.

type Key

type Key interface {
	Compare(b []byte) (int, error)
	Size() uint
	Read(b []byte) error
	Write(b []byte) error
}

An interface a key must support to be stored in the tree. A key must be exact the len of b All fields of the key must be exportable. Compare has to return a value less that 0, equal of 0 or more that 0 if k is less, equal or more that an underlying key in b. An error must be returned if something is wrong. Size returns a size of key in bytes, the size has to be immutable Read reads a key from b Write writes a key to b

type Tree

type Tree interface {
	Find(key Key) (Key, error)
	Insert(key Key) (Key, error)
	Update(key Key) (Key, error)
	Delete(key Key) (Key, error)
	Enum(key Key) func() (Key, error)
	ReverseEnum(key Key) func() (Key, error)
}

A basic interface for tree operations.

func NewBTree

func NewBTree(storage io.ReadWriteSeeker, magic [16]byte, key Key, capacity uint) (Tree, error)

NewBTree creates a new B-tree with magic like a file magic, key like a key type and capacity like a number of elements per data. The capacity must be even. It returns a pointer to the new tree and an error, if any

func OpenBTree

func OpenBTree(storage io.ReadSeeker, magic [16]byte, key Key) (Tree, error)

OpenBTree opens an existing B-tree. The file magic and magic must be the same, the type and the size of key and of the key in the tree must be the same too. If changing of the tree is planning, storage has to be io.ReadWriteSeeker. It returns a pointer to the new tree and an error, if any.

Notes

Bugs

• The storage with B-tree can't be reduced even after erasing all of its keys. All empty nodes are stored and reused when necessary