btree

README

BTree

The BTree package implements a generic B+Tree, a BTree where all the values are in the leaves, with a "pluggable" storage backend.

The tree itself doesn't manage the storage layout, it just need a Storer interface to get or update existing nodes or put new ones. It doesn't even manage a cache of blocks or a freelist, these issues are relegated to the storage layer.

A peculiar thing is that even the "pointer" type is parametrized, since it could be a disk sector, a mac, or a key in a leveldb cache.

There is a way to "convert" one tree from one storage to another via the Persist function that works in a way that's suitable for content-addressed stores (like a packfile.)

Documentation

Index

• Constants
• Variables
• func Persist[K, PA, PB, VA, VB any](b *BTree[K, PA, VA], store Storer[K, PB, VB], conv func(VA) (VB, error)) (ptr PB, err error)
• type BTree
  • func Deserialize[K, P, V any](rd io.Reader, store Storer[K, P, V], compare func(K, K) int) (*BTree[K, P, V], error)
  • func FromStorage[K any, P any, V any](root P, store Storer[K, P, V], compare func(K, K) int, order int) *BTree[K, P, V]
  • func New[K any, P any, V any](store Storer[K, P, V], compare func(K, K) int, order int) (*BTree[K, P, V], error)
  • func (b *BTree[K, P, V]) Dot(w io.Writer, showNextPtrs bool) error
  • func (b *BTree[K, P, V]) Find(key K) (val V, found bool, err error)
  • func (b *BTree[K, P, V]) Insert(key K, val V) error
  • func (b *BTree[K, P, V]) IterDFS() Iterator[P, *Node[K, P, V]]
  • func (b *BTree[K, P, V]) ScanAll() (Iterator[K, V], error)
  • func (b *BTree[K, P, V]) ScanAllReverse() (Iterator[K, V], error)
  • func (b *BTree[K, P, V]) ScanFrom(key K) (Iterator[K, V], error)
  • func (b *BTree[K, P, V]) Update(key K, val V) error
  • func (b *BTree[K, P, V]) Verify() error
• type InMemoryStore
  • func (s *InMemoryStore[K, V]) Get(ptr int) (n *Node[K, int, V], err error)
  • func (s *InMemoryStore[K, V]) Put(n *Node[K, int, V]) (int, error)
  • func (s *InMemoryStore[K, V]) Update(ptr int, n *Node[K, int, V]) error
• type Iterator
• type Node
• type Storer
• type VerifyState

Constants

const BTREE_VERSION = "1.0.0"

Variables

var (
	ErrExists = errors.New("Item already exists")
)

Functions

func Persist

func Persist[K, PA, PB, VA, VB any](b *BTree[K, PA, VA], store Storer[K, PB, VB], conv func(VA) (VB, error)) (ptr PB, err error)

Persist converts a BTree from one storage backend to another. The given store only needs to provide a working Put method, since by design Persist inserts the nodes in post-order from the right-most leaf, in a way that's suitable for a content-addressed store, and never updates existing nodes nor retrieves inserted ones.

Types

type BTree

type BTree[K any, P any, V any] struct {
	Version versioning.Version
	Order   int
	Count   int
	Root    P
	// contains filtered or unexported fields
}

BTree implements a B+tree. K is the type for the key, V for the value stored, and P is a pointer type: it could be a disk sector, a MAC in a packfile, or a key in a leveldb cache. or more.

func Deserialize

func Deserialize[K, P, V any](rd io.Reader, store Storer[K, P, V], compare func(K, K) int) (*BTree[K, P, V], error)

func FromStorage

func FromStorage[K any, P any, V any](root P, store Storer[K, P, V], compare func(K, K) int, order int) *BTree[K, P, V]

FromStorage returns a btree from the given storage. The root must exist, eventually empty, i.e. it should be a tree previously created via New().

func New

func New[K any, P any, V any](store Storer[K, P, V], compare func(K, K) int, order int) (*BTree[K, P, V], error)

New returns a new, empty tree.

func (*BTree[K, P, V]) Dot

func (b *BTree[K, P, V]) Dot(w io.Writer, showNextPtrs bool) error

func (*BTree[K, P, V]) Find

func (b *BTree[K, P, V]) Find(key K) (val V, found bool, err error)

func (*BTree[K, P, V]) Insert

func (b *BTree[K, P, V]) Insert(key K, val V) error

func (*BTree[K, P, V]) IterDFS

func (b *BTree[K, P, V]) IterDFS() Iterator[P, *Node[K, P, V]]

func (*BTree[K, P, V]) ScanAll

func (b *BTree[K, P, V]) ScanAll() (Iterator[K, V], error)

ScanAll returns an iterator that visits all the values from the smaller one onwards.

func (*BTree[K, P, V]) ScanAllReverse

func (b *BTree[K, P, V]) ScanAllReverse() (Iterator[K, V], error)

func (*BTree[K, P, V]) ScanFrom

func (b *BTree[K, P, V]) ScanFrom(key K) (Iterator[K, V], error)

ScanFrom returns an iterator that visits all the values starting from the given key, or the first key larger than the given one, onwards.

func (*BTree[K, P, V]) Update

func (b *BTree[K, P, V]) Update(key K, val V) error

func (*BTree[K, P, V]) Verify

func (b *BTree[K, P, V]) Verify() error

type InMemoryStore

type InMemoryStore[K any, V any] struct {
	// contains filtered or unexported fields
}

func (*InMemoryStore[K, V]) Get

func (s *InMemoryStore[K, V]) Get(ptr int) (n *Node[K, int, V], err error)

func (*InMemoryStore[K, V]) Put

func (s *InMemoryStore[K, V]) Put(n *Node[K, int, V]) (int, error)

func (*InMemoryStore[K, V]) Update

func (s *InMemoryStore[K, V]) Update(ptr int, n *Node[K, int, V]) error

type Iterator

type Iterator[K, V any] interface {
	Next() bool
	Current() (K, V)
	Err() error
}

type Node

type Node[K any, P any, V any] struct {
	Version versioning.Version `msgpack:"version"`

	// An intermediate node has only Keys and Pointers, while
	// leaves have only keys and values and optionally a next
	// pointer.
	//
	// invariant: len(Pointers) == len(Keys) + 1 in intermediate nodes
	// invariant: len(Values)   == len(Keys)     in leaf nodes
	Keys     []K `msgpack:"keys"`
	Pointers []P `msgpack:"pointers"`
	Values   []V `msgpack:"values"`
	Prev     *P  `msgpack:"prev,omitempty"` // unused for now
	Next     *P  `msgpack:"next,omitempty"`
}

type Storer

type Storer[K any, P any, V any] interface {
	// Get returns the node pointed by P.  The pointer is one
	// previously returned by the Put method.
	Get(P) (*Node[K, P, V], error)
	// Updates in-place the node pointed by P.
	Update(P, *Node[K, P, V]) error
	// Put saves a new node and returns its address, or an error.
	Put(*Node[K, P, V]) (P, error)
}

type VerifyState

type VerifyState struct {
	LeafDepth    int
	CurrDepth    int
	VisitedCount int64
}