btree
package
This package is not in the latest version of its module.
Details
Validgo.mod file
The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
- Redistributable license
Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
- Tagged version
Modules with tagged versions give importers more predictable builds.
Stable versionWhen a project reaches major version v1 it is considered stable.
- Learn more about best practices
Repository
Links
Open Source Insights
README¶
This package is a fork of github.com/jba/btree at commitd4edd57f39b8425fc2c631047ff4dc6024d82a4f, which itself was a fork ofgithub.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), andmuch of the code is taken from there. But the API has been changed significantly,particularly around iteration, and support for indexing by position has beenadded.
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-Treeimplementation 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 causeefficiency differences when compared to equivalent C++ template code thatstores values in arrays within the node:
- Due to the overhead of storing values as interfaces (eachvalue needs to be stored as the value itself, then 2 words for theinterface pointing to that value and its type), resulting in highermemory use.
- Since interfaces can point to values anywhere in memory, values aremost likely not stored in contiguous blocks, resulting in a highernumber of cache misses.
These issues don't tend to matter, though, when working with strings or otherheap-allocated structures, since C++-equivalent structures also must storepointers and also distribute their values across the heap.
Index¶
- type 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)
- func (t *BTree) SetWithIndex(k Key, v Value) (old Value, present bool, index int)
- type Iterator
- type Key
- type Value
Constants¶
This section is empty.
Variables¶
This section is empty.
Functions¶
This section is empty.
Types¶
typeBTree¶
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 multiplegoroutines, but Read operations are.
funcNew¶
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 itemsand 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 treecan hold only one of a or b).
func (*BTree)After¶
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¶
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¶
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¶
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¶
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¶
Clone clones the btree, lazily. Clone should not be called concurrently,but the original tree (t) and the new tree (t2) can be used concurrentlyonce the Clone call completes.
The internal tree structure of b is marked read-only and shared between t andt2. Writes to both t and t2 use copy-on-write logic, creating new nodeswhenever one of b's original nodes would have been modified. Read operationsshould have no performance degredation. Write operations for both t and t2will initially experience minor slow-downs caused by additional allocs andcopies due to the aforementioned copy-on-write logic, but should converge tothe original performance characteristics of the original tree.
func (*BTree)Delete¶
Delete removes the item with the given key, returning its value. The second return valuereports whether the key was found.
func (*BTree)DeleteMax¶
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¶
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¶
Get returns the value for the given key in the tree, or the zero value if thekey is not in the tree.
To distinguish a zero value from a key that is not present, use GetWithIndex.
func (*BTree)GetWithIndex¶
GetWithIndex returns the value and index for the given key in the tree, or thezero value and -1 if the key is not in the tree.
func (*BTree)Max¶
Max returns the largest key in the tree and its value. If the tree is empty, bothreturn values are zero values.
func (*BTree)Min¶
Min returns the smallest key in the tree and its value. If the tree is empty, itreturns zero values.
typeIterator¶
type Iterator struct {KeyKeyValueValue// Index is the position of the item in the tree viewed as a sequence.// The minimum item has index zero.Indexint// contains filtered or unexported fields}An Iterator supports traversing the items in the tree.
func (*Iterator)Next¶
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 returnsfalse, 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.
Source Files