btree

package
v1.8.2-0...-f7776fc Latest Latest
Warning

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

 Go to latest Published: Feb 2, 2024 License: GPL-2.0, GPL-3.0 Imports: 9 Imported by: 0

Documentation

Overview

Package btree provides B⁺ Trees for ZODB.

It is modelled after and is data compatible with BTree/py package: 

http://btrees.readthedocs.io
https://github.com/zopefoundation/BTrees

A B⁺ tree consists of nodes. Only leaf tree nodes point to data. Intermediate tree nodes contains keys and pointers to next-level tree nodes.

A well-balanced B⁺ tree always have uniform depth - that is the path to any leaf node from the tree root is the same. However historically ZODB/py does not always balance B⁺ trees well(*), so this property is not preserved. Nevertheless an intermediate B⁺ tree node always has children of the same kind: they are either all leafs or all intermediate nodes(+).

BTree and Bucket represent an intermediate and a leaf tree node correspondingly. Node represents any of them.

node.Get(key) performs point-query.

node.{Min,Max}Key() returns key-range limit for all children/values under the node.

node.Entryv() returns [] of (key, child/value).

BTree.FirstBucket() and Bucket.Next() allow to iterate through leaf B⁺ tree nodes.

BTree.V<op>(..., visit) performs <op> with calling visit on every accessed tree node.

--------

(*) https://github.com/zopefoundation/ZODB/blob/3.10.7-4-gb8d7a8567/src/BTrees/Development.txt#L211

(+) https://github.com/zopefoundation/ZODB/blob/3.10.7-4-gb8d7a8567/src/BTrees/Development.txt#L231

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type IKeyRange 

type IKeyRange struct {
	Lo  int32
	Hi_ int32 // NOTE _not_ hi) to avoid overflow at ∞;  hi = hi_ + 1
}

IKeyRange represents [lo,hi) key range.

func (*IKeyRange) Empty 

func (r *IKeyRange) Empty() bool

Empty returns whether key range is empty.

func (*IKeyRange) Has 

func (r *IKeyRange) Has(k int32) bool

Has returns whether key k belongs to the range.

func (IKeyRange) String 

func (r IKeyRange) String() string

type IOBTree 

type IOBTree struct {
	zodb.Persistent
	// contains filtered or unexported fields
}

IOBTree is a non-leaf node of a B⁺ tree.

It contains []IOEntry in ↑ key order.

It mimics IOBTree from btree/py.

func (*IOBTree) Entryv 

func (t *IOBTree) Entryv() []IOEntry

Entryv returns entries of a IOBTree node.

Entries keys limit the keys of all children reachable from an entry: 

[i].Key ≤ [i].Child.*.Key < [i+1].Key		i ∈ [0, len([]))

[0].Key       = -∞	; always returned so
[len(ev)].Key = +∞	; should be assumed so

Children of all entries are guaranteed to be of the same kind - either all IOBTree, or all IOBucket.

The caller must not modify returned array.

func (*IOBTree) FirstBucket 

func (t *IOBTree) FirstBucket() *IOBucket

FirstBucket returns bucket containing the smallest key in the tree.

func (*IOBTree) Get 

func (t *IOBTree) Get(ctx context.Context, key int32) (_ interface{}, _ bool, err error)

Get searches IOBTree by key.

It loads intermediate IOBTree nodes from database on demand as needed.

t need not be activated beforehand for Get to work.

func (*IOBTree) MaxKey 

func (t *IOBTree) MaxKey(ctx context.Context) (_ int32, _ bool, err error)

MaxKey returns maximum key in IOBTree.

If the tree is empty, ok=false is returned. The tree does not need to be activated beforehand.

func (*IOBTree) MinKey 

func (t *IOBTree) MinKey(ctx context.Context) (_ int32, ok bool, err error)

MinKey returns minimum key in IOBTree.

If the tree is empty, ok=false is returned. The tree does not need to be activated beforehand.

func (*IOBTree) VGet 

func (t *IOBTree) VGet(ctx context.Context, key int32, visit func(node IONode, keycov IKeyRange)) (_ interface{}, _ bool, err error)

VGet is like Get but also calls visit while traversing the tree.

Visit is called with node being activated.

func (*IOBTree) VMaxKey 

func (t *IOBTree) VMaxKey(ctx context.Context, visit func(node IONode, keycov IKeyRange)) (_ int32, _ bool, err error)

VMaxKey is like MaxKey but also calls visit while traversing the tree.

Visit is called with node being activated.

func (*IOBTree) VMinKey 

func (t *IOBTree) VMinKey(ctx context.Context, visit func(node IONode, keycov IKeyRange)) (_ int32, ok bool, err error)

VMinKey is like MinKey but also calls visit while traversing the tree.

Visit is called with node being activated.

type IOBucket 

type IOBucket struct {
	zodb.Persistent
	// contains filtered or unexported fields
}

IOBucket is a leaf node of a B⁺ tree.

It contains []IOBucketEntry in ↑ key order.

It mimics IOBucket from btree/py.

func (*IOBucket) Entryv 

func (b *IOBucket) Entryv() []IOBucketEntry

Entryv returns entries of a IOBucket node.

func (*IOBucket) Get 

func (b *IOBucket) Get(key int32) (interface{}, bool)

Get searches IOBucket by key.

no loading from database is done. The bucket must be already activated.

func (*IOBucket) MaxKey 

func (b *IOBucket) MaxKey() (_ int32, ok bool)

MaxKey returns maximum key in IOBucket.

If the bucket is empty, ok=false is returned.

func (*IOBucket) MinKey 

func (b *IOBucket) MinKey() (_ int32, ok bool)

MinKey returns minimum key in IOBucket.

If the bucket is empty, ok=false is returned.

func (*IOBucket) Next 

func (b *IOBucket) Next() *IOBucket

Next returns tree bucket with next larger keys relative to current bucket.

type IOBucketEntry 

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

IOBucketEntry is one IOBucket node entry.

It contains key and value.

func (*IOBucketEntry) Key 

func (e *IOBucketEntry) Key() int32

Key returns IOBucket entry key.

func (*IOBucketEntry) Value 

func (e *IOBucketEntry) Value() interface{}

Value returns IOBucket entry value.

type IOEntry 

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

IOEntry is one IOBTree node entry.

It contains key and child, which is either IOBTree or IOBucket.

Key limits child's keys - see IOBTree.Entryv for details.

func (*IOEntry) Child 

func (e *IOEntry) Child() IONode

Child returns IOBTree entry child.

func (*IOEntry) Key 

func (e *IOEntry) Key() int32

Key returns IOBTree entry key.

type IONode 

type IONode interface {
	zodb.IPersistent
	// contains filtered or unexported methods
}

IONode represents a tree node - either IOBTree or IOBucket.

type LKeyRange 

type LKeyRange struct {
	Lo  int64
	Hi_ int64 // NOTE _not_ hi) to avoid overflow at ∞;  hi = hi_ + 1
}

LKeyRange represents [lo,hi) key range.

func (*LKeyRange) Empty 

func (r *LKeyRange) Empty() bool

Empty returns whether key range is empty.

func (*LKeyRange) Has 

func (r *LKeyRange) Has(k int64) bool

Has returns whether key k belongs to the range.

func (LKeyRange) String 

func (r LKeyRange) String() string

type LOBTree 

type LOBTree struct {
	zodb.Persistent
	// contains filtered or unexported fields
}

LOBTree is a non-leaf node of a B⁺ tree.

It contains []LOEntry in ↑ key order.

It mimics LOBTree from btree/py.

func (*LOBTree) Entryv 

func (t *LOBTree) Entryv() []LOEntry

Entryv returns entries of a LOBTree node.

Entries keys limit the keys of all children reachable from an entry: 

[i].Key ≤ [i].Child.*.Key < [i+1].Key		i ∈ [0, len([]))

[0].Key       = -∞	; always returned so
[len(ev)].Key = +∞	; should be assumed so

Children of all entries are guaranteed to be of the same kind - either all LOBTree, or all LOBucket.

The caller must not modify returned array.

func (*LOBTree) FirstBucket 

func (t *LOBTree) FirstBucket() *LOBucket

FirstBucket returns bucket containing the smallest key in the tree.

func (*LOBTree) Get 

func (t *LOBTree) Get(ctx context.Context, key int64) (_ interface{}, _ bool, err error)

Get searches LOBTree by key.

It loads intermediate LOBTree nodes from database on demand as needed.

t need not be activated beforehand for Get to work.

func (*LOBTree) MaxKey 

func (t *LOBTree) MaxKey(ctx context.Context) (_ int64, _ bool, err error)

MaxKey returns maximum key in LOBTree.

If the tree is empty, ok=false is returned. The tree does not need to be activated beforehand.

func (*LOBTree) MinKey 

func (t *LOBTree) MinKey(ctx context.Context) (_ int64, ok bool, err error)

MinKey returns minimum key in LOBTree.

If the tree is empty, ok=false is returned. The tree does not need to be activated beforehand.

func (*LOBTree) VGet 

func (t *LOBTree) VGet(ctx context.Context, key int64, visit func(node LONode, keycov LKeyRange)) (_ interface{}, _ bool, err error)

VGet is like Get but also calls visit while traversing the tree.

Visit is called with node being activated.

func (*LOBTree) VMaxKey 

func (t *LOBTree) VMaxKey(ctx context.Context, visit func(node LONode, keycov LKeyRange)) (_ int64, _ bool, err error)

VMaxKey is like MaxKey but also calls visit while traversing the tree.

Visit is called with node being activated.

func (*LOBTree) VMinKey 

func (t *LOBTree) VMinKey(ctx context.Context, visit func(node LONode, keycov LKeyRange)) (_ int64, ok bool, err error)

VMinKey is like MinKey but also calls visit while traversing the tree.

Visit is called with node being activated.

type LOBucket 

type LOBucket struct {
	zodb.Persistent
	// contains filtered or unexported fields
}

LOBucket is a leaf node of a B⁺ tree.

It contains []LOBucketEntry in ↑ key order.

It mimics LOBucket from btree/py.

func (*LOBucket) Entryv 

func (b *LOBucket) Entryv() []LOBucketEntry

Entryv returns entries of a LOBucket node.

func (*LOBucket) Get 

func (b *LOBucket) Get(key int64) (interface{}, bool)

Get searches LOBucket by key.

no loading from database is done. The bucket must be already activated.

func (*LOBucket) MaxKey 

func (b *LOBucket) MaxKey() (_ int64, ok bool)

MaxKey returns maximum key in LOBucket.

If the bucket is empty, ok=false is returned.

func (*LOBucket) MinKey 

func (b *LOBucket) MinKey() (_ int64, ok bool)

MinKey returns minimum key in LOBucket.

If the bucket is empty, ok=false is returned.

func (*LOBucket) Next 

func (b *LOBucket) Next() *LOBucket

Next returns tree bucket with next larger keys relative to current bucket.

type LOBucketEntry 

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

LOBucketEntry is one LOBucket node entry.

It contains key and value.

func (*LOBucketEntry) Key 

func (e *LOBucketEntry) Key() int64

Key returns LOBucket entry key.

func (*LOBucketEntry) Value 

func (e *LOBucketEntry) Value() interface{}

Value returns LOBucket entry value.

type LOEntry 

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

LOEntry is one LOBTree node entry.

It contains key and child, which is either LOBTree or LOBucket.

Key limits child's keys - see LOBTree.Entryv for details.

func (*LOEntry) Child 

func (e *LOEntry) Child() LONode

Child returns LOBTree entry child.

func (*LOEntry) Key 

func (e *LOEntry) Key() int64

Key returns LOBTree entry key.

type LONode 

type LONode interface {
	zodb.IPersistent
	// contains filtered or unexported methods
}

LONode represents a tree node - either LOBTree or LOBucket.

type Length 

type Length struct {
	zodb.Persistent
	// contains filtered or unexported fields
}

Length is equivalent of BTrees.Length.Length in BTree/py.

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.