btree

Documentation

Overview

Package btree implements an immutable persistent in-memory version of B-trees.

An immutable persistent tree has copy-on-write behaviour: Each “modification” of the tree (insertion, replacement or deletion) creates a copy, leaving the original unmodified. Under the hood, copy-on-write retains most of the memory held by the original, and creates a new incarnation of parts of the structure only. Thus, most of the structure/memory is shared between original and copy, transparently to clients.

Immutable trees are inherently concurrency-safe.

Status

Awaiting Go 1.18 with generics.

License

Governed by a 3-Clause BSD license. License file may be found in the root folder of this module.

Copyright © 2022 Norbert Pillmayer <norbert@pillmayer.com>

Index

• type Ext
• type K
• type Location
• type Option
  • func Degree(n int) Option
• type T
• type Tree
  • func Immutable(opts ...Option) Tree
  • func (tree Tree) Ext(ext Ext) TreeExtension
  • func (tree Tree) Find(key K) (T, bool)
  • func (tree Tree) With(key K, value T) Tree
  • func (tree Tree) WithDeleted(key K) Tree
• type TreeExtension
  • func (tex TreeExtension) Locate(key K) Location

Types

type Ext

type Ext interface {
	Agg(key, agg K) K
	Cmp(key, itemKey, agg K) int
}

Ext (extensions) is something I'll need for using B-trees as ropes/cords in the future. I'm not yet sure of how to go about it in a general way, but my current thinking is that Extension will let clients treat a tree like a tree (in a controlled fashion), while the primary API of B-tree is more like a map.

type K

type K int // TODO for generics: change to type parameter, ordered

type Location

type Location struct {
	// contains filtered or unexported fields
}

Location reflects a key/value pair in the B-tree, together with the node-path to it. A location is valid for a specific incarnation of a tree only; applying any of its methods on a different incarnation will result in a panic.

type Option

type Option func(Tree) Tree

Option is a type to help initializing B-trees at creation time.

func Degree

func Degree(n int) Option

Degree is an option to set the minimum number of children a node in the tree owns. The lower bound for the degree is 3.

Use it like this:

tree := btree.Immutable[int, string](Degree(16))

type T

type T interface{} // TODO for generics: change to type parameter, comparable

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree is an in-memory B-tree. An empty instance is usable as an empty tree, i.e. this is legal:

tree := btree.Tree[int,int]{}.With(1, 42)

returning a tree containing a single node ⟨1⟩ associated with value 42.

func Immutable

func Immutable(opts ...Option) Tree

Immutable constructs a B-tree with options, if you need any. Use it like this:

tree := btree.Immutable[int, string](Degree(16))
tree = tree.With(42, "Galaxy")
value, found := tree.Find(42)   // returns "Galaxy"

func (Tree) Ext

func (tree Tree) Ext(ext Ext) TreeExtension

Ext returns a tree extension for a given incarnation of a tree. This will wrap a client-provided Ext into an opaque TreeExtension, which then will manage accessing tree-properties of B-trees.

Supplying nil as an ext result in returning a default type TreeExtension.

func (Tree) Find

func (tree Tree) Find(key K) (T, bool)

Find locates a key in a tree, if present, and returns the value associated with the key. If `key` is not found, the zero value for type T will be returned, together with found=false.

func (Tree) With

func (tree Tree) With(key K, value T) Tree

With returns a copy of a tree with a new key inserted, which is associated with `value`. If an entry for key is already present in tree, the associated value will be replaced (in a new incarnation of the tree, nevertheless).

func (Tree) WithDeleted

func (tree Tree) WithDeleted(key K) Tree

With returns a copy of a tree with key deleted, if present, together with its associated value. If key is not found, tree is returned unchanged.

type TreeExtension

type TreeExtension struct {
	// contains filtered or unexported fields
}

TreeExtension represents a B-tree as a tree and exposes some of its tree properties.

This is something I'll need for using B-trees as ropes/cords in the future. I'm not yet sure of how to go about it in a general way, but my current thinking is that Extension will let clients treat a tree like a tree (in a controlled fashion), while the primary API of B-tree is more like a map.

func (TreeExtension) Locate

func (tex TreeExtension) Locate(key K) Location