btree

Documentation

Overview

Package btree implements a generic B-tree data structure.

A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and lookup operations. It's particularly suitable for external storage systems like databases and file systems because it reduces disk I/O operations.

Features:

• Ordered storage with support for sequential element traversal
• Efficient insertion, deletion, and lookup operations with O(log n) time complexity
• Support for range queries
• Support for retrieving first and last elements

Usage Example:

// Create an ordered B-tree for integers
tree := btree.NewOrdered[int]()

// Insert elements
tree.Insert(5)
tree.Insert(3)
tree.Insert(7)

// Check if an element exists
val, found := tree.Search(5) // 5, true

// Traverse elements (in order)
for val := range tree.Iter() {
    fmt.Println(val) // Output: 3, 5, 7
}

// Get elements within a range
lower := 4
upper := 8
for val := range tree.Range(&lower, &upper) {
    fmt.Println(val) // Output: 5, 7
}

Index

• type BTree
  • func New[E any](comparator func(E, E) int) *BTree[E]
  • func NewOrdered[E cmp.Ordered]() *BTree[E]
  • func (t *BTree[E]) First() (E, bool)
  • func (t *BTree[E]) Insert(key E)
  • func (bt *BTree[E]) Iter() iter.Seq[E]
  • func (bt *BTree[E]) IterBack() iter.Seq[E]
  • func (t *BTree[E]) Last() (E, bool)
  • func (t *BTree[E]) Len() int
  • func (t *BTree[E]) PopFirst() (E, bool)
  • func (t *BTree[E]) PopLast() (E, bool)
  • func (bt *BTree[E]) Range(lowerBound, upperBound *E) iter.Seq[E]
  • func (bt *BTree[E]) RangeBack(lowerBound, upperBound *E) iter.Seq[E]
  • func (t *BTree[E]) Remove(key E) bool
  • func (t *BTree[E]) Search(key E) (E, bool)

Types

type BTree

type BTree[E any] struct {
	// contains filtered or unexported fields
}

BTree is a generic B-tree implementation A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and lookup operations, all with O(log n) time complexity

func New

func New[E any](comparator func(E, E) int) *BTree[E]

New creates a new B-tree with the given comparator function The B-tree order is set to a default value and cannot be configured by users

Parameters:

• comparator: A function to compare elements, returning a negative number if a < b, zero if a == b, and a positive number if a > b

Returns:

• A newly created BTree instance

Note: The comparator function cannot be nil, otherwise it will panic

Time Complexity: O(1)

func NewOrdered

func NewOrdered[E cmp.Ordered]() *BTree[E]

NewOrdered creates a new B-tree for ordered element types This is a convenience function that uses cmp.Compare as the comparator

Type Parameters:

• E: The element type, must implement the cmp.Ordered interface

Returns:

• A newly created BTree instance

Time Complexity: O(1)

func (*BTree[E]) First

func (t *BTree[E]) First() (E, bool)

First returns the smallest element in the B-tree

Returns:

• If the tree is non-empty, returns the smallest element and true
• If the tree is empty, returns zero value and false

Time Complexity: O(log n)

func (*BTree[E]) Insert

func (t *BTree[E]) Insert(key E)

Insert adds an element to the B-tree

Parameters:

• key: The element value to insert

Time Complexity: O(log n)

func (*BTree[E]) Iter

func (bt *BTree[E]) Iter() iter.Seq[E]

Iter returns a sequential iterator that traverses all elements in the BTree. Returns:

• An iter.Seq[E] iterator that produces all elements in the BTree in order

func (*BTree[E]) IterBack

func (bt *BTree[E]) IterBack() iter.Seq[E]

IterBack 返回一个逆序迭代器，用于从后向前遍历BTree中的所有元素 返回:

• 一个iter.Seq[E]类型的迭代器，按逆序产生BTree中的所有元素

func (*BTree[E]) Last

func (t *BTree[E]) Last() (E, bool)

Last returns the largest element in the B-tree

Returns:

• If the tree is non-empty, returns the largest element and true
• If the tree is empty, returns zero value and false

Time Complexity: O(log n)

func (*BTree[E]) Len

func (t *BTree[E]) Len() int

Len returns the number of elements in the B-tree

Returns:

• The count of elements in the tree

Time Complexity: O(1)

func (*BTree[E]) PopFirst

func (t *BTree[E]) PopFirst() (E, bool)

PopFirst retrieves and removes the smallest element from the B-tree

Returns:

• If the tree is non-empty, returns the removed smallest element and true
• If the tree is empty, returns zero value and false

Time Complexity: O(log n)

func (*BTree[E]) PopLast

func (t *BTree[E]) PopLast() (E, bool)

PopLast retrieves and removes the largest element from the B-tree

Returns:

• If the tree is non-empty, returns the removed largest element and true
• If the tree is empty, returns zero value and false

Time Complexity: O(log n)

func (*BTree[E]) Range

func (bt *BTree[E]) Range(lowerBound, upperBound *E) iter.Seq[E]

Range returns a range iterator that traverses all elements in the BTree with values in [lowerBound, upperBound). Parameters:

• lowerBound: The lower bound of the range (inclusive); if nil, no lower bound
• upperBound: The upper bound of the range (exclusive); if nil, no upper bound

Returns:

• An iter.Seq[E] iterator that produces all elements in the specified range in order

func (*BTree[E]) RangeBack

func (bt *BTree[E]) RangeBack(lowerBound, upperBound *E) iter.Seq[E]

RangeBack returns a reverse iterator that traverses all elements in the BTree with values in [lowerBound, upperBound) 参数:

• lowerBound: 范围的下界（包含），如果为nil则没有下界
• upperBound: 范围的上界（不包含），如果为nil则没有上界

返回:

• 一个iter.Seq[E]类型的迭代器，按逆序产生指定范围内的所有元素

func (*BTree[E]) Remove

func (t *BTree[E]) Remove(key E) bool

Remove deletes an element from the B-tree

Parameters:

• key: The element value to delete

Returns:

• true if the element existed and was successfully deleted
• false if the element didn't exist

Time Complexity: O(log n)

func (*BTree[E]) Search

func (t *BTree[E]) Search(key E) (E, bool)

Search looks up an element in the B-tree, returning the value and true if found, or zero value and false if not found

Parameters:

• key: The element value to search for

Returns:

• If the element exists, returns the element value and true
• If the element doesn't exist, returns zero value and false

Time Complexity: O(log n)