Documentation
¶
Overview ¶
Package btree implements a disk-backed B+Tree primitive.
Index ¶
Constants ¶
const ( MaxKeySize = 128 MaxValueSize = 1024 )
const (
// PageSize is the standard size for a B+Tree page (4KB)
PageSize = 4096
)
Variables ¶
var (
ErrPageNotFound = errors.New("page not found")
)
Functions ¶
This section is empty.
Types ¶
type Cursor ¶
type Cursor struct {
// contains filtered or unexported fields
}
Cursor represents an iterator over B+Tree keys
type Node ¶
type Node struct {
ID uint64
IsLeaf bool
Keys [][]byte
Children []uint64 // For internal nodes
Values [][]byte // For leaf nodes
NextPage uint64 // For leaf nodes (linked list)
// contains filtered or unexported fields
}
Node represents a B+Tree node
func DeserializeNode ¶
DeserializeNode deserializes a node from a page
type Pager ¶
type Pager struct {
// contains filtered or unexported fields
}
Pager manages reading and writing pages to a file
func (*Pager) AllocatePage ¶
AllocatePage creates a new page at the end of the file
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree represents a B+Tree
func (*Tree) Delete ¶
Delete marks a key as deleted by writing a zero-length value as a tombstone. Get and Cursor.Next treat zero-length values as absent, so reads behave as expected.
Tombstone semantics are the intended contract — they trade space for simplicity, deferring the leaf-underflow-rebalance complexity of a real B+Tree delete. A re-Put of a tombstoned key overwrites in place, so the delete-and-rewrite pattern reclaims space; pure deletes do not. A periodic compaction pass would reclaim leaked tombstone slots — see the TODO at the top of pager.go.
Callers that need real-removal semantics (e.g. for storage-tier compaction) should layer that on top, not expect Delete to do it.
Source Files