btree

Documentation

Index

• 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
  • func NewProllyChunkerFactory[TNode proto.Message, TMetadata model_core.ReferenceMetadata](minimumCount, minimumSizeBytes, maximumSizeBytes int) ChunkerFactory[TNode, TMetadata]
• type ChunkerFactoryForTesting
• type ChunkerForTesting
• type NodeMerger
  • func NewObjectCreatingNodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata](encoder model_encoding.BinaryEncoder, referenceFormat object.ReferenceFormat, ...) NodeMerger[TNode, TMetadata]
• type NodeMergerForTesting
• type ParentNodeComputer
• type ParentNodeComputerForTesting

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 a message having the following schema:

message TNodeList {
  repeated TNode nodes = 1;
}

type ChunkerFactoryForTesting

type ChunkerFactoryForTesting ChunkerFactory[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

type ChunkerForTesting

type ChunkerForTesting Chunker[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

type NodeMerger

type NodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata] func(model_core.PatchedMessage[[]TNode, TMetadata]) (model_core.PatchedMessage[TNode, TMetadata], error)

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]

type ParentNodeComputer

type ParentNodeComputer[TNode proto.Message, TMetadata model_core.ReferenceMetadata] func(
	contents *object.Contents,
	childNodes []TNode,
	outgoingReferences object.OutgoingReferences,
	metadata []TMetadata,
) (model_core.PatchedMessage[TNode, TMetadata], error)

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]