btree

README

BTree implementation for Go

This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure.

The API is based off of the wonderful http://godoc.org/github.com/petar/GoLLRB/llrb, and is meant to allow btree to act as a drop-in replacement for gollrb trees.

See http://godoc.org/github.com/google/btree for documentation.

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 implmentation 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 or backwards iteration.

Index

• type BTree
  • func New(degree int) *BTree
  • func (t *BTree) Ascend(iterator ItemIterator)
  • func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)
  • func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator)
  • func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator)
  • func (t *BTree) Delete(item Item) Item
  • func (t *BTree) DeleteMax() Item
  • func (t *BTree) DeleteMin() Item
  • func (t *BTree) Get(key Item) Item
  • func (t *BTree) Has(key Item) bool
  • func (t *BTree) Len() int
  • func (t *BTree) ReplaceOrInsert(item Item) Item
• type Int
  • func (a Int) Less(b Item) bool
• type Item
• type ItemIterator

Examples

• BTree

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.

Example

tr := New(*btreeDegree)
for i := Int(0); i < 10; i++ {
	tr.ReplaceOrInsert(i)
}
fmt.Println("len:       ", tr.Len())
fmt.Println("get3:      ", tr.Get(Int(3)))
fmt.Println("get100:    ", tr.Get(Int(100)))
fmt.Println("del4:      ", tr.Delete(Int(4)))
fmt.Println("del100:    ", tr.Delete(Int(100)))
fmt.Println("replace5:  ", tr.ReplaceOrInsert(Int(5)))
fmt.Println("replace100:", tr.ReplaceOrInsert(Int(100)))
fmt.Println("delmin:    ", tr.DeleteMin())
fmt.Println("delmax:    ", tr.DeleteMax())
fmt.Println("len:       ", tr.Len())

Output:

len:        10
get3:       3
get100:     <nil>
del4:       4
del100:     <nil>
replace5:   5
replace100: <nil>
delmin:     0
delmax:     100
len:        8

func New

func New(degree int) *BTree

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 (*BTree) Ascend

func (t *BTree) Ascend(iterator ItemIterator)

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

func (*BTree) AscendGreaterOrEqual

func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)

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

func (*BTree) AscendLessThan

func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator)

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

func (*BTree) AscendRange

func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator)

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

func (*BTree) Delete

func (t *BTree) Delete(item Item) Item

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

func (*BTree) DeleteMax

func (t *BTree) DeleteMax() Item

DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns nil.

func (*BTree) DeleteMin

func (t *BTree) DeleteMin() Item

DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns nil.

func (*BTree) Get

func (t *BTree) Get(key Item) Item

Get looks for the key item in the tree, returning it. It returns nil if unable to find that item.

func (*BTree) Has

func (t *BTree) Has(key Item) bool

Has returns true if 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) ReplaceOrInsert

func (t *BTree) ReplaceOrInsert(item Item) Item

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. Otherwise, nil is returned.

nil cannot be added to the tree (will panic).

type Int

type Int int

Int implements the Item interface for integers.

func (Int) Less

func (a Int) Less(b Item) bool

Less returns true if int(a) < int(b).

type Item

type Item interface {
	// 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.

type ItemIterator

type ItemIterator func(i Item) bool

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