b: modernc.org/b Index | Files | Directories

package b

import "modernc.org/b"

Package b implements the B+tree flavor of a BTree.

Changelog

2016-07-16: Update benchmark results to newer Go version. Add a note on concurrency.

2014-06-26: Lower GC presure by recycling things.

2014-04-18: Added new method Put.

Concurrency considerations

Tree.{Clear,Delete,Put,Set} mutate the tree. One can use eg. a sync.Mutex.Lock/Unlock (or sync.RWMutex.Lock/Unlock) to wrap those calls if they are to be invoked concurrently.

Tree.{First,Get,Last,Len,Seek,SeekFirst,SekLast} read but do not mutate the tree. One can use eg. a sync.RWMutex.RLock/RUnlock to wrap those calls if they are to be invoked concurrently with any of the tree mutating methods.

Enumerator.{Next,Prev} mutate the enumerator and read but not mutate the tree. One can use eg. a sync.RWMutex.RLock/RUnlock to wrap those calls if they are to be invoked concurrently with any of the tree mutating methods. A separate mutex for the enumerator, or the whole tree in a simplified variant, is necessary if the enumerator's Next/Prev methods per se are to be invoked concurrently.

Generic types

Keys and their associated values are interface{} typed, similar to all of the containers in the standard library.

Semiautomatic production of a type specific variant of this package is supported via

$ make generic

This command will write to stdout a version of the btree.go file where every key type occurrence is replaced by the word 'KEY' and every value type occurrence is replaced by the word 'VALUE'. Then you have to replace these tokens with your desired type(s), using any technique you're comfortable with.

This is how, for example, 'example/int.go' was created:

$ mkdir example
$ make generic | sed -e 's/KEY/int/g' -e 's/VALUE/int/g' > example/int.go

No other changes to int.go are necessary, it compiles just fine.

Running the benchmarks for 1000 keys on a machine with Intel i5-4670 CPU @ 3.4GHz, Go 1.7rc1.

$ go test -bench 1e3 example/all_test.go example/int.go
BenchmarkSetSeq1e3-4    	   20000	     78265 ns/op
BenchmarkGetSeq1e3-4    	   20000	     67980 ns/op
BenchmarkSetRnd1e3-4    	   10000	    172720 ns/op
BenchmarkGetRnd1e3-4    	   20000	     89539 ns/op
BenchmarkDelSeq1e3-4    	   20000	     87863 ns/op
BenchmarkDelRnd1e3-4    	   10000	    130891 ns/op
BenchmarkSeekSeq1e3-4   	   10000	    100118 ns/op
BenchmarkSeekRnd1e3-4   	   10000	    121684 ns/op
BenchmarkNext1e3-4      	  200000	      6330 ns/op
BenchmarkPrev1e3-4      	  200000	      9066 ns/op
PASS
ok  	command-line-arguments	42.531s
$

Index

Package Files

btree.go doc.go nop_inst.go

type Cmp Uses

type Cmp func(a, b interface{}) int

Cmp compares a and b. Return value is:

< 0 if a <  b
  0 if a == b
> 0 if a >  b

type Enumerator Uses

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

Enumerator captures the state of enumerating a tree. It is returned from the Seek* methods. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration at the proper key, if possible.

However, once an Enumerator returns io.EOF to signal "no more items", it does no more attempt to "resync" on tree mutation(s). In other words, io.EOF from an Enumerator is "sticky" (idempotent).

func (*Enumerator) Close Uses

func (e *Enumerator) Close()

Close recycles e to a pool for possible later reuse. No references to e should exist or such references must not be used afterwards.

func (*Enumerator) Next Uses

func (e *Enumerator) Next() (k interface{}, v interface{}, err error)

Next returns the currently enumerated item, if it exists and moves to the next item in the key collation order. If there is no item to return, err == io.EOF is returned.

func (*Enumerator) Prev Uses

func (e *Enumerator) Prev() (k interface{}, v interface{}, err error)

Prev returns the currently enumerated item, if it exists and moves to the previous item in the key collation order. If there is no item to return, err == io.EOF is returned.

type Tree Uses

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

Tree is a B+tree.

func TreeNew Uses

func TreeNew(cmp Cmp) *Tree

TreeNew returns a newly created, empty Tree. The compare function is used for key collation.

func (*Tree) Clear Uses

func (t *Tree) Clear()

Clear removes all K/V pairs from the tree.

func (*Tree) Close Uses

func (t *Tree) Close()

Close performs Clear and recycles t to a pool for possible later reuse. No references to t should exist or such references must not be used afterwards.

func (*Tree) Delete Uses

func (t *Tree) Delete(k interface{}) (ok bool)

Delete removes the k's KV pair, if it exists, in which case Delete returns true.

func (*Tree) First Uses

func (t *Tree) First() (k interface{}, v interface{})

First returns the first item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*Tree) Get Uses

func (t *Tree) Get(k interface{}) (v interface{}, ok bool)

Get returns the value associated with k and true if it exists. Otherwise Get returns (zero-value, false).

func (*Tree) Last Uses

func (t *Tree) Last() (k interface{}, v interface{})

Last returns the last item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*Tree) Len Uses

func (t *Tree) Len() int

Len returns the number of items in the tree.

func (*Tree) Put Uses

func (t *Tree) Put(k interface{}, upd func(oldV interface{}, exists bool) (newV interface{}, write bool)) (oldV interface{}, written bool)

Put combines Get and Set in a more efficient way where the tree is walked only once. The upd(ater) receives (old-value, true) if a KV pair for k exists or (zero-value, false) otherwise. It can then return a (new-value, true) to create or overwrite the existing value in the KV pair, or (whatever, false) if it decides not to create or not to update the value of the KV pair.

tree.Set(k, v) call conceptually equals calling

tree.Put(k, func(interface{} /*K*/, bool){ return v, true })

modulo the differing return values.

func (*Tree) Seek Uses

func (t *Tree) Seek(k interface{}) (e *Enumerator, ok bool)

Seek returns an Enumerator positioned on an item such that k >= item's key. ok reports if k == item.key The Enumerator's position is possibly after the last item in the tree.

func (*Tree) SeekFirst Uses

func (t *Tree) SeekFirst() (e *Enumerator, err error)

SeekFirst returns an enumerator positioned on the first KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*Tree) SeekLast Uses

func (t *Tree) SeekLast() (e *Enumerator, err error)

SeekLast returns an enumerator positioned on the last KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*Tree) Set Uses

func (t *Tree) Set(k interface{}, v interface{})

Set sets the value associated with k.

Directories

PathSynopsis
example

Package b imports 3 packages (graph) and is imported by 1 packages. Updated 2019-08-18. Refresh now. Tools for package owners.