btree

package module
v1.1.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 21, 2024 License: Apache-2.0 Imports: 5 Imported by: 2,018

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 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.

There are two implementations; those suffixed with 'G' are generics, usable for any type, and require a passed-in "less" function to define their ordering. Those without this prefix are specific to the 'Item' interface, and use its 'Less' function for ordering.

Index

Examples

Constants

View Source 
const (
	DefaultFreeListSize = 32
)

Variables

This section is empty.

Functions

This section is empty.

Types

type BTree 

type BTree BTreeG[Item]

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("min:       ", tr.Min())
fmt.Println("delmin:    ", tr.DeleteMin())
fmt.Println("max:       ", tr.Max())
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>
min:        0
delmin:     0
max:        100
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 NewWithFreeList 

func NewWithFreeList(degree int, f *FreeList) *BTree

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

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) Clear 

func (t *BTree) Clear(addNodesToFreelist bool)

Clear removes all items from the btree. 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) Clone 

func (t *BTree) Clone() (t2 *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(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) Descend 

func (t *BTree) Descend(iterator ItemIterator)

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

func (*BTree) DescendGreaterThan 

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

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

func (*BTree) DescendLessOrEqual 

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

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

func (*BTree) DescendRange 

func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator)

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

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) Max 

func (t *BTree) Max() Item

Max returns the largest item in the tree, or nil if the tree is empty.

func (*BTree) Min 

func (t *BTree) Min() Item

Min returns the smallest item in the tree, or nil if the tree is empty.

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 BTreeG added in v1.1.0 

type BTreeG[T any] struct {
	// contains filtered or unexported fields
}

BTreeG is a generic implementation of a B-Tree.

BTreeG 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 := NewOrderedG[int](*btreeDegree)
for i := 0; i < 10; i++ {
	tr.ReplaceOrInsert(i)
}
fmt.Println("len:       ", tr.Len())
v, ok := tr.Get(3)
fmt.Println("get3:      ", v, ok)
v, ok = tr.Get(100)
fmt.Println("get100:    ", v, ok)
v, ok = tr.Delete(4)
fmt.Println("del4:      ", v, ok)
v, ok = tr.Delete(100)
fmt.Println("del100:    ", v, ok)
v, ok = tr.ReplaceOrInsert(5)
fmt.Println("replace5:  ", v, ok)
v, ok = tr.ReplaceOrInsert(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 true
get100:     0 false
del4:       4 true
del100:     0 false
replace5:   5 true
replace100: 0 false
min:        0 true
delmin:     0 true
max:        100 true
delmax:     100 true
len:        8

func NewG added in v1.1.0 

func NewG[T any](degree int, less LessFunc[T]) *BTreeG[T]

NewG creates a new B-Tree with the given degree.

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

The passed-in LessFunc determines how objects of type T are ordered.

func NewOrderedG added in v1.1.0 

func NewOrderedG[T Ordered](degree int) *BTreeG[T]

NewOrderedG creates a new B-Tree for ordered types.

func NewWithFreeListG added in v1.1.0 

func NewWithFreeListG[T any](degree int, less LessFunc[T], f *FreeListG[T]) *BTreeG[T]

NewWithFreeListG creates a new B-Tree that uses the given node free list.

func (*BTreeG[T]) Ascend added in v1.1.0 

func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T])

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

func (*BTreeG[T]) AscendGreaterOrEqual added in v1.1.0 

func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) AscendLessThan added in v1.1.0 

func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) AscendRange added in v1.1.0 

func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) Clear added in v1.1.0 

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

Clear removes all items from the btree. 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 (*BTreeG[T]) Clone added in v1.1.0 

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

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 (*BTreeG[T]) Delete added in v1.1.0 

func (t *BTreeG[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 (*BTreeG[T]) DeleteMax added in v1.1.0 

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

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

func (*BTreeG[T]) DeleteMin added in v1.1.0 

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

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

func (*BTreeG[T]) Descend added in v1.1.0 

func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T])

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

func (*BTreeG[T]) DescendGreaterThan added in v1.1.0 

func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) DescendLessOrEqual added in v1.1.0 

func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) DescendRange added in v1.1.0 

func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T])

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

func (*BTreeG[T]) Get added in v1.1.0 

func (t *BTreeG[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 (*BTreeG[T]) Has added in v1.1.0 

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

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

func (*BTreeG[T]) Len added in v1.1.0 

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

Len returns the number of items currently in the tree.

func (*BTreeG[T]) Max added in v1.1.0 

func (t *BTreeG[T]) Max() (_ T, _ bool)

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

func (*BTreeG[T]) Min added in v1.1.0 

func (t *BTreeG[T]) Min() (_ T, _ bool)

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

func (*BTreeG[T]) ReplaceOrInsert added in v1.1.0 

func (t *BTreeG[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)

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

type FreeList 

type FreeList FreeListG[Item]

FreeList represents a free list of btree nodes. By default each BTree has its own FreeList, but multiple BTrees can share the same FreeList. Two Btrees using the same freelist are safe for concurrent write access.

func NewFreeList 

func NewFreeList(size int) *FreeList

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

type FreeListG added in v1.1.0 

type FreeListG[T any] struct {
	// contains filtered or unexported fields
}

FreeListG represents a free list of btree nodes. By default each BTree has its own FreeList, but multiple BTrees can share the same FreeList, in particular when they're created with Clone. Two Btrees using the same freelist are safe for concurrent write access.

func NewFreeListG added in v1.1.0 

func NewFreeListG[T any](size int) *FreeListG[T]

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

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 ItemIteratorG[Item]

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.

type ItemIteratorG added in v1.1.0 

type ItemIteratorG[T any] func(item T) bool

ItemIteratorG 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 Ascend* function will immediately return.

type LessFunc added in v1.1.0 

type LessFunc[T any] func(a, b T) bool

LessFunc[T] determines how to order a type 'T'. It should implement a strict ordering, and should return true if within that ordering, 'a' < 'b'.

func Less added in v1.1.0 

func Less[T Ordered]() LessFunc[T]

Less[T] returns a default LessFunc that uses the '<' operator for types that support it.

type Ordered added in v1.1.0 

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string
}

Ordered represents the set of types for which the '<' operator work.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.