btree

package
v1.0.46 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 12, 2018 License: Apache-2.0 Imports: 10 Imported by: 0

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL