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
- func CoerceComparer(anyX any) func(x, y any) int
- func Compare(anyX, anyY any) int
- func IsPrimitive[TK any]() bool
- func NewBtreeWithTransaction[TK Ordered, TV any](t sop.TwoPhaseCommitTransaction, btree BtreeInterface[TK, TV]) *btreeWithTransaction[TK, TV]
- type Btree
- func (btree *Btree[TK, TV]) Add(ctx context.Context, key TK, value TV) (bool, error)
- func (btree *Btree[TK, TV]) AddIfNotExist(ctx context.Context, key TK, value TV) (bool, error)
- func (btree *Btree[TK, TV]) AddItem(ctx context.Context, item *Item[TK, TV]) (bool, error)
- func (btree *Btree[TK, TV]) Count() int64
- func (btree *Btree[TK, TV]) Find(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)
- func (btree *Btree[TK, TV]) FindInDescendingOrder(ctx context.Context, key TK) (bool, error)
- func (btree *Btree[TK, TV]) FindWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)
- func (btree *Btree[TK, TV]) First(ctx context.Context) (bool, error)
- func (btree *Btree[TK, TV]) GetCurrentItem(ctx context.Context) (Item[TK, TV], error)
- func (btree *Btree[TK, TV]) GetCurrentItemNoLock(ctx context.Context) (Item[TK, TV], error)
- func (btree *Btree[TK, TV]) GetCurrentKey() Item[TK, TV]
- func (btree *Btree[TK, TV]) GetCurrentValue(ctx context.Context) (TV, error)
- func (btree *Btree[TK, TV]) GetCurrentValueNoLock(ctx context.Context) (TV, error)
- func (btree *Btree[TK, TV]) GetStoreInfo() sop.StoreInfo
- func (btree *Btree[TK, TV]) IsUnique() bool
- func (btree *Btree[TK, TV]) IsValueDataInNodeSegment() bool
- func (btree *Btree[TK, TV]) Last(ctx context.Context) (bool, error)
- func (btree *Btree[TK, TV]) Lock(ctx context.Context, forWriting bool) error
- func (btree *Btree[TK, TV]) Next(ctx context.Context) (bool, error)
- func (btree *Btree[TK, TV]) Previous(ctx context.Context) (bool, error)
- func (btree *Btree[TK, TV]) RLockCurrentItem(ctx context.Context) error
- func (btree *Btree[TK, TV]) Remove(ctx context.Context, key TK) (bool, error)
- func (btree *Btree[TK, TV]) RemoveCurrentItem(ctx context.Context) (bool, error)
- func (btree *Btree[TK, TV]) Update(ctx context.Context, key TK, newValue TV) (bool, error)
- func (btree *Btree[TK, TV]) UpdateCurrentItem(ctx context.Context, key TK, value TV) (bool, error)
- func (btree *Btree[TK, TV]) UpdateCurrentItemWithItem(ctx context.Context, item *Item[TK, TV]) (bool, error)
- func (btree *Btree[TK, TV]) UpdateCurrentKey(ctx context.Context, key TK) (bool, error)
- func (btree *Btree[TK, TV]) UpdateCurrentValue(ctx context.Context, newValue TV) (bool, error)
- func (btree *Btree[TK, TV]) UpdateKey(ctx context.Context, key TK) (bool, error)
- func (btree *Btree[TK, TV]) Upsert(ctx context.Context, key TK, value TV) (bool, error)
- type BtreeInterface
- type Comparer
- type ComparerFunc
- type Cursor
- func (b3 *Cursor[TK, TV]) Add(ctx context.Context, key TK, value TV) (bool, error)
- func (b3 *Cursor[TK, TV]) AddIfNotExist(ctx context.Context, key TK, value TV) (bool, error)
- func (b3 *Cursor[TK, TV]) Find(ctx context.Context, key TK, firstItemWithKey bool) (bool, error)
- func (b3 *Cursor[TK, TV]) FindInDescendingOrder(ctx context.Context, key TK) (bool, error)
- func (b3 *Cursor[TK, TV]) FindWithID(ctx context.Context, key TK, id sop.UUID) (bool, error)
- func (b3 *Cursor[TK, TV]) First(ctx context.Context) (bool, error)
- func (b3 *Cursor[TK, TV]) GetCurrentItem(ctx context.Context) (Item[TK, TV], error)
- func (b3 *Cursor[TK, TV]) GetCurrentItemNoLock(ctx context.Context) (Item[TK, TV], error)
- func (b3 *Cursor[TK, TV]) GetCurrentKey() Item[TK, TV]
- func (b3 *Cursor[TK, TV]) GetCurrentValue(ctx context.Context) (TV, error)
- func (b3 *Cursor[TK, TV]) GetCurrentValueNoLock(ctx context.Context) (TV, error)
- func (b3 *Cursor[TK, TV]) Last(ctx context.Context) (bool, error)
- func (b3 *Cursor[TK, TV]) Next(ctx context.Context) (bool, error)
- func (b3 *Cursor[TK, TV]) Previous(ctx context.Context) (bool, error)
- func (b3 *Cursor[TK, TV]) RLockCurrentItem(ctx context.Context) error
- func (b3 *Cursor[TK, TV]) Remove(ctx context.Context, key TK) (bool, error)
- func (b3 *Cursor[TK, TV]) RemoveCurrentItem(ctx context.Context) (bool, error)
- func (b3 *Cursor[TK, TV]) Update(ctx context.Context, key TK, value TV) (bool, error)
- func (b3 *Cursor[TK, TV]) UpdateCurrentItem(ctx context.Context, key TK, value TV) (bool, error)
- func (b3 *Cursor[TK, TV]) UpdateCurrentKey(ctx context.Context, key TK) (bool, error)
- func (b3 *Cursor[TK, TV]) UpdateCurrentValue(ctx context.Context, value TV) (bool, error)
- func (b3 *Cursor[TK, TV]) UpdateKey(ctx context.Context, key TK) (bool, error)
- func (b3 *Cursor[TK, TV]) Upsert(ctx context.Context, key TK, value TV) (bool, error)
- type Item
- type ItemActionTracker
- type MetaDataType
- type Node
- func (n *Node[TK, TV]) Clone() *Node[TK, TV]
- func (n *Node[TK, TV]) CloneMetaData() MetaDataType
- func (n *Node[TK, TV]) CopyTo(dst any) bool
- func (n *Node[TK, TV]) GetID() sop.UUID
- func (n *Node[TK, TV]) GetVersion() int32
- func (n *Node[TK, TV]) MarshalJSON() ([]byte, error)
- func (n *Node[TK, TV]) SetVersion(v int32)
- func (n *Node[TK, TV]) UnmarshalJSON(data []byte) error
- type NodeRepository
- type Ordered
- type StoreInterface
Constants ¶
const DefaultSlotLength = 5000
Default Slot Length is 5000.
Variables ¶
This section is empty.
Functions ¶
func CoerceComparer ¶
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 ¶
Compare compares two values, handling common built-in types, UUIDs, time.Time, Comparer implementations, and finally falling back to string comparison.
func IsPrimitive ¶
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]) AddIfNotExist ¶
AddIfNotExist inserts the item only when a duplicate key does not exist (temporarily enabling uniqueness).
func (*Btree[TK, TV]) AddItem ¶
AddItem is used internally during refetch/merge in commit to add an already-constructed Item.
func (*Btree[TK, TV]) Find ¶
Find searches for the key and positions the cursor to the first or exact match depending on firstItemWithKey.
func (*Btree[TK, TV]) FindInDescendingOrder ¶
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 ¶
FindWithID searches for the key and then walks duplicates until the specified ID is matched.
func (*Btree[TK, TV]) First ¶
First positions the cursor at the first item according to key ordering.
func (*Btree[TK, TV]) GetCurrentItem ¶
GetCurrentItem returns the current item including key and value, fetching value if necessary.
func (*Btree[TK, TV]) GetCurrentItemNoLock ¶
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 ¶
GetCurrentKey returns the current item's key and ID.
func (*Btree[TK, TV]) GetCurrentValue ¶
GetCurrentValue returns the current item's value, fetching it if necessary.
func (*Btree[TK, TV]) GetCurrentValueNoLock ¶
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 ¶
GetStoreInfo returns the StoreInfo describing this B-tree instance.
func (*Btree[TK, TV]) IsUnique ¶
IsUnique reports whether the B-tree is configured to store unique keys.
func (*Btree[TK, TV]) IsValueDataInNodeSegment ¶
IsValueDataInNodeSegment reports whether Values are stored in the node segment with Keys.
func (*Btree[TK, TV]) Lock ¶
Lock acquires any locks required by the underlying store for read or write access.
func (*Btree[TK, TV]) RLockCurrentItem ¶
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]) RemoveCurrentItem ¶
RemoveCurrentItem deletes the item at the current cursor position.
func (*Btree[TK, TV]) Update ¶
Update finds the item with matching key and calls UpdateCurrentItem to update it.
func (*Btree[TK, TV]) UpdateCurrentItem ¶
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 ¶
UpdateCurrentKey updates the current item with the provided key.
func (*Btree[TK, TV]) UpdateCurrentValue ¶
UpdateCurrentValue updates the value of the current item.
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 ¶
ComparerFunc allows providing a comparer function separate from the key object.
type Cursor ¶
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 (*Cursor[TK, TV]) AddIfNotExist ¶
AddIfNotExist adds only when no duplicate key exists.
func (*Cursor[TK, TV]) Find ¶
Find positions the cursor on an exact/first match; requires begun transaction.
func (*Cursor[TK, TV]) FindInDescendingOrder ¶
FindInDescendingOrder positions the cursor on a match for descending iteration; requires begun transaction.
func (*Cursor[TK, TV]) FindWithID ¶
FindWithID positions the cursor on a match with specific ID; requires begun transaction.
func (*Cursor[TK, TV]) GetCurrentItem ¶
GetCurrentItem returns the current item; requires begun transaction.
func (*Cursor[TK, TV]) GetCurrentItemNoLock ¶
func (*Cursor[TK, TV]) GetCurrentKey ¶
GetCurrentKey returns the current key/ID; returns zero value if no transaction.
func (*Cursor[TK, TV]) GetCurrentValue ¶
GetCurrentValue returns the current value; requires begun transaction.
func (*Cursor[TK, TV]) GetCurrentValueNoLock ¶
GetCurrentValueNoLock returns the current value without read lock hint.
func (*Cursor[TK, TV]) RLockCurrentItem ¶
RLockCurrentItem registers the current item for read lock.
func (*Cursor[TK, TV]) RemoveCurrentItem ¶
RemoveCurrentItem deletes the current item.
func (*Cursor[TK, TV]) UpdateCurrentItem ¶
UpdateCurrentItem updates the current item.
func (*Cursor[TK, TV]) UpdateCurrentKey ¶
UpdateCurrentKey updates the current item's key.
func (*Cursor[TK, TV]) UpdateCurrentValue ¶
UpdateCurrentValue updates the current item.
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 ¶
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 ¶
CopyTo copies this node into an existing destination node, reusing any pre-allocated backing slices on the destination when possible.
func (*Node[TK, TV]) GetVersion ¶
GetVersion returns the node's version.
func (*Node[TK, TV]) MarshalJSON ¶
func (*Node[TK, TV]) SetVersion ¶
SetVersion updates the node's version to v.
func (*Node[TK, TV]) UnmarshalJSON ¶
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 ¶
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.