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
- Bugs
Constants ¶
This section is empty.
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.
Functions ¶
This section is empty.
Types ¶
type BTree ¶
type BTree struct {
// contains filtered or unexported fields
}
an internal representation of B-tree.
func (*BTree) Delete ¶
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 ¶
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 ¶
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 ¶
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) ReverseEnum ¶
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.
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 ¶
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 ¶
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
Source Files