Documentation
¶
Overview ¶
Package btree provides a very specific set implementation for k/v lookup. This is based on a B PALM tree as described here: http://irvcvcs01.intel-research.net/publications/palm.pdf
This tree is best interacted with in batches. Insertions and deletions are optimized for dealing with large amounts of data.
Future work includes:
1) Optimization 2) Range scans
Usage:
rt := New(config) mutable := rt.AsMutable() ... operations
rt, err := mutable.Commit() // saves all mutated nodes
.. rt reading/operations
Once a mutable has been committed, its further operations are undefined.
Index ¶
- Variables
- type Comparator
- type Config
- type ID
- type Item
- type Key
- type Keys
- type MutableTree
- type Node
- type Payload
- type Persister
- type ReadableTree
- type Tr
- func (t *Tr) AddItems(its ...*Item) ([]*Item, error)
- func (t *Tr) Apply(fn func(item *Item), keys ...interface{}) error
- func (t *Tr) AsMutable() MutableTree
- func (t *Tr) Commit() (ReadableTree, error)
- func (t *Tr) DeleteItems(values ...interface{}) ([]*Item, error)
- func (t *Tr) ID() ID
- func (t *Tr) Len() int
- func (z *Tr) MarshalMsg(b []byte) (o []byte, err error)
- func (z *Tr) Msgsize() (s int)
- func (z *Tr) UnmarshalMsg(bts []byte) (o []byte, err error)
- type Tree
Constants ¶
This section is empty.
Variables ¶
var ErrNodeNotFound = errors.New(`node not found`)
ErrNodeNotFound is returned when the cacher could not find a node.
var ErrTreeNotFound = errors.New(`tree not found`)
ErrTreeNotFound is returned when a tree with the provided key could not be loaded.
Functions ¶
This section is empty.
Types ¶
type Comparator ¶
type Comparator func(item1, item2 interface{}) int
Comparator is used to determine ordering in the tree. If item1 is less than item2, a negative number should be returned and vice versa. If equal, 0 should be returned.
type Config ¶
type Config struct {
// NodeWidth defines the branching factor of the tree. Any node
// wider than this value will get split and when the width of a node
// falls to less than half this value the node gets merged. This
// ensures optimal performance while running to the key value store.
NodeWidth int
// Perister defines the key value store that the tree can use to
// save and load nodes.
Persister Persister
// Comparator is the function used to determine ordering.
Comparator Comparator `msg:"-"`
}
Config defines all the parameters available to the UB-tree. Of most important are nodewidth and the persister to be used during commit phase.
func DefaultConfig ¶
func DefaultConfig(persister Persister, comparator Comparator) Config
DefaultConfig returns a configuration with the persister set. All other fields are set to smart defaults for persistence.
type ID ¶
type ID []byte
ID exists because i'm tired of writing []byte
func (ID) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Key ¶
Key a convenience struct that holds both an id and a value. Internally, this is how we reference items in nodes but consumers interface with the tree using row/col/id.
func (*Key) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type MutableTree ¶
type MutableTree interface {
Tree
// Commit commits all mutated nodes to persistence and returns a
// read-only version of this tree. An error is returned if nodes
// could not be committed to persistence.
Commit() (ReadableTree, error)
// AddItems adds the provided items to the btree. Any existing items
// are overwritten. An error is returned if the tree could not be
// traversed due to an error in the persistence layer.
AddItems(items ...*Item) ([]*Item, error)
// DeleteItems removes all provided keys and returns them.
// An error is returned if the tree could not be traversed.
DeleteItems(keys ...interface{}) ([]*Item, error)
}
MutableTree represents a mutable version of the btree. This interface is not threadsafe.
type Node ¶
type Node struct {
// ID is the unique UUID that addresses this singular node.
ID ID `msg:"id"`
// IsLeaf is a bool indicating if this is a leaf node as opposed
// to an internal node. The primary difference between these nodes
// is that leaf nodes have an equal number of values and IDs while
// internal nodes have n+1 ids.
IsLeaf bool `msg:"il"`
// ChildValues is only a temporary field that is used to house all
// values for serialization purposes.
ChildValues []interface{} `msg:"cv"`
// ChildKeys is similar to child values but holds the IDs of children.
ChildKeys Keys `msg:"ck"`
}
Node represents either a leaf node or an internal node. These are the value containers. This is exported because code generation requires it. Only exported fields are required to be persisted. We use msgpack for optimal performance.
func (*Node) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Persister ¶
Perister describes the interface of the different implementations. Given that we expect that datastrutures are immutable, we never have the need to delete.
type ReadableTree ¶
type ReadableTree interface {
Tree
// AsMutable returns a mutable version of this tree. The mutable version
// has common mutations and you can create as many mutable versions of this
// tree as you'd like. However, the returned mutable is not threadsafe.
AsMutable() MutableTree
}
ReadableTree represents the operations that can be performed on a read-only version of the tree. All reads of the readable tree are threadsafe and an indefinite number of mutable trees can be created from a single readable tree with the caveat that no mutable trees reflect any mutations to any other mutable tree.
func Load ¶
func Load(p Persister, id []byte, comparator Comparator) (ReadableTree, error)
Load returns a ReadableTree from persistence. The provided config should contain a persister that can be used for this purpose. An error is returned if the tree could not be found or an error occurred in the persistence layer.
func New ¶
func New(cfg Config) ReadableTree
New creates a new ReadableTree using the provided config.
type Tr ¶
type Tr struct {
UUID ID `msg:"u"`
Count int `msg:"c"`
Root ID `msg:"r"`
NodeWidth int `msg:"nw"`
// contains filtered or unexported fields
}
Tr itself is exported so that the code generated for serialization/deserialization works on Tr. Exported fields on Tr are those fields that need to be serialized.
func (*Tr) AsMutable ¶
func (t *Tr) AsMutable() MutableTree
func (*Tr) Commit ¶
func (t *Tr) Commit() (ReadableTree, error)
func (*Tr) DeleteItems ¶
func (*Tr) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Tree ¶
type Tree interface {
// Apply takes a range and applies the provided function to every value
// in that range in order. If a key could not be found, it is
// skipped.
Apply(fn func(item *Item), keys ...interface{}) error
// ID returns the identifier for this tree.
ID() ID
// Len returns the number of items in the tree.
Len() int
}
Tree describes the common functionality of both the read-only and mutable forms of a btree.
Source Files