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

    Constants

    This section is empty.

    Variables

    View Source
    var ErrNodeNotFound = errors.New(`node not found`)

      ErrNodeNotFound is returned when the cacher could not find a node.

      View Source
      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

                func (z ID) MarshalMsg(b []byte) (o []byte, err error)

                  MarshalMsg implements msgp.Marshaler

                  func (ID) Msgsize

                  func (z ID) Msgsize() (s int)

                  func (*ID) UnmarshalMsg

                  func (z *ID) UnmarshalMsg(bts []byte) (o []byte, err error)

                    UnmarshalMsg implements msgp.Unmarshaler

                    type Item

                    type Item struct {
                    	Value   interface{}
                    	Payload []byte
                    }

                    type Key

                    type Key struct {
                    	UUID    ID          `msg:"u"`
                    	Value   interface{} `msg:"v"`
                    	Payload []byte      `msg:"p"`
                    }

                      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) ID

                      func (k Key) ID() []byte

                        ID returns the unique identifier.

                        func (*Key) MarshalMsg

                        func (z *Key) MarshalMsg(b []byte) (o []byte, err error)

                          MarshalMsg implements msgp.Marshaler

                          func (*Key) Msgsize

                          func (z *Key) Msgsize() (s int)

                          func (Key) ToItem

                          func (k Key) ToItem() *Item

                          func (*Key) UnmarshalMsg

                          func (z *Key) UnmarshalMsg(bts []byte) (o []byte, err error)

                            UnmarshalMsg implements msgp.Unmarshaler

                            type Keys

                            type Keys []*Key

                            func (Keys) MarshalMsg

                            func (z Keys) MarshalMsg(b []byte) (o []byte, err error)

                              MarshalMsg implements msgp.Marshaler

                              func (Keys) Msgsize

                              func (z Keys) Msgsize() (s int)

                              func (*Keys) UnmarshalMsg

                              func (z *Keys) UnmarshalMsg(bts []byte) (o []byte, err error)

                                UnmarshalMsg implements msgp.Unmarshaler

                                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

                                    func (z *Node) MarshalMsg(b []byte) (o []byte, err error)

                                      MarshalMsg implements msgp.Marshaler

                                      func (*Node) Msgsize

                                      func (z *Node) Msgsize() (s int)

                                      func (*Node) UnmarshalMsg

                                      func (z *Node) UnmarshalMsg(bts []byte) (o []byte, err error)

                                        UnmarshalMsg implements msgp.Unmarshaler

                                        type Payload

                                        type Payload struct {
                                        	Key     []byte
                                        	Payload []byte
                                        }

                                          Payload is very basic and simply contains a key and a payload.

                                          type Persister

                                          type Persister interface {
                                          	Save(items ...*Payload) error
                                          	Load(keys ...[]byte) ([]*Payload, error)
                                          }

                                            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) AddItems

                                                    func (t *Tr) AddItems(its ...*Item) ([]*Item, error)

                                                    func (*Tr) Apply

                                                    func (t *Tr) Apply(fn func(item *Item), keys ...interface{}) error

                                                    func (*Tr) AsMutable

                                                    func (t *Tr) AsMutable() MutableTree

                                                    func (*Tr) Commit

                                                    func (t *Tr) Commit() (ReadableTree, error)

                                                    func (*Tr) DeleteItems

                                                    func (t *Tr) DeleteItems(values ...interface{}) ([]*Item, error)

                                                    func (*Tr) ID

                                                    func (t *Tr) ID() ID

                                                    func (*Tr) Len

                                                    func (t *Tr) Len() int

                                                    func (*Tr) MarshalMsg

                                                    func (z *Tr) MarshalMsg(b []byte) (o []byte, err error)

                                                      MarshalMsg implements msgp.Marshaler

                                                      func (*Tr) Msgsize

                                                      func (z *Tr) Msgsize() (s int)

                                                      func (*Tr) UnmarshalMsg

                                                      func (z *Tr) UnmarshalMsg(bts []byte) (o []byte, err error)

                                                        UnmarshalMsg implements msgp.Unmarshaler

                                                        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.