btree

README

Usual variable name abbreviations

b - builder bt - btree it, iter - iterator nd - node ni - node iterator off - offset (uint64) pos - position sb - strings.Builder sep - separator st - state st - stor.Stor

Documentation

Overview

Example (Merge_split)

var b nodeBuilder
b.Add("1234xxxx", 1234, 1)
b.Add("1235xxxx", 1235, 1)
b.Add("1299xxxx", 1299, 1)
b.Add("1300xxxx", 1300, 1)
b.Add("1305xxxx", 1305, 1)
m := merge{node: b.node, modified: true}
left, right, splitKey := m.split(b.node.Size())
fmt.Println("splitKey", splitKey)
fmt.Println("LEFT ---")
left.print()
fmt.Println("RIGHT ---")
right.print()

Output:

splitKey 129
LEFT ---
1234 ''
1235 1235
RIGHT ---
1299 ''
1300 13
1305 1305

Example (Node_BuilderSplit)

var b nodeBuilder
b.Add("1234xxxx", 1234, 1)
b.Add("1235xxxx", 1235, 1)
b.Add("1299xxxx", 1299, 1)
b.Add("1300xxxx", 1300, 1)
b.Add("1305xxxx", 1305, 1)
st := stor.HeapStor(8192)
leftOff, splitKey := b.Split(st)
// assert.T(t).This(splitKey).Is("13")
fmt.Println("splitKey", splitKey)
fmt.Println("LEFT ---")
readNode(st, leftOff).print()
fmt.Println("RIGHT ---")
b.node.print()

Output:

splitKey 13
LEFT ---
1234 ''
1235 1235
1299 129
RIGHT ---
1300 ''
1305 1305

Index

• Constants
• Variables
• func Builder(st *stor.Stor) *builder
• func CreateBtree(st *stor.Stor, is *ixkey.Spec) *btree
• func OpenBtree(st *stor.Stor, root uint64, treeLevels int) *btree
• func Read(st *stor.Stor, r *stor.Reader) *btree
• type Iterator
  • func (it *Iterator) Cur() (string, uint64)
  • func (it *Iterator) Eof() bool
  • func (it *Iterator) Modified() bool
  • func (it *Iterator) Next()
  • func (it *Iterator) Prev()
  • func (it *Iterator) Range(rng Range)
  • func (it *Iterator) Rewind()
  • func (it *Iterator) Seek(key string)
  • func (it *Iterator) SeekAll(key string)
• type Range
• type Stats
  • func (stats Stats) String() string
• type T

Examples

• Package (Merge_split)
• Package (Node_BuilderSplit)

Constants

const EntrySize = 10

EntrySize is the estimated average entry size

const MinSplitSize = 6 // for builder that will be split 4 and 2

const TreeHeight = 3

TreeHeight is the estimated average tree height. It is used by Table.lookupCost

Variables

var Fanout = MaxNodeSize / EntrySize // estimate

var GetLeafKey func(st *stor.Stor, is *ixkey.Spec, off uint64) string

GetLeafKey is used to get the key for a data offset. It is a dependency that must be injected

var MaxNodeSize = 1024

MaxNodeSize is the maximum node size in bytes, split if larger. var rather than const because it is overridden by tests.

Functions

func Builder

func Builder(st *stor.Stor) *builder

func CreateBtree

func CreateBtree(st *stor.Stor, is *ixkey.Spec) *btree

func OpenBtree

func OpenBtree(st *stor.Stor, root uint64, treeLevels int) *btree

func Read

func Read(st *stor.Stor, r *stor.Reader) *btree

Types

type Iterator

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

Iterator is a Suneido style iterator with Next/Prev/Rewind

func (*Iterator) Cur

func (it *Iterator) Cur() (string, uint64)

func (*Iterator) Eof

func (it *Iterator) Eof() bool

func (*Iterator) Modified

func (it *Iterator) Modified() bool

func (*Iterator) Next

func (it *Iterator) Next()

func (*Iterator) Prev

func (it *Iterator) Prev()

func (*Iterator) Range

func (it *Iterator) Range(rng Range)

func (*Iterator) Rewind

func (it *Iterator) Rewind()

func (*Iterator) Seek

func (it *Iterator) Seek(key string)

func (*Iterator) SeekAll

func (it *Iterator) SeekAll(key string)

type Range

type Range = iterator.Range

type Stats

type Stats struct {
	Levels  int
	Count   int
	Size    int
	Nnodes  int
	RootN   int
	Fan     int
	NodeFan [8]int
}

func (Stats) String

func (stats Stats) String() string

type T

type T = btree