btree

README

This package is a fork of github.com/jba/btree at commit aa53f88384b4d43de7e047ebe8d2c0fbb84fce89, which itself was a fork of github.com/google/btree at 316fb6d3f031ae8f4d457c6c5186b9e3ded70435.

This directory makes the following modifications:

• Updated copyright notice.
• removed LICENSE (it is the same as the repo-wide license, Apache 2.0)
• Removed examples_test.go and .travis.yml.
• Added this file.

Documentation

Overview

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

This implementation is based on google/btree (http://github.com/google/btree), and much of the code is taken from there. But the API has been changed significantly, particularly around iteration, and support for indexing by position has been added.

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.

Index

• type BTree
  • func New(degree int, less func(interface{}, interface{}) bool) *BTree
  • func (t *BTree) After(k Key) *Iterator
  • func (t *BTree) AfterIndex(i int) *Iterator
  • func (t *BTree) At(i int) (Key, Value)
  • func (t *BTree) Before(k Key) *Iterator
  • func (t *BTree) BeforeIndex(i int) *Iterator
  • func (t *BTree) Clone() *BTree
  • func (t *BTree) Delete(k Key) (Value, bool)
  • func (t *BTree) DeleteMax() (Key, Value)
  • func (t *BTree) DeleteMin() (Key, Value)
  • func (t *BTree) Get(k Key) Value
  • func (t *BTree) GetWithIndex(k Key) (Value, int)
  • func (t *BTree) Has(k Key) bool
  • func (t *BTree) Len() int
  • func (t *BTree) Max() (Key, Value)
  • func (t *BTree) Min() (Key, Value)
  • func (t *BTree) Set(k Key, v Value) (old Value, present bool)
• type Iterator
  • func (it *Iterator) Next() bool
• type Key
• type Value

Types

type BTree

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

BTree is an implementation of a B-Tree.

BTree stores item instances 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.

func New

func New(degree int, less func(interface{}, interface{}) bool) *BTree

New creates a new B-Tree with the given degree and comparison function.

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

The less function tests whether the current item is less than the given argument. It must provide a strict weak ordering. If !less(a, b) && !less(b, a), we treat this to mean a == b (i.e. the tree can hold only one of a or b).

func (*BTree) After

func (t *BTree) After(k Key) *Iterator

After returns an iterator positioned just after k. After the first call to Next, the Iterator will be at k, or at the key just less than k if k is not in the tree. Subsequent calls to Next will traverse the tree's items in descending order.

func (*BTree) AfterIndex

func (t *BTree) AfterIndex(i int) *Iterator

AfterIndex returns an iterator positioned just after the item with the given index. The iterator will traverse the tree's items in descending order. If i is not in the range [0, tr.Len()], AfterIndex panics. Note that it is not an error to provide an index of tr.Len().

func (*BTree) At

func (t *BTree) At(i int) (Key, Value)

At returns the key and value at index i. The minimum item has index 0. If i is outside the range [0, t.Len()), At panics.

func (*BTree) Before

func (t *BTree) Before(k Key) *Iterator

Before returns an iterator positioned just before k. After the first call to Next, the Iterator will be at k, or at the key just greater than k if k is not in the tree. Subsequent calls to Next will traverse the tree's items in ascending order.

func (*BTree) BeforeIndex

func (t *BTree) BeforeIndex(i int) *Iterator

BeforeIndex returns an iterator positioned just before the item with the given index. The iterator will traverse the tree's items in ascending order. If i is not in the range [0, tr.Len()], BeforeIndex panics. Note that it is not an error to provide an index of tr.Len().

func (*BTree) Clone

func (t *BTree) Clone() *BTree

Clone clones the btree, 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) Delete

func (t *BTree) Delete(k Key) (Value, bool)

Delete removes the item with the given key, returning its value. The second return value reports whether the key was found.

func (*BTree) DeleteMax

func (t *BTree) DeleteMax() (Key, Value)

DeleteMax removes the largest item in the tree and returns its key and value. If the tree is empty, it returns zero values.

func (*BTree) DeleteMin

func (t *BTree) DeleteMin() (Key, Value)

DeleteMin removes the smallest item in the tree and returns its key and value. If the tree is empty, it returns zero values.

func (*BTree) Get

func (t *BTree) Get(k Key) Value

Get returns the value for the given key in the tree, or the zero value if the key is not in the tree.

To distinguish a zero value from a key that is not present, use GetWithIndex.

func (*BTree) GetWithIndex

func (t *BTree) GetWithIndex(k Key) (Value, int)

GetWithIndex returns the value and index for the given key in the tree, or the zero value and -1 if the key is not in the tree.

func (*BTree) Has

func (t *BTree) Has(k Key) bool

Has reports whether the given key is in the tree.

func (*BTree) Len

func (t *BTree) Len() int

Len returns the number of items currently in the tree.

func (*BTree) Max

func (t *BTree) Max() (Key, Value)

Max returns the largest key in the tree and its value. If the tree is empty, both return values are zero values.

func (*BTree) Min

func (t *BTree) Min() (Key, Value)

Min returns the smallest key in the tree and its value. If the tree is empty, it returns zero values.

func (*BTree) Set

func (t *BTree) Set(k Key, v Value) (old Value, present bool)

Set sets the given key to the given value in the tree. If the key is present in the tree, its value is changed and the old value is returned along with a second return value of true. If the key is not in the tree, it is added, and the second return value is false.

type Iterator

type Iterator struct {
	Key   Key
	Value Value
	// Index is the position of the item in the tree viewed as a sequence.
	// The minimum item has index zero.
	Index int
	// contains filtered or unexported fields
}

An Iterator supports traversing the items in the tree.

func (*Iterator) Next

func (it *Iterator) Next() bool

Next advances the Iterator to the next item in the tree. If Next returns true, the Iterator's Key, Value and Index fields refer to the next item. If Next returns false, there are no more items and the values of Key, Value and Index are undefined.

If the tree is modified during iteration, the behavior is undefined.

type Key

type Key interface{}

Key represents a key into the tree.

type Value

type Value interface{}