btree

package
v1.8.7 Latest Latest
Warning

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

 Go to latest Published: Mar 10, 2024 License: MIT Imports: 6 Imported by: 0

Documentation

Overview

Package btree contains the code artifacts implementing the M-Way Trie data structures and algorithms. It also contains different interfaces necessary for btree to support different storage backends. In one implementation, btree can be in-memory, in another, it can be using other backend storage systems like Cassandra and AWS S3.

A b-tree that can distribute items added on a given "leaf" sub-branch so it will tend to fill in the nodes of the sub-branch. Instead of achieving half full on average load(typical), each node can then achieve higher load average, perhaps up to 62%-75% on average. This logic is cut, limited within a given sub-branch so as not to affect performance. Feature can be turned off if needed.

"leaf sub-branch" is the outermost node of the trie that only has 1 level children, that is, its children has no children.

"leaf" node is the edge node, it has no children.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Compare added in v1.8.7 

func Compare[T Comparable](x, y T) int

Compare can Compare a Comparable type.

func ConvertToBlobTableName added in v1.6.3 

func ConvertToBlobTableName(registryTableName string) string

func FormatBlobTable added in v1.6.3 

func FormatBlobTable(name string) string

func FormatRegistryTable added in v1.6.3 

func FormatRegistryTable(name string) string

Types

type Btree 

type Btree[TK Comparable, TV any] struct {
	StoreInfo *StoreInfo
	// contains filtered or unexported fields
}

Btree manages items using B-tree data structure and algorithm.

func New added in v1.5.1 

func New[TK Comparable, TV any](storeInfo *StoreInfo, si *StoreInterface[TK, TV]) (*Btree[TK, TV], error)

New creates a new B-Tree instance.

func (*Btree[TK, TV]) Add 

func (btree *Btree[TK, TV]) Add(ctx context.Context, key TK, value TV) (bool, error)

Add a key/value pair item to the tree.

func (*Btree[TK, TV]) AddIfNotExist 

func (btree *Btree[TK, TV]) AddIfNotExist(ctx context.Context, key TK, value TV) (bool, error)

AddIfNotExist will add an item if its key is not yet in the B-Tree.

func (*Btree[TK, TV]) AddItem added in v1.8.7 

func (btree *Btree[TK, TV]) AddItem(ctx context.Context, item *Item[TK, TV]) (bool, error)

For internal use only, when SOP is doing refetch and merge in commt.

func (*Btree[TK, TV]) Count added in v1.7.3 

func (btree *Btree[TK, TV]) Count() int64

Returns the number of items in this B-Tree.

func (*Btree[TK, TV]) FindOne 

func (btree *Btree[TK, TV]) FindOne(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)

FindOne will traverse the tree to find an item with such key.

func (*Btree[TK, TV]) FindOneWithID added in v1.8.7 

func (btree *Btree[TK, TV]) FindOneWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)

FindOneWithID is synonymous to FindOne but allows code to supply the Item's ID to identify it.

func (*Btree[TK, TV]) First added in v1.5.1 

func (btree *Btree[TK, TV]) First(ctx context.Context) (bool, error)

First will traverse the tree and find the first item, first according to the key ordering sequence.

func (*Btree[TK, TV]) GetCurrentItem 

func (btree *Btree[TK, TV]) GetCurrentItem(ctx context.Context) (Item[TK, TV], error)

getCurrentItem returns the current item containing key/value pair.

func (*Btree[TK, TV]) GetCurrentKey 

func (btree *Btree[TK, TV]) GetCurrentKey() TK

GetCurrentKey returns the current item's key part.

func (*Btree[TK, TV]) GetCurrentValue 

func (btree *Btree[TK, TV]) GetCurrentValue(ctx context.Context) (TV, error)

GetCurrentValue returns the current item's value part.

func (*Btree[TK, TV]) IsUnique 

func (btree *Btree[TK, TV]) IsUnique() bool

IsUnique returns true if B-Tree is specified to store items with Unique keys, otherwise false.

func (*Btree[TK, TV]) IsValueDataInNodeSegment 

func (btree *Btree[TK, TV]) IsValueDataInNodeSegment() bool

IsValueDataInNodeSegment is true if Item's Values are stored in the Node segment together with the Items' Keys. Always true in in-memory B-Tree.

func (*Btree[TK, TV]) Last added in v1.5.1 

func (btree *Btree[TK, TV]) Last(ctx context.Context) (bool, error)

func (*Btree[TK, TV]) Next added in v1.5.1 

func (btree *Btree[TK, TV]) Next(ctx context.Context) (bool, error)

func (*Btree[TK, TV]) Previous added in v1.5.1 

func (btree *Btree[TK, TV]) Previous(ctx context.Context) (bool, error)

func (*Btree[TK, TV]) Remove 

func (btree *Btree[TK, TV]) Remove(ctx context.Context, key TK) (bool, error)

Remove will find the item with given key and delete it.

func (*Btree[TK, TV]) RemoveCurrentItem 

func (btree *Btree[TK, TV]) RemoveCurrentItem(ctx context.Context) (bool, error)

RemoveCurrentItem will remove the current item, i.e. - referenced by CurrentItemRef.

func (*Btree[TK, TV]) Update 

func (btree *Btree[TK, TV]) Update(ctx context.Context, key TK, newValue TV) (bool, error)

Update will find the item with matching key as the key parameter & update its value with the provided value parameter.

func (*Btree[TK, TV]) UpdateCurrentItem 

func (btree *Btree[TK, TV]) UpdateCurrentItem(ctx context.Context, newValue TV) (bool, error)

func (*Btree[TK, TV]) UpdateCurrentNodeItem added in v1.8.7 

func (btree *Btree[TK, TV]) UpdateCurrentNodeItem(ctx context.Context, item *Item[TK, TV]) (bool, error)

For internal use only, when SOP is doing refetch and merge in commt.

type BtreeInterface 

type BtreeInterface[TK Comparable, TV any] interface {
	// Add adds an item to the b-tree and does not check for duplicates.
	Add(ctx context.Context, key TK, value TV) (bool, error)
	// AddIfNotExist adds an item if there is no item matching the key yet.
	// Otherwise, it will do nothing and return false, for not adding the item.
	// This is useful for cases one wants to add an item without creating a duplicate entry.
	AddIfNotExist(ctx context.Context, key TK, value TV) (bool, error)

	// Update finds the item with key and update its value to the value argument.
	Update(ctx context.Context, key TK, value TV) (bool, error)
	// UpdateCurrentItem will update the Value of the current item.
	// Key is read-only, thus, no argument for the key.
	UpdateCurrentItem(ctx context.Context, newValue TV) (bool, error)
	// Remove will find the item with a given key then remove that item.
	Remove(ctx context.Context, key TK) (bool, error)
	// RemoveCurrentItem will remove the current key/value pair from the store.
	RemoveCurrentItem(ctx context.Context) (bool, error)

	// FindOne will search Btree for an item with a given key. Return true if found,
	// otherwise false. firstItemWithKey is useful when there are items with same key.
	// true will position pointer to the first item with the given key,
	// according to key ordering sequence.
	// Use the CurrentKey/CurrentValue to retrieve the "current item" details(key &/or value).
	FindOne(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)
	// FindOneWithID is synonymous to FindOne but allows code to supply the Item's ID to identify it.
	// This is useful for B-Tree that allows duplicate keys(IsUnique = false) as it provides a way to
	// differentiate duplicated keys via the unique ID(sop.UUID).
	FindOneWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)
	// GetCurrentKey returns the current item's key.
	GetCurrentKey() TK
	// GetCurrentValue returns the current item's value.
	GetCurrentValue(ctx context.Context) (TV, error)
	// GetCurrentItem returns the current item.
	GetCurrentItem(ctx context.Context) (Item[TK, TV], error)

	// First positions the "cursor" to the first item as per key ordering.
	// Use the CurrentKey/CurrentValue to retrieve the "current item" details(key &/or value).
	First(ctx context.Context) (bool, error)
	// Last positionts the "cursor" to the last item as per key ordering.
	// Use the CurrentKey/CurrentValue to retrieve the "current item" details(key &/or value).
	Last(ctx context.Context) (bool, error)
	// Next positions the "cursor" to the next item as per key ordering.
	// Use the CurrentKey/CurrentValue to retrieve the "current item" details(key &/or value).
	Next(ctx context.Context) (bool, error)
	// Previous positions the "cursor" to the previous item as per key ordering.
	// Use the CurrentKey/CurrentValue to retrieve the "current item" details(key &/or value).
	Previous(ctx context.Context) (bool, error)

	// IsValueDataInNodeSegment is true if "Value" data is stored in the B-Tree node's segment.
	// Otherwise is false.
	IsValueDataInNodeSegment() bool

	// IsUnique returns true if B-Tree is specified to store items with Unique keys, otherwise false.
	// Specifying uniqueness base on key makes the B-Tree permanently set. If you want just a temporary
	// unique check during Add of an item, then you can use AddIfNotExist method for that.
	IsUnique() bool

	// Returns the number of items in this B-Tree.
	Count() int64
}

BtreeInterface defines publicly callable methods of Btree.

type Comparable 

type Comparable interface {
	cmp.Ordered | *Comparer | any
}

Comparable interface is used as a B-Tree store (generics) constraint for Key types.

type Comparer 

type Comparer interface {
	// Implement Compare to compare this object with the 'other' object.
	// Returns -1 (this object < other), 0 (this object == other), 1 (this object > other)
	Compare(other interface{}) int
}

Comparer interface specifies the Compare function.

type Item 

type Item[TK Comparable, TV any] struct {
	// (Internal) ID is the Item's sop.UUID. ID is needed for two reasons:
	// 1. so B-Tree can identify or differentiate item(s) with duplicated Key.
	// 2. used as the Value "data" ID if item's value data is persisted in another
	// data segment, separate from the Node segment(IsValueDataInNodeSegment=false).
	ID sop.UUID
	// Key is the key part in key/value pair.
	Key TK
	// Value is saved nil if data is to be persisted in the "data segment"(& ValueID set to a valid sop.UUID),
	// otherwise it should point to the actual data and persisted in B-Tree Node segment together with the Key.
	Value *TV
	// Version is used for conflict resolution among (in-flight) transactions.
	Version int
	// flag that tells B-Tree whether value data needs fetching or not.
	// Applicable only for B-Tree where 'IsValueDataInNodeSegment' is false use-case.
	ValueNeedsFetch bool
	// contains filtered or unexported fields
}

Item contains key & value pair, plus the version number.

type ItemActionTracker added in v1.5.1 

type ItemActionTracker[TK Comparable, TV any] interface {
	// Add will just cache the item, "add" action for submit on transaction commit as appropriate.
	Add(ctx context.Context, item *Item[TK, TV]) error
	// Get will just cache the item, "get" action then resolve on transaction commit, compare version
	// with backend copy, error out if version shows another transaction modified/deleted this item on the back.
	Get(ctx context.Context, item *Item[TK, TV]) error
	// Update will just cache the item, "update" action for submit on transaction commit as appropriate.
	Update(ctx context.Context, item *Item[TK, TV]) error
	// Remove will just cache the item, "remove" action for submit on transaction commit as appropriate.
	Remove(ctx context.Context, item *Item[TK, TV]) error
}

ItemActionTracker specifies the CRUD action methods that can be done to manage Items. These action methods can be implemented to allow the backend to resolve and submit these changes to the backend storage during transaction commit.

type MetaDataType added in v1.6.3 

type MetaDataType interface {
	// Returns the object's ID.
	GetID() sop.UUID
	// Returns the object's version.
	GetVersion() int
	// Applies a version to the object.
	SetVersion(v int)
}

MetaDataType specifies object meta data fields such as ID & Version.

type Node 

type Node[TK Comparable, TV any] struct {
	ID       sop.UUID
	ParentID sop.UUID
	// Slots is an array where the Items get stored in.
	Slots []*Item[TK, TV]
	// Count of items in this node.
	Count int
	// Version of this node.
	Version int
	// Children IDs of this node.
	ChildrenIDs []sop.UUID
	// contains filtered or unexported fields
}

Node contains a B-Tree node's data.

func (*Node[TK, TV]) GetID added in v1.8.7 

func (n *Node[TK, TV]) GetID() sop.UUID

func (*Node[TK, TV]) GetVersion added in v1.6.4 

func (n *Node[TK, TV]) GetVersion() int

func (*Node[TK, TV]) SetVersion added in v1.6.4 

func (n *Node[TK, TV]) SetVersion(v int)

type NodeRepository 

type NodeRepository[TK Comparable, TV any] interface {
	// Add will just cache the item, "add" action for submit on transaction commit as appropriate.
	Add(node *Node[TK, TV])
	// Get fetches from backend(or from cache if exists) & returns the Node with a given nodeID.
	Get(ctx context.Context, nodeID sop.UUID) (*Node[TK, TV], error)
	// Mark Node with nodeID as fetched, so, it will get checked for version conflict during commit.
	Fetched(nodeID sop.UUID)
	// Update will just cache the item, "update" action for resolve on transaction commit as appropriate.
	Update(node *Node[TK, TV])
	// Remove will just cache the item, "remove" action for resolve on transaction commit as appropriate.
	Remove(nodeID sop.UUID)
}

NodeRepository interface specifies the node repository.

type StoreInfo added in v1.5.1 

type StoreInfo struct {
	// Short name of this (B-Tree store).
	Name string
	// Count of items that can be stored on a given node.
	SlotLength int
	// IsUnique tells whether key/value pair (items) of this tree should be unique on key.
	IsUnique bool
	// (optional) Description of the Store.
	Description string
	// Virtual ID registry table name.
	RegistryTable string
	// Blob table name.
	BlobTable string
	// RootNodeID is the root node's ID.
	RootNodeID sop.UUID
	// Total count of items stored.
	Count int64
	// Used internally by SOP. Should be ignored when persisted in the backend.
	CountDelta int64 `json:"-"`
	// Add or update timestamp in milliseconds.
	Timestamp int64
	// IsValueDataInNodeSegment is true if "Value" data is stored in the B-Tree node's data segment.
	// Otherwise is false.
	IsValueDataInNodeSegment bool
	// If true, each Btree Add(..) method call will persist the item value's data to another partition, then on commit,
	// it will then be a very quick action as item(s) values' data were already saved on backend.
	// This rquires 'IsValueDataInNodeSegment' field to be set to false to work.
	IsValueDataActivelyPersisted bool
	// If true, the Value data will be cached in Redis, otherwise not. This is used when 'IsValueDataInNodeSegment'
	// is set to false. Typically set to false if 'IsValueDataActivelyPersisted' is true, as value data is expected
	// to be huge rendering caching it in Redis to affect Redis performance due to the drastic size of data per item.
	IsValueDataGloballyCached bool
	// If true, node load will be balanced by pushing items to sibling nodes if there are vacant slots,
	// otherwise will not. This feature can be turned off if backend is impacted by the "balancing" act.
	LeafLoadBalancing bool
}

StoreInfo contains a given (B-Tree) store details.

func NewStoreInfo added in v1.5.1 

func NewStoreInfo(name string, slotLength int, isUnique bool, isValueDataInNodeSegment bool, leafLoadBalancing bool, desciption string) *StoreInfo

NewStoreInfo instantiates a new Store, defaults extended parameters to typical use-case values. Please use NewStoreInfoExtended(..) function below for option to set including the extended parameters.

func NewStoreInfoExt added in v1.8.7 

func NewStoreInfoExt(name string, slotLength int, isUnique bool, isValueDataInNodeSegment bool, isValueDataActivelyPersisted bool, isValueDataGloballyCached bool, leafLoadBalancing bool, desciption string) *StoreInfo

NewStoreInfoExt instantiates a new Store and offers more parameters configurable to your desire.

func (StoreInfo) IsCompatible added in v1.5.1 

func (s StoreInfo) IsCompatible(b StoreInfo) bool

Returns true if another store is compatible with this one spec wise.

func (StoreInfo) IsEmpty added in v1.5.1 

func (s StoreInfo) IsEmpty() bool

Returns true if this StoreInfo is empty, false otherwise. Empty StoreInfo signifies B-Tree does not exist yet.

type StoreInterface 

type StoreInterface[TK Comparable, TV any] struct {
	// NodeRepository is used to manage/access B-Tree nodes.
	NodeRepository NodeRepository[TK, TV]
	// ItemActionTracker is used to track management actions to Items which
	// are geared for resolution & submit on the backend during transaction commit.
	ItemActionTracker ItemActionTracker[TK, TV]
}

StoreInterface contains different repositories needed/used by B-Tree to manage/access its data/objects from a backend.

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.