btree

package
v1.8.8-0...-edaca3c Latest Latest
Warning

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

Go to latest
Published: Jul 22, 2026 License: MIT Imports: 11 Imported by: 0

Documentation

Overview

Package btree provides the core B-Tree data structure and algorithms used by SOP. It defines generic node/item types and storage interfaces to support multiple backends.

This B-tree can distribute items added on a given leaf sub-branch so it tends to fill nodes of that sub-branch. Instead of ~50% average fill (typical), each node can achieve higher average utilization, commonly 62%–75%. The logic operates within a given sub-branch to avoid broader performance impact and can be disabled.

"Leaf sub-branch" refers to the outermost branch whose children have no further descendants. A "leaf" node is an edge node with no children.

Index

Constants

View Source
const DefaultSlotLength = 5000

Default Slot Length is 5000.

Variables

This section is empty.

Functions

func CoerceComparer

func CoerceComparer(anyX any) func(x, y any) int

CoerceComparer returns a type-appropriate comparer function for values similar to anyX. It specializes for common built-in types, UUIDs, time.Time, and Comparer implementations.

func Compare

func Compare(anyX, anyY any) int

Compare compares two values, handling common built-in types, UUIDs, time.Time, Comparer implementations, and finally falling back to string comparison.

func IsPrimitive

func IsPrimitive[TK any]() bool

IsPrimitive returns true if data type is primitive type.

func NewBtreeWithTransaction

func NewBtreeWithTransaction[TK Ordered, TV any](t sop.TwoPhaseCommitTransaction, btree BtreeInterface[TK, TV]) *btreeWithTransaction[TK, TV]

NewBtreeWithTransaction wraps a B-tree with a transaction session, enforcing that operations are run only when a transaction has begun and in the correct mode.

Types

type Btree

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

Btree manages items using a B-tree data structure and algorithm. TK (Key Type) can be any comparable type, including complex structs. Using a struct as TK allows the B-Tree to act as a "Covering Index", where metadata is stored directly in the key and available during traversal without fetching the Value (TV).

func New

func New[TK Ordered, TV any](storeInfo *sop.StoreInfo, si *StoreInterface[TK, TV], comparer ComparerFunc[TK]) (*Btree[TK, TV], error)

New creates a new Btree instance. comparer can be provided to override default comparison for TK.

func (*Btree[TK, TV]) Add

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

Add inserts a key/value pair into the tree.

func (*Btree[TK, TV]) AddIfNotExist

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

AddIfNotExist inserts the item only when a duplicate key does not exist (temporarily enabling uniqueness).

func (*Btree[TK, TV]) AddItem

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

AddItem is used internally during refetch/merge in commit to add an already-constructed Item.

func (*Btree[TK, TV]) Count

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

Count returns the number of items in the B-tree.

func (*Btree[TK, TV]) Find

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

Find searches for the key and positions the cursor to the first or exact match depending on firstItemWithKey.

func (*Btree[TK, TV]) FindInDescendingOrder

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

FindInDescendingOrder is analogous to Find but is useful when doing search item and retrieval will be in descending order. Use Previous to navigate backwards.

func (*Btree[TK, TV]) FindWithID

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

FindWithID searches for the key and then walks duplicates until the specified ID is matched.

func (*Btree[TK, TV]) First

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

First positions the cursor at the first item according to key ordering.

func (*Btree[TK, TV]) GetCurrentItem

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

GetCurrentItem returns the current item including key and value, fetching value if necessary.

func (*Btree[TK, TV]) GetCurrentItemNoLock

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

GetCurrentItemNoLock returns the current item without read lock hint. Use this when managing locks explicitly (e.g., in SQL layer).

func (*Btree[TK, TV]) GetCurrentKey

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

GetCurrentKey returns the current item's key and ID.

func (*Btree[TK, TV]) GetCurrentValue

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

GetCurrentValue returns the current item's value, fetching it if necessary.

func (*Btree[TK, TV]) GetCurrentValueNoLock

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

GetCurrentValueNoLock returns the current item's value without registering a read lock hint. This is useful when the caller manages locking explicitly (e.g., SQL layer with explicit lock management).

func (*Btree[TK, TV]) GetStoreInfo

func (btree *Btree[TK, TV]) GetStoreInfo() sop.StoreInfo

GetStoreInfo returns the StoreInfo describing this B-tree instance.

func (*Btree[TK, TV]) IsUnique

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

IsUnique reports whether the B-tree is configured to store unique keys.

func (*Btree[TK, TV]) IsValueDataInNodeSegment

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

IsValueDataInNodeSegment reports whether Values are stored in the node segment with Keys.

func (*Btree[TK, TV]) Last

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

Last positions the cursor at the last item according to key ordering.

func (*Btree[TK, TV]) Lock

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

Lock acquires any locks required by the underlying store for read or write access.

func (*Btree[TK, TV]) Next

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

Next advances the cursor to the next item.

func (*Btree[TK, TV]) Previous

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

Previous moves the cursor to the previous item.

func (*Btree[TK, TV]) RLockCurrentItem

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

RLockCurrentItem registers the current item for read lock (version check) on Commit without returning the value. This is useful when you need to lock an item for consistency checking but don't need to read its value.

func (*Btree[TK, TV]) Remove

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

Remove deletes the item matching the given key.

func (*Btree[TK, TV]) RemoveCurrentItem

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

RemoveCurrentItem deletes the item at the current cursor position.

func (*Btree[TK, TV]) Update

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

Update finds the item with matching key and calls UpdateCurrentItem to update it.

func (*Btree[TK, TV]) UpdateCurrentItem

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

UpdateCurrentItem updates the current item with the incoming key & value.

func (*Btree[TK, TV]) UpdateCurrentItemWithItem

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

UpdateCurrentNodeItem is used internally during refetch/merge in commit to replace the current item.

func (*Btree[TK, TV]) UpdateCurrentKey

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

UpdateCurrentKey updates the current item with the provided key.

func (*Btree[TK, TV]) UpdateCurrentValue

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

UpdateCurrentValue updates the value of the current item.

func (*Btree[TK, TV]) UpdateKey

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

UpdateKey finds the item with matching key and updates its key.

func (*Btree[TK, TV]) Upsert

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

Upsert adds the item if it does not exist or updates it when it does.

type BtreeInterface

type BtreeInterface[TK Ordered, 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 does nothing and returns false.
	// This is useful when adding an item without creating a duplicate entry.
	AddIfNotExist(ctx context.Context, key TK, value TV) (bool, error)

	// Update finds the item with key and calls UpdateCurrentValue to update it.
	Update(ctx context.Context, key TK, value TV) (bool, error)

	// UpdateKey finds the item with key and updates its Key to the incoming key argument.
	UpdateKey(ctx context.Context, key TK) (bool, error)

	// UpdateCurrentKey updates the Key of the current item but only allows if key does not affect ordering.
	UpdateCurrentKey(ctx context.Context, key TK) (bool, error)
	// UpdateCurrentValue updates the Value of the current item.
	UpdateCurrentValue(ctx context.Context, newValue TV) (bool, error)

	// UpdateCurrentItem updates the current item with the incoming key & value.
	// This is a convenience method that combines UpdateCurrentKey and UpdateCurrentValue but
	// only allows if key does not affect ordering.
	UpdateCurrentItem(ctx context.Context, key TK, value TV) (bool, error)

	// Upsert adds the item if it does not exist or updates it if it does.
	Upsert(ctx context.Context, key TK, value TV) (bool, error)

	// Remove finds the item with a given key then removes that item.
	Remove(ctx context.Context, key TK) (bool, error)
	// RemoveCurrentItem removes the current key/value pair from the store.
	RemoveCurrentItem(ctx context.Context) (bool, error)

	// Find searches the B-tree for an item with a given key. Returns true if found,
	// otherwise false. firstItemWithKey is useful when there are items with the same key:
	// true positions the cursor to the first item with the given key according to ordering.
	// Use GetCurrentKey/GetCurrentValue to retrieve the current item's details.
	Find(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)
	// FindWithID is synonymous to Find but allows code to supply the Item's ID to identify it.
	// This is useful for B-tree configurations that allow duplicate keys (IsUnique = false),
	// as it provides a way to differentiate duplicates via the unique ID (sop.UUID).
	FindWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)

	// FindInDescendingOrder is analogous to Find but is useful when doing search item and
	// retrieval will be in descending order. Use Previous to navigate backwards.
	FindInDescendingOrder(ctx context.Context, key TK) (bool, error)

	// GetCurrentKey returns the current item's key (and Item ID). If the B-tree allows duplicates,
	// having the Item ID available allows finding that item conveniently (see FindWithID).
	GetCurrentKey() Item[TK, TV]
	// GetCurrentValue returns the current item's value with read lock hint for transaction commit.
	GetCurrentValue(ctx context.Context) (TV, error)
	// GetCurrentValueNoLock returns the current item's value without read lock hint.
	// Use this when managing locks explicitly (e.g., in SQL layer).
	GetCurrentValueNoLock(ctx context.Context) (TV, error)
	// GetCurrentItem returns the current item.
	GetCurrentItem(ctx context.Context) (Item[TK, TV], error)
	// GetCurrentItemNoLock returns the current item without read lock hint.
	// Use this when managing locks explicitly (e.g., in SQL layer).
	GetCurrentItemNoLock(ctx context.Context) (Item[TK, TV], error)

	// RLockCurrentItem registers the current item for read lock (version check) on Commit.
	// Use this when you need to lock an item without fetching its value.
	RLockCurrentItem(ctx context.Context) error

	// First positions the cursor to the first item as per key ordering.
	// Use GetCurrentKey/GetCurrentValue to retrieve the current item.
	First(ctx context.Context) (bool, error)
	// Last positions the cursor to the last item as per key ordering.
	// Use GetCurrentKey/GetCurrentValue to retrieve the current item.
	Last(ctx context.Context) (bool, error)
	// Next positions the cursor to the next item as per key ordering.
	// Use GetCurrentKey/GetCurrentValue to retrieve the current item.
	Next(ctx context.Context) (bool, error)
	// Previous positions the cursor to the previous item as per key ordering.
	// Use GetCurrentKey/GetCurrentValue to retrieve the current item.
	Previous(ctx context.Context) (bool, error)

	// IsUnique returns true if the B-tree is configured to store items with unique keys.
	// If you only need a uniqueness check when adding an item, use AddIfNotExist instead.
	IsUnique() bool

	// Count returns the number of items in this B-tree.
	Count() int64

	// GetStoreInfo returns StoreInfo which contains the details about this B-tree.
	GetStoreInfo() sop.StoreInfo
}

BtreeInterface defines the public API of the Btree.

type Comparer

type Comparer interface {
	// Compare compares this object with the other and returns -1, 0, or 1.
	// -1 means this < other, 0 means equal, 1 means this > other.
	Compare(other interface{}) int
}

Comparer specifies how to compare this value against another value.

type ComparerFunc

type ComparerFunc[TK Ordered] func(a TK, b TK) int

ComparerFunc allows providing a comparer function separate from the key object.

type Cursor

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

Cursor is a Btree cursor, it allows iteration on an underlying Btree and behaves like it is the Btree though it is not. It only holds the current item reference "state".

func NewCursor

func NewCursor[TK Ordered, TV any](btree *Btree[TK, TV]) *Cursor[TK, TV]

func (*Cursor[TK, TV]) Add

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

Add adds a key/value.

func (*Cursor[TK, TV]) AddIfNotExist

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

AddIfNotExist adds only when no duplicate key exists.

func (*Cursor[TK, TV]) Find

func (b3 *Cursor[TK, TV]) Find(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)

Find positions the cursor on an exact/first match; requires begun transaction.

func (*Cursor[TK, TV]) FindInDescendingOrder

func (b3 *Cursor[TK, TV]) FindInDescendingOrder(ctx context.Context, key TK) (bool, error)

FindInDescendingOrder positions the cursor on a match for descending iteration; requires begun transaction.

func (*Cursor[TK, TV]) FindWithID

func (b3 *Cursor[TK, TV]) FindWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)

FindWithID positions the cursor on a match with specific ID; requires begun transaction.

func (*Cursor[TK, TV]) First

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

First positions the cursor at the smallest key.

func (*Cursor[TK, TV]) GetCurrentItem

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

GetCurrentItem returns the current item; requires begun transaction.

func (*Cursor[TK, TV]) GetCurrentItemNoLock

func (b3 *Cursor[TK, TV]) GetCurrentItemNoLock(ctx context.Context) (Item[TK, TV], error)

func (*Cursor[TK, TV]) GetCurrentKey

func (b3 *Cursor[TK, TV]) GetCurrentKey() Item[TK, TV]

GetCurrentKey returns the current key/ID; returns zero value if no transaction.

func (*Cursor[TK, TV]) GetCurrentValue

func (b3 *Cursor[TK, TV]) GetCurrentValue(ctx context.Context) (TV, error)

GetCurrentValue returns the current value; requires begun transaction.

func (*Cursor[TK, TV]) GetCurrentValueNoLock

func (b3 *Cursor[TK, TV]) GetCurrentValueNoLock(ctx context.Context) (TV, error)

GetCurrentValueNoLock returns the current value without read lock hint.

func (*Cursor[TK, TV]) Last

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

Last positions the cursor at the largest key.

func (*Cursor[TK, TV]) Next

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

Next advances the cursor forward; requires begun transaction.

func (*Cursor[TK, TV]) Previous

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

Previous moves the cursor backward.

func (*Cursor[TK, TV]) RLockCurrentItem

func (b3 *Cursor[TK, TV]) RLockCurrentItem(ctx context.Context) error

RLockCurrentItem registers the current item for read lock.

func (*Cursor[TK, TV]) Remove

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

Remove finds by key and deletes.

func (*Cursor[TK, TV]) RemoveCurrentItem

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

RemoveCurrentItem deletes the current item.

func (*Cursor[TK, TV]) Update

func (b3 *Cursor[TK, TV]) Update(ctx context.Context, key TK, value TV) (bool, error)

Update finds by key and updates value.

func (*Cursor[TK, TV]) UpdateCurrentItem

func (b3 *Cursor[TK, TV]) UpdateCurrentItem(ctx context.Context, key TK, value TV) (bool, error)

UpdateCurrentItem updates the current item.

func (*Cursor[TK, TV]) UpdateCurrentKey

func (b3 *Cursor[TK, TV]) UpdateCurrentKey(ctx context.Context, key TK) (bool, error)

UpdateCurrentKey updates the current item's key.

func (*Cursor[TK, TV]) UpdateCurrentValue

func (b3 *Cursor[TK, TV]) UpdateCurrentValue(ctx context.Context, value TV) (bool, error)

UpdateCurrentValue updates the current item.

func (*Cursor[TK, TV]) UpdateKey

func (b3 *Cursor[TK, TV]) UpdateKey(ctx context.Context, key TK) (bool, error)

UpdateKey finds by key and updates key.

func (*Cursor[TK, TV]) Upsert

func (b3 *Cursor[TK, TV]) Upsert(ctx context.Context, key TK, value TV) (bool, error)

Upsert inserts or updates depending on existence.

type Item

type Item[TK Ordered, TV any] struct {
	// (Internal) ID is the Item's sop.UUID. ID is needed for two reasons:
	// 1. so the B-tree can identify or differentiate items with duplicated keys.
	// 2. used as the value data ID if the item's value is persisted in another
	//    data segment, separate from the node segment (IsValueDataInNodeSegment=false).
	ID sop.UUID `json:"ID"`
	// Key is the key part in the key/value pair.
	Key TK `json:"Key"`
	// Value is nil when data is persisted in the separate data segment (with ValueID set to a valid sop.UUID);
	// otherwise it points to the actual data and is persisted in the B-tree node segment together with the key.
	Value *TV `json:"Value,omitempty"`
	// Version is used for conflict resolution among in-flight transactions.
	Version int32 `json:"Version"`
	// ValueNeedsFetch tells the B-tree whether the value data needs fetching.
	// Applicable only when IsValueDataInNodeSegment is false.
	ValueNeedsFetch bool `json:"ValueNeedsFetch,omitempty"`
	// contains filtered or unexported fields
}

Item contains a key/value pair and a version number.

type ItemActionTracker

type ItemActionTracker[TK Ordered, TV any] interface {
	// Add caches the add action for submit on transaction commit.
	Add(ctx context.Context, item *Item[TK, TV]) error
	// Get caches the get action to be resolved on transaction commit, comparing version
	// with the backend copy and erroring if another transaction modified/deleted the item.
	Get(ctx context.Context, item *Item[TK, TV]) error
	// Update caches the update action for submit on transaction commit.
	Update(ctx context.Context, item *Item[TK, TV]) error
	// Remove caches the remove action for submit on transaction commit.
	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

type MetaDataType interface {
	// GetID returns the object's ID.
	GetID() sop.UUID
	// GetVersion returns the object's version.
	GetVersion() int32
	// SetVersion applies a version to the object.
	SetVersion(v int32)
}

MetaDataType specifies metadata fields such as ID and Version.

type Node

type Node[TK Ordered, TV any] struct {
	ID       sop.UUID `json:"ID"`
	ParentID sop.UUID `json:"ParentID"`
	// Slots is an array where the Items get stored.
	Slots []Item[TK, TV] `json:"Slots"`
	// Count of items in this node.
	Count int `json:"Count"`
	// Version of this node.
	Version int32 `json:"Version"`
	// ChildrenIDs holds the IDs of this node's children.
	ChildrenIDs []sop.UUID `json:"ChildrenIDs,omitempty"`
	// contains filtered or unexported fields
}

Node contains a B-Tree node's data.

func (*Node[TK, TV]) Clone

func (n *Node[TK, TV]) Clone() *Node[TK, TV]

Clone returns a deep copy of the node, preserving the current slot capacity while copying the contents of the slots and child IDs.

func (*Node[TK, TV]) CloneMetaData

func (n *Node[TK, TV]) CloneMetaData() MetaDataType

CloneMetaData returns a metadata-safe clone of the node for cache use.

func (*Node[TK, TV]) CopyTo

func (n *Node[TK, TV]) CopyTo(dst any) bool

CopyTo copies this node into an existing destination node, reusing any pre-allocated backing slices on the destination when possible.

func (*Node[TK, TV]) GetID

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

GetID returns the node's UUID.

func (*Node[TK, TV]) GetVersion

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

GetVersion returns the node's version.

func (*Node[TK, TV]) MarshalJSON

func (n *Node[TK, TV]) MarshalJSON() ([]byte, error)

func (*Node[TK, TV]) SetVersion

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

SetVersion updates the node's version to v.

func (*Node[TK, TV]) UnmarshalJSON

func (n *Node[TK, TV]) UnmarshalJSON(data []byte) error

type NodeRepository

type NodeRepository[TK Ordered, TV any] interface {
	// Add caches the add action for submit on transaction commit.
	Add(node *Node[TK, TV])
	// Get fetches from backend (or cache if present) and returns the Node with the given nodeID.
	Get(ctx context.Context, nodeID sop.UUID) (*Node[TK, TV], error)
	// Fetched marks the Node with nodeID as fetched so it will be checked for version conflict during commit.
	Fetched(nodeID sop.UUID)
	// Update caches the update action for resolution on transaction commit.
	Update(node *Node[TK, TV])
	// Remove caches the remove action for resolution on transaction commit.
	Remove(nodeID sop.UUID)
}

NodeRepository specifies the node repository used by the B-tree.

type Ordered

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

Ordered constrains key types that can be stored in a Btree. It permits built-in ordered types, UUIDs, Comparer implementations, and any as a fallback.

type StoreInterface

type StoreInterface[TK Ordered, TV any] struct {
	// NodeRepository is used to manage/access B-tree nodes.
	NodeRepository NodeRepository[TK, TV]
	// ItemActionTracker tracks management actions to Items which are resolved and submitted
	// to the backend during transaction commit.
	ItemActionTracker ItemActionTracker[TK, TV]
}

StoreInterface bundles the repositories the B-tree uses to manage/access its data/objects from a backend.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL