README
¶
PairTree
BTree implementation for Go
This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure.
This is a fork of the google/btree package which uses tidwall/pair as items.
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 ¶
- type Cursor
- type PairTree
- func (t *PairTree) Ascend(iterator func(item pair.Pair) bool)
- func (t *PairTree) AscendGreaterOrEqual(pivot pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) AscendLessThan(pivot pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) AscendRange(greaterOrEqual, lessThan pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) Clone() (t2 *PairTree)
- func (t *PairTree) Cursor() *Cursor
- func (t *PairTree) Delete(item pair.Pair) pair.Pair
- func (t *PairTree) DeleteMax() pair.Pair
- func (t *PairTree) DeleteMin() pair.Pair
- func (t *PairTree) Descend(iterator func(item pair.Pair) bool)
- func (t *PairTree) DescendGreaterThan(pivot pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) DescendLessOrEqual(pivot pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) DescendRange(lessOrEqual, greaterThan pair.Pair, iterator func(item pair.Pair) bool)
- func (t *PairTree) Get(key pair.Pair) pair.Pair
- func (t *PairTree) Has(key pair.Pair) bool
- func (t *PairTree) Len() int
- func (t *PairTree) Max() pair.Pair
- func (t *PairTree) Min() pair.Pair
- func (t *PairTree) ReplaceOrInsert(item pair.Pair) pair.Pair
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cursor ¶
type Cursor struct {
// contains filtered or unexported fields
}
Cursor represents an iterator that can traverse over all items in the tree in sorted order.
Changing data while traversing a cursor may result in unexpected items to be returned. You must reposition your cursor after mutating data.
type PairTree ¶
type PairTree struct {
// contains filtered or unexported fields
}
PairTree is an implementation of a B-Tree.
PairTree stores Pair 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 ¶
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 (*PairTree) Ascend ¶
Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.
func (*PairTree) AscendGreaterOrEqual ¶
AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.
func (*PairTree) AscendLessThan ¶
AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until iterator returns false.
func (*PairTree) AscendRange ¶
func (t *PairTree) AscendRange(greaterOrEqual, lessThan pair.Pair, iterator func(item pair.Pair) bool)
AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until iterator returns false.
func (*PairTree) Clone ¶
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 (*PairTree) Delete ¶
Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns nil.
func (*PairTree) DeleteMax ¶
DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns nil.
func (*PairTree) DeleteMin ¶
DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns nil.
func (*PairTree) Descend ¶
Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.
func (*PairTree) DescendGreaterThan ¶
DescendGreaterThan calls the iterator for every value in the tree within the range (pivot, last], until iterator returns false.
func (*PairTree) DescendLessOrEqual ¶
DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.
func (*PairTree) DescendRange ¶
func (t *PairTree) DescendRange(lessOrEqual, greaterThan pair.Pair, iterator func(item pair.Pair) bool)
DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until iterator returns false.
func (*PairTree) Get ¶
Get looks for the key item in the tree, returning it. It returns nil if unable to find that item.
func (*PairTree) ReplaceOrInsert ¶
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).
Source Files