newtree

Documentation

Overview

A generalized search tree (GiST) implementation with some modifications from the original algorithm. This implementation is based around a Fixed-Sized Page allocation, and a split algorithm with strong page-limitations.

Unlike other GiST implementations, this one is designed to be a Table rather than just an Index.

The GiST paper: http://db.cs.berkeley.edu/papers/vldb95-gist.pdf

Index

• Constants
• Variables
• type Element
  • func (e *Element) BinDecode(b []byte) ([]byte, error)
  • func (e Element) BinEncode(b []byte) (int, error)
  • func (e Element) Length() int
  • func (e Element) String() string
• type Elements
  • func (e *Elements) BinDecode(b []byte) ([]byte, error)
  • func (e Elements) BinEncode(b []byte) (int, error)
  • func (e Elements) IsLeaf() bool
  • func (e Elements) IsNode() bool
  • func (e Elements) Length() int
  • func (e Elements) String() string
• type IBase
• type ReadAlloc
  • func (r *ReadAlloc) HeadAlloc() (int64, error)
  • func (r *ReadAlloc) HeadFree(id int64) error
  • func (r *ReadAlloc) HeadRead(id int64) (b bufferex.Binary, e error)
  • func (r *ReadAlloc) HeadWrite(id int64, b []byte) error
  • func (r *ReadAlloc) Page() int
  • func (r *ReadAlloc) PageAlloc() (int64, error)
  • func (r *ReadAlloc) PageFree(id int64) error
  • func (r *ReadAlloc) PageRead(id int64) (b bufferex.Binary, e error)
  • func (r *ReadAlloc) PageWrite(id int64, b []byte) error
• type Root
  • func (r *Root) BinDecode(b []byte) error
  • func (r Root) BinEncode(b []byte) error
• type Tree
  • func (t *Tree) Delete(ctx context.Context, obj int64, q interface{}, chk func([]byte) bool) (r_abort, r_err error)
  • func (t *Tree) GSearch(ctx context.Context, obj int64, q interface{}, consume func(b []byte) bool) error
  • func (t *Tree) Insert(obj int64, nitem []byte) error
  • func (t *Tree) NewRoot() (int64, error)
  • func (t *Tree) Search(ctx context.Context, obj int64, q interface{}, consumer func([]byte)) error
• type TreeOps
• type WriteAlloc
  • func (r *WriteAlloc) HeadAlloc() (int64, error)
  • func (r *WriteAlloc) HeadFree(id int64) error
  • func (r *WriteAlloc) HeadWrite(id int64, b []byte) error
  • func (r *WriteAlloc) PageAlloc() (int64, error)
  • func (r *WriteAlloc) PageFree(id int64) error
  • func (r *WriteAlloc) PageWrite(id int64, b []byte) error

Constants

const HeadSize = 16

Variables

var EReadOnly = errors.New("EReadOnly")

var EShort = errors.New("Too short")

Types

type Element

type Element struct {
	Val []byte
	Ptr int64
	Tmp interface{}
}

func (*Element) BinDecode

func (e *Element) BinDecode(b []byte) ([]byte, error)

func (Element) BinEncode

func (e Element) BinEncode(b []byte) (int, error)

func (Element) Length

func (e Element) Length() int

func (Element) String

func (e Element) String() string

type Elements

type Elements []Element

func (*Elements) BinDecode

func (e *Elements) BinDecode(b []byte) ([]byte, error)

func (Elements) BinEncode

func (e Elements) BinEncode(b []byte) (int, error)

func (Elements) IsLeaf

func (e Elements) IsLeaf() bool

func (Elements) IsNode

func (e Elements) IsNode() bool

func (Elements) Length

func (e Elements) Length() int

func (Elements) String

func (e Elements) String() string

type IBase

type IBase interface {
	Page() int
	PageAlloc() (int64, error)
	PageRead(id int64) (bufferex.Binary, error)
	PageWrite(id int64, b []byte) error
	PageFree(id int64) error
	HeadAlloc() (int64, error)
	HeadRead(id int64) (bufferex.Binary, error)
	HeadWrite(id int64, b []byte) error
	HeadFree(id int64) error
}

type ReadAlloc

type ReadAlloc struct {
	P int
	F file.File
}

func (*ReadAlloc) HeadAlloc

func (r *ReadAlloc) HeadAlloc() (int64, error)

func (*ReadAlloc) HeadFree

func (r *ReadAlloc) HeadFree(id int64) error

func (*ReadAlloc) HeadRead

func (r *ReadAlloc) HeadRead(id int64) (b bufferex.Binary, e error)

func (*ReadAlloc) HeadWrite

func (r *ReadAlloc) HeadWrite(id int64, b []byte) error

func (*ReadAlloc) Page

func (r *ReadAlloc) Page() int

func (*ReadAlloc) PageAlloc

func (r *ReadAlloc) PageAlloc() (int64, error)

func (*ReadAlloc) PageFree

func (r *ReadAlloc) PageFree(id int64) error

func (*ReadAlloc) PageRead

func (r *ReadAlloc) PageRead(id int64) (b bufferex.Binary, e error)

func (*ReadAlloc) PageWrite

func (r *ReadAlloc) PageWrite(id int64, b []byte) error

type Root

type Root struct {
	Ptr   int64
	Depth uint32
}

func (*Root) BinDecode

func (r *Root) BinDecode(b []byte) error

func (Root) BinEncode

func (r Root) BinEncode(b []byte) error

type Tree

type Tree struct {
	IBase
	Ops TreeOps
}

func (*Tree) Delete

func (t *Tree) Delete(
	ctx context.Context,
	obj int64,
	q interface{},
	chk func([]byte) bool) (r_abort, r_err error)

func (*Tree) GSearch

func (t *Tree) GSearch(
	ctx context.Context,
	obj int64,
	q interface{},
	consume func(b []byte) bool) error

func (*Tree) Insert

func (t *Tree) Insert(obj int64, nitem []byte) error

func (*Tree) NewRoot

func (t *Tree) NewRoot() (int64, error)

func (*Tree) Search

func (t *Tree) Search(
	ctx context.Context,
	obj int64,
	q interface{},
	consumer func([]byte)) error

type TreeOps

type TreeOps interface {
	Consistent(p []byte, q interface{}) bool

	Union(P Elements) []byte

	Penalty(E1, E2 []byte) float64

	// The FirstSplit functions covers three cases.
	// Given FirstSplit(P,maxsize) -> A,B
	//
	// - Case 1: P is small enough to fit in maxsize.
	//           In this case, return P,nil
	// - Case 2: P is small enough so that A and B can fit in maxsize each.
	//           In this case, split P into A and B evenly.
	// - Case 3: P is so large, that eighter only A or B can fit in maxsize.
	//           In this case, return A,B so that A fits in maxsize.
	//
	// Given FirstSplit(P,maxsize) -> A,B   and .Sort() is implemented
	//       P is sorted and A and B are assumed to be sorted.
	FirstSplit(P Elements, maxsize int) (Elements, Elements)

	Sort(E Elements)
}

type WriteAlloc

type WriteAlloc struct {
	ReadAlloc
	A *file.Allocator
}

func (*WriteAlloc) HeadAlloc

func (r *WriteAlloc) HeadAlloc() (int64, error)

func (*WriteAlloc) HeadFree

func (r *WriteAlloc) HeadFree(id int64) error

func (*WriteAlloc) HeadWrite

func (r *WriteAlloc) HeadWrite(id int64, b []byte) error

func (*WriteAlloc) PageAlloc

func (r *WriteAlloc) PageAlloc() (int64, error)

func (*WriteAlloc) PageFree

func (r *WriteAlloc) PageFree(id int64) error

func (*WriteAlloc) PageWrite

func (r *WriteAlloc) PageWrite(id int64, b []byte) error