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 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)) (_ 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)) (_ 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)) (_ 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, who 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 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)) (_ 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)) (_ 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)) (_ 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, who 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.