gkvdb: github.com/johng-cn/gkvdb/gkvdb/gbtree Index | Examples | Files

package gbtree

import "github.com/johng-cn/gkvdb/gkvdb/gbtree"

B-Tree

Index

Examples

Package Files

gbtree.go

Constants

const (
    DefaultFreeListSize = 32
)

type BTree Uses

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.

Code:

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 Uses

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 Uses

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

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

func (*BTree) Ascend Uses

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 Uses

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 Uses

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 Uses

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) Clone Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

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

func (*BTree) Len Uses

func (t *BTree) Len() int

Len returns the number of items currently in the tree.

func (*BTree) Max Uses

func (t *BTree) Max() Item

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

func (*BTree) Min Uses

func (t *BTree) Min() Item

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

func (*BTree) ReplaceOrInsert Uses

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 FreeList Uses

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

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 Uses

func NewFreeList(size int) *FreeList

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

type Int Uses

type Int int

Int implements the Item interface for integers.

func (Int) Less Uses

func (a Int) Less(b Item) bool

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

type Item Uses

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 Uses

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.

Package gbtree imports 5 packages (graph). Updated 2018-04-17. Refresh now. Tools for package owners.