Documentation
¶
Index ¶
- func AllLeaves[TMessage any, TMessagePtr interface{ ... }, TReference any](ctx context.Context, ...) iter.Seq[model_core.Message[TMessagePtr, TReference]]
- func Find[TMessage any, TMessagePtr interface{ ... }, TReference any](ctx context.Context, ...) (model_core.Message[TMessagePtr, TReference], error)
- func MaybeMergeNodes[TNode proto.Message, TMetadata model_core.ReferenceMetadata](nodes []TNode, ...) []TNode
- type Builder
- func NewSplitBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](leavesChunker Chunker[TNode, TMetadata], ...) Builder[TNode, TMetadata]
- func NewSplitProllyBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](minimumSizeBytes, maximumSizeBytes int, ...) Builder[TNode, TMetadata]
- func NewUniformBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](chunkerFactory ChunkerFactory[TNode, TMetadata], ...) Builder[TNode, TMetadata]
- func NewUniformProllyBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](minimumSizeBytes, maximumSizeBytes int, ...) Builder[TNode, TMetadata]
- type Chunker
- type ChunkerFactory
- type ChunkerFactoryForTesting
- type ChunkerForTesting
- type NodeMerger
- type NodeMergerForTesting
- type ParentNodeComputer
- type ParentNodeComputerForTesting
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AllLeaves ¶
func AllLeaves[ TMessage any, TMessagePtr interface { *TMessage proto.Message }, TReference any, ]( ctx context.Context, reader model_parser.ParsedObjectReader[model_core.Decodable[TReference], model_core.Message[[]TMessagePtr, TReference]], root model_core.Message[[]TMessagePtr, TReference], traverser func(model_core.Message[TMessagePtr, TReference]) (*model_core_pb.DecodableReference, error), errOut *error, ) iter.Seq[model_core.Message[TMessagePtr, TReference]]
AllLeaves can be used to iterate all leaf entries contained in a B-tree.
func Find ¶
func Find[ TMessage any, TMessagePtr interface { *TMessage proto.Message }, TReference any, ]( ctx context.Context, reader model_parser.ParsedObjectReader[model_core.Decodable[TReference], model_core.Message[[]TMessagePtr, TReference]], list model_core.Message[[]TMessagePtr, TReference], cmp func(model_core.Message[TMessagePtr, TReference]) (int, *model_core_pb.DecodableReference), ) (model_core.Message[TMessagePtr, TReference], error)
Find an entry contained in a B-tree.
func MaybeMergeNodes ¶
func MaybeMergeNodes[TNode proto.Message, TMetadata model_core.ReferenceMetadata]( nodes []TNode, externalObject *model_core.Decodable[model_core.CreatedObject[TMetadata]], patcher *model_core.ReferenceMessagePatcher[TMetadata], parentNodeComputer ParentNodeComputer[TNode, TMetadata], ) []TNode
MaybeMergeNodes either returns the top-level elements of a B-tree in literal form, or emits a single parent node referring to the elements stored in a separate object.
This function is typically used in combination with inlinedtree.Build() to spill the top-level elements of a B-tree into a separate object, if storing them inline would cause the parent object to become too large.
Types ¶
type Builder ¶
type Builder[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface { PushChild(node model_core.PatchedMessage[TNode, TMetadata]) error FinalizeList() (model_core.PatchedMessage[[]TNode, TMetadata], error) FinalizeSingle() (model_core.PatchedMessage[TNode, TMetadata], error) }
Builder of B-trees.
func NewSplitBuilder ¶
func NewSplitBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](leavesChunker Chunker[TNode, TMetadata], leavesNodeMerger NodeMerger[TNode, TMetadata], parentsBuilder Builder[TNode, TMetadata]) Builder[TNode, TMetadata]
NewSplitBuilder creates a Builder that can use a different Chunker for leaf and parent objects. This can, for example, be used to make leaf nodes larger than parents.
func NewSplitProllyBuilder ¶
func NewSplitProllyBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](minimumSizeBytes, maximumSizeBytes int, nodeMerger NodeMerger[TNode, TMetadata]) Builder[TNode, TMetadata]
NewSplitProllyBuilder creates a builder of B-trees, assuming that leaf nodes may be large. In those cases leaf objects should be permitted to contain a single node, if it turns out it's too large to store alongside its siblings.
func NewUniformBuilder ¶
func NewUniformBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](chunkerFactory ChunkerFactory[TNode, TMetadata], nodeMerger NodeMerger[TNode, TMetadata]) Builder[TNode, TMetadata]
NewUniformBuilder creates a B-tree builder that is in the initial state (i.e., does not contain any nodes). The resulting B-tree will be uniform, meaning that all layers will be constructed using the same Chunker.
func NewUniformProllyBuilder ¶
func NewUniformProllyBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](minimumSizeBytes, maximumSizeBytes int, nodeMerger NodeMerger[TNode, TMetadata]) Builder[TNode, TMetadata]
NewUniformProllyBuilder creates a builder of B-trees, assuming that leaf nodes in the tree are small and mere references to the actual data. For example, for files the leaf nodes in the B-tree are just references to the a chunk. For such trees, each object in the B-tree should contain at least two nodes.
type Chunker ¶
type Chunker[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface { PushSingle(node model_core.PatchedMessage[TNode, TMetadata]) error PopMultiple(finalize bool) model_core.PatchedMessage[[]TNode, TMetadata] }
Chunker is responsible for determining how nodes at a given level in the B-tree are chunked and spread out across sibling objects at the same level.
type ChunkerFactory ¶
type ChunkerFactory[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface { NewChunker() Chunker[TNode, TMetadata] }
ChunkerFactory is a factory type for creating chunkers of individual levels of a B-tree.
func NewProllyChunkerFactory ¶
func NewProllyChunkerFactory[TNode proto.Message, TMetadata model_core.ReferenceMetadata]( minimumCount, minimumSizeBytes, maximumSizeBytes int, ) ChunkerFactory[TNode, TMetadata]
NewProllyChunkerFactory returns a ChunkerFactory that is capable of creating Chunkers that perform probabilistic chunking, leading to the creation of a Prolly Tree:
https://docs.dolthub.com/architecture/storage-engine/prolly-tree
For each node that is inserted, an FNV-1a hash is computed based on the node's message contents and outgoing references. A cut is made after the node where the hash is maximal.
The size computation that is used by this type assumes that the resulting nodes are stored in an object where each node is prefixed with a variable length integer indicating the node's size.
type ChunkerFactoryForTesting ¶
type ChunkerFactoryForTesting ChunkerFactory[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]
ChunkerFactoryForTesting is an instantiation of ChunkerFactory for generating mocks to be used by tests.
type ChunkerForTesting ¶
type ChunkerForTesting Chunker[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]
ChunkerForTesting is an instantiation of Chunker for generating mocks to be used by tests.
type NodeMerger ¶
type NodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata] func(model_core.PatchedMessage[[]TNode, TMetadata]) (model_core.PatchedMessage[TNode, TMetadata], error)
NodeMerger is invoked whenever a list of tree nodes is gathered that should be placed as siblings in a single B-tree object. It is responsible for constructing the B-tree object and yielding a message that can be placed in the parent object to reference it.
func NewObjectCreatingNodeMerger ¶
func NewObjectCreatingNodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata](encoder model_encoding.BinaryEncoder, referenceFormat object.ReferenceFormat, parentNodeComputer ParentNodeComputer[TNode, TMetadata]) NodeMerger[TNode, TMetadata]
NewObjectCreatingNodeMerger creates a NodeMerger that can be used in combination with Builder to construct B-trees that are backed by storage objects that reference each other.
type NodeMergerForTesting ¶
type NodeMergerForTesting NodeMerger[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]
NodeMergerForTesting is an instantiation of NodeMerger for generating mocks to be used by tests.
type ParentNodeComputer ¶
type ParentNodeComputer[TNode proto.Message, TMetadata model_core.ReferenceMetadata] func( createdObject model_core.Decodable[model_core.CreatedObject[TMetadata]], childNodes []TNode, ) model_core.PatchedMessage[TNode, TMetadata]
ParentNodeComputer can be used by ObjectCreatingNodeMerger to combine the values of nodes stored in an object into a single node that can be stored in its parent.
type ParentNodeComputerForTesting ¶
type ParentNodeComputerForTesting ParentNodeComputer[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]
ParentNodeComputerForTesting is an instantiation of ParentNodeComputer for generating mocks to be used by tests.
Source Files