btree

Documentation

Overview

Package btree implements in-memory B-trees of arbitrary degree.

btree implements an in-memory B-tree for use as an ordered data structure. It is not meant for persistent storage solutions.

It has a flatter structure than an equivalent red-black or other binary tree, which in some cases yields better memory usage and/or performance. See some discussion on the matter here:

http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html

Note, though, that this project is in no way related to the C++ B-tree implementation written about there.

Within this tree, each node contains a slice of items and a (possibly nil) slice of children. For basic numeric values or raw structs, this can cause efficiency differences when compared to equivalent C++ template code that stores values in arrays within the node:

• Due to the overhead of storing values as interfaces (each value needs to be stored as the value itself, then 2 words for the interface pointing to that value and its type), resulting in higher memory use.
• Since interfaces can point to values anywhere in memory, values are most likely not stored in contiguous blocks, resulting in a higher number of cache misses.

These issues don't tend to matter, though, when working with strings or other heap-allocated structures, since C++-equivalent structures also must store pointers and also distribute their values across the heap.

This implementation is designed to be a drop-in replacement to gollrb.LLRB trees, (http://github.com/petar/gollrb), an excellent and probably the most widely used ordered tree implementation in the Go ecosystem currently. Its functions, therefore, exactly mirror those of llrb.LLRB where possible. Unlike gollrb, though, we currently don't support storing multiple equivalent values.

Index

• Constants
• func DefaultTargetNodeSize[T Item]() int
• type BTree
  • func New[T Item](degree int) *BTree[T]
  • func NewWithFreeList[T Item](degree int, f *FreeList[T]) *BTree[T]
  • func (t *BTree[T]) Ascend(iterator ItemIterator[T])
  • func (t *BTree[T]) AscendGreaterOrEqual(pivot T, iterator ItemIterator[T])
  • func (t *BTree[T]) AscendLessThan(pivot T, iterator ItemIterator[T])
  • func (t *BTree[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIterator[T])
  • func (t *BTree[T]) Clear(addNodesToFreelist bool)
  • func (t *BTree[T]) Clone() (t2 *BTree[T])
  • func (t *BTree[T]) Delete(item T) (T, bool)
  • func (t *BTree[T]) DeleteMax() (T, bool)
  • func (t *BTree[T]) DeleteMin() (T, bool)
  • func (t *BTree[T]) DeleteNearest(item T) (T, bool)
  • func (t *BTree[T]) Descend(iterator ItemIterator[T])
  • func (t *BTree[T]) DescendGreaterThan(pivot T, iterator ItemIterator[T])
  • func (t *BTree[T]) DescendLessOrEqual(pivot T, iterator ItemIterator[T])
  • func (t *BTree[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIterator[T])
  • func (t *BTree[T]) Get(key T) (_ T, _ bool)
  • func (t *BTree[T]) Has(key T) bool
  • func (t *BTree[T]) Len() int
  • func (t *BTree[T]) Max() (T, bool)
  • func (t *BTree[T]) Min() (T, bool)
  • func (t *BTree[T]) ReplaceOrInsert(item T) (_ T, _ bool)
• type FreeList
  • func NewFreeList[T Item](size int) *FreeList[T]
• type Item
• type ItemBase
  • func NewItemBase(index, size int64) ItemBase
  • func (i ItemBase) Index() int64
  • func (i ItemBase) Less(than Item) bool
  • func (i ItemBase) Size() int64
• type ItemIterator

Examples

• BTree

Constants

const DefaultFreeListSize = 32

Functions

func DefaultTargetNodeSize

func DefaultTargetNodeSize[T Item]() int

DefaultTargetNodeSize finds the degree for type T that allows items[T] to fit on a single memory page.

Types

type BTree

type BTree[T Item] struct {
	// contains filtered or unexported fields
}

BTree is a generic implementation of a B-tree.

BTree stores items of type T in an ordered structure, allowing easy insertion, removal, and iteration.

Write operations are not safe for concurrent mutation by multiple goroutines, but read operations are.

Example

tr := New[*ItemBase](*btreeDegree)
for i := 0; i < 10; i++ {
	tr.ReplaceOrInsert(&ItemBase{int64(i), int64(i)})
}
fmt.Println("len:       ", tr.Len())
v, ok := tr.Get(&ItemBase{3, 3})
fmt.Println("get3:      ", v, ok)
v, ok = tr.Get(&ItemBase{100, 100})
fmt.Println("get100:    ", v, ok)
v, ok = tr.Delete(&ItemBase{4, 4})
fmt.Println("del4:      ", v, ok)
v, ok = tr.Delete(&ItemBase{100, 100})
fmt.Println("del100:    ", v, ok)
v, ok = tr.ReplaceOrInsert(&ItemBase{5, 5})
fmt.Println("replace5:  ", v, ok)
v, ok = tr.ReplaceOrInsert(&ItemBase{100, 100})
fmt.Println("replace100:", v, ok)
v, ok = tr.Min()
fmt.Println("min:       ", v, ok)
v, ok = tr.DeleteMin()
fmt.Println("delmin:    ", v, ok)
v, ok = tr.Max()
fmt.Println("max:       ", v, ok)
v, ok = tr.DeleteMax()
fmt.Println("delmax:    ", v, ok)
fmt.Println("len:       ", tr.Len())

Output:

len:        10
get3:       &{3 3} true
get100:     <nil> false
del4:       &{4 4} true
del100:     <nil> false
replace5:   &{5 5} true
replace100: <nil> false
min:        &{0 0} true
delmin:     &{0 0} true
max:        &{100 100} true
delmax:     &{100 100} true
len:        8

func New

func New[T Item](degree int) *BTree[T]

New creates a new B-tree with the given degree.

New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items and 2-4 children).

func NewWithFreeList

func NewWithFreeList[T Item](degree int, f *FreeList[T]) *BTree[T]

NewWithFreeList creates a new B-tree that uses the given node free list.

func (*BTree[T]) Ascend

func (t *BTree[T]) Ascend(iterator ItemIterator[T])

Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.

func (*BTree[T]) AscendGreaterOrEqual

func (t *BTree[T]) AscendGreaterOrEqual(pivot T, iterator ItemIterator[T])

AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.

func (*BTree[T]) AscendLessThan

func (t *BTree[T]) AscendLessThan(pivot T, iterator ItemIterator[T])

AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until iterator returns false.

func (*BTree[T]) AscendRange

func (t *BTree[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIterator[T])

AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until iterator returns false.

func (*BTree[T]) Clear

func (t *BTree[T]) Clear(addNodesToFreelist bool)

Clear removes all items from the tree. If addNodesToFreelist is true, t's nodes are added to its freelist as part of this call, until the freelist is full. Otherwise, the root node is simply dereferenced and the subtree left to Go's normal GC processes.

This can be much faster than calling Delete on all elements, because that requires finding/removing each element in the tree and updating the tree accordingly. It also is somewhat faster than creating a new tree to replace the old one, because nodes from the old tree are reclaimed into the freelist for use by the new one, instead of being lost to the garbage collector.

This call takes:

O(1): when addNodesToFreelist is false, this is a single operation.
O(1): when the freelist is already full, it breaks out immediately
O(freelist size):  when the freelist is empty and the nodes are all owned
    by this tree, nodes are added to the freelist until full.
O(tree size):  when all nodes are owned by another tree, all nodes are
    iterated over looking for nodes to add to the freelist, and due to
    ownership, none are.

func (*BTree[T]) Clone

func (t *BTree[T]) Clone() (t2 *BTree[T])

Clone clones the tree, lazily. Clone should not be called concurrently, but the original tree (t) and the new tree (t2) can be used concurrently once the Clone call completes.

The internal tree structure of b is marked read-only and shared between t and t2. Writes to both t and t2 use copy-on-write logic, creating new nodes whenever one of b's original nodes would have been modified. Read operations should have no performance degredation. Write operations for both t and t2 will initially experience minor slow-downs caused by additional allocs and copies due to the aforementioned copy-on-write logic, but should converge to the original performance characteristics of the original tree.

func (*BTree[T]) Delete

func (t *BTree[T]) Delete(item T) (T, bool)

Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns (zeroValue, false).

func (*BTree[T]) DeleteMax

func (t *BTree[T]) DeleteMax() (T, bool)

DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns (zeroValue, false).

func (*BTree[T]) DeleteMin

func (t *BTree[T]) DeleteMin() (T, bool)

DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns (zeroValue, false).

func (*BTree[T]) DeleteNearest

func (t *BTree[T]) DeleteNearest(item T) (T, bool)

DeleteNearest removes the nearest item to the passed in item from the tree, returning it. If no such item exists, returns (zeroValue, false).

func (*BTree[T]) Descend

func (t *BTree[T]) Descend(iterator ItemIterator[T])

Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.

func (*BTree[T]) DescendGreaterThan

func (t *BTree[T]) DescendGreaterThan(pivot T, iterator ItemIterator[T])

DescendGreaterThan calls the iterator for every value in the tree within the range [last, pivot), until iterator returns false.

func (*BTree[T]) DescendLessOrEqual

func (t *BTree[T]) DescendLessOrEqual(pivot T, iterator ItemIterator[T])

DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.

func (*BTree[T]) DescendRange

func (t *BTree[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIterator[T])

DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until iterator returns false.

func (*BTree[T]) Get

func (t *BTree[T]) Get(key T) (_ T, _ bool)

Get looks for the key item in the tree, returning it. It returns (zeroValue, false) if unable to find that item.

func (*BTree[T]) Has

func (t *BTree[T]) Has(key T) bool

Has returns true if the given key is in the tree.

func (*BTree[T]) Len

func (t *BTree[T]) Len() int

Len returns the number of items currently in the tree.

func (*BTree[T]) Max

func (t *BTree[T]) Max() (T, bool)

Max returns the largest item in the tree, or (zeroValue, false) if the tree is empty.

func (*BTree[T]) Min

func (t *BTree[T]) Min() (T, bool)

Min returns the smallest item in the tree, or (zeroValue, false) if the tree is empty.

func (*BTree[T]) ReplaceOrInsert

func (t *BTree[T]) ReplaceOrInsert(item T) (_ T, _ bool)

ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned, and the second return value is true. Otherwise, (zeroValue, false).

type FreeList

type FreeList[T Item] struct {
	// contains filtered or unexported fields
}

FreeList represents a free list of BTree nodes. By default each BTree has its own FreeList, but multiple BTrees can share the same FreeList.

func NewFreeList

func NewFreeList[T Item](size int) *FreeList[T]

NewFreeList creates a new free list. size is the maximum size of the returned free list.

type Item

type Item interface {
	// Index provides a primitive to identify a particular item in the tree.
	Index() int64

	// Size provides a primitive for the user-defined relative size of the item.
	Size() int64

	// Less tests whether the current item is less than the given argument.
	//
	// This must provide a strict weak ordering; if !a.Less(b) && !b.Less(a),
	// we treat this to mean a == b (i.e., we can only hold one of either a or b
	// in the tree).
	Less(than Item) bool
}

Item represents a single object in the tree. All implementations must embed ItemBase for forward compatibility.

type ItemBase

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

ItemBase meets the minimum requirements for identifying the item.

func NewItemBase

func NewItemBase(index, size int64) ItemBase

NewItemBase creates a new base item with the given arguments.

func (ItemBase) Index

func (i ItemBase) Index() int64

Index returns the index of the item.

func (ItemBase) Less

func (i ItemBase) Less(than Item) bool

Less tests whether the current item is less than the given argument.

func (ItemBase) Size

func (i ItemBase) Size() int64

Size returns the relative size of the item.

type ItemIterator

type ItemIterator[T Item] func(item T) bool

ItemIterator allows callers of {A/De}scend* to iterate in-order over portions of the tree. When this function returns false, iteration will stop and the associated {A/De}scend* function will immediately return.