Documentation
¶
Overview ¶
Package btree implements a B-tree for ordered key-value storage.
A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
Properties of a B-Tree of order m: - Every node has at most m children. - Every non-leaf node (except root) has at least ⌈m/2⌉ children. - The root has at least two children if it is not a leaf node. - A non-leaf node with k children contains k−1 keys. - All leaves appear at the same level.
This implementation is not thread-safe.
References: https://en.wikipedia.org/wiki/B-tree
Index ¶
- type Node
- type Tree
- func (t *Tree[K, V]) Begin() (k K, v V, ok bool)
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Clone() container.Map[K, V]
- func (t *Tree[K, V]) Comparator() cmp.Comparator[K]
- func (t *Tree[K, V]) Delete(key K) (v V, found bool)
- func (t *Tree[K, V]) DeleteBegin() (k K, v V, ok bool)
- func (t *Tree[K, V]) DeleteEnd() (k K, v V, ok bool)
- func (t *Tree[K, V]) End() (k K, v V, ok bool)
- func (t *Tree[K, V]) Entries() ([]K, []V)
- func (t *Tree[K, V]) Get(key K) (V, bool)
- func (tree *Tree[K, V]) GetBeginNode() *Node[K, V]
- func (tree *Tree[K, V]) GetEndNode() *Node[K, V]
- func (t *Tree[K, V]) GetNode(key K) *Node[K, V]
- func (t *Tree[K, V]) Has(key K) bool
- func (t *Tree[K, V]) Height() int
- func (t *Tree[K, V]) IsEmpty() bool
- func (t *Tree[K, V]) Iter() iter.Seq2[K, V]
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Len() int
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) MaxChildren() int
- func (t *Tree[K, V]) Put(key K, value V)
- func (t *Tree[K, V]) RIter() iter.Seq2[K, V]
- func (t *Tree[K, V]) Root() *Node[K, V]
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) ToSlice() []V
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K comparable, V any] struct { // contains filtered or unexported fields }
Node is a single element within the tree, containing entries and children.
func (*Node[K, V]) Entries ¶
func (n *Node[K, V]) Entries() []*entry[K, V]
Entries returns the key-value pairs of the node.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree holds the elements and configuration of the B-tree.
func New ¶
New creates a new B-tree with the specified order and a built-in comparator. The order `m` must be 3 or greater. Panics if order is invalid. K must be an ordered type (e.g., int, string). Time complexity: O(1).
func NewWith ¶
func NewWith[K comparable, V any](order int, cmp cmp.Comparator[K]) *Tree[K, V]
NewWith creates a new B-tree with a custom comparator. The order `m` must be 3 or greater. Panics if order is invalid. Time complexity: O(1).
func (*Tree[K, V]) Begin ¶ added in v0.6.1
Begin returns the minimum key-value pair. Time complexity: O(log n).
func (*Tree[K, V]) Clear ¶
func (t *Tree[K, V]) Clear()
Clear removes all items from the tree. Time complexity: O(1).
func (*Tree[K, V]) Clone ¶ added in v0.5.0
Clone creates a deep copy of the tree. Time complexity: O(n).
func (*Tree[K, V]) Comparator ¶
func (t *Tree[K, V]) Comparator() cmp.Comparator[K]
Comparator returns the comparator used by the tree.
func (*Tree[K, V]) Delete ¶ added in v0.5.0
Delete removes a key-value pair from the tree. Returns the value and true if the key was found and removed, false otherwise. Time complexity: O(log n).
func (*Tree[K, V]) DeleteBegin ¶ added in v0.6.1
DeleteBegin removes the minimum key-value pair. Returns the removed pair and true, or zero values and false if the tree is empty. Time complexity: O(log n).
func (*Tree[K, V]) DeleteEnd ¶ added in v0.6.1
DeleteEnd removes the maximum key-value pair. Returns the removed pair and true, or zero values and false if the tree is empty. Time complexity: O(log n).
func (*Tree[K, V]) End ¶ added in v0.6.1
End returns the maximum key-value pair. Time complexity: O(log n).
func (*Tree[K, V]) Entries ¶ added in v0.6.1
func (t *Tree[K, V]) Entries() ([]K, []V)
Entries returns slices of all keys and values in sorted order. Time complexity: O(n).
func (*Tree[K, V]) Get ¶
Get retrieves the value for a given key. Returns the value and true if found, or the zero value and false otherwise. Time complexity: O(log n).
func (*Tree[K, V]) GetBeginNode ¶ added in v0.6.1
GetBeginNode returns the node with the minimum key. Returns nil if the tree is empty. Time complexity: O(log n).
func (*Tree[K, V]) GetEndNode ¶ added in v0.6.1
GetEndNode returns the node with the maximum key. Returns nil if the tree is empty. Time complexity: O(log n).
func (*Tree[K, V]) GetNode ¶
GetNode retrieves the node containing the given key. Returns the node if found, nil otherwise. Time complexity: O(log n).
func (*Tree[K, V]) Has ¶ added in v0.5.0
Has checks if a key exists in the tree. Time complexity: O(log n).
func (*Tree[K, V]) Height ¶
Height returns the height of the tree. A tree with a single node has a height of 1. Returns 0 if the tree is empty. Time complexity: O(log n).
func (*Tree[K, V]) IsEmpty ¶ added in v0.6.1
IsEmpty returns true if the tree has no items. Time complexity: O(1).
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Keys returns a slice of all keys in sorted order. Time complexity: O(n).
func (*Tree[K, V]) Len ¶ added in v0.5.0
Len returns the number of items in the tree. Time complexity: O(1).
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON implements the json.Marshaler interface. Time complexity: O(n).
func (*Tree[K, V]) MaxChildren ¶ added in v0.6.0
MaxChildren returns the maximum number of children allowed in a node.
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, value V)
Put inserts a key-value pair into the tree, updating the value if the key already exists. Time complexity: O(log n).
func (*Tree[K, V]) ToSlice ¶ added in v0.6.1
func (t *Tree[K, V]) ToSlice() []V
ToSlice returns a slice of all key-value pairs in sorted order. Time complexity: O(n).
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface. Time complexity: O(m log m).
Source Files