Documentation
¶
Index ¶
- Constants
- Variables
- type Builder
- func (b *Builder) AddInternalChild(key []byte, childPageID uint64) error
- func (b *Builder) AddLeafEntry(key, value []byte, flags byte, valPtr page.ValuePtr) error
- func (b *Builder) AddLeafEntryWithPrefix(key, value []byte, flags byte, valPtr page.ValuePtr, ...) error
- func (b *Builder) Count() uint16
- func (b *Builder) Data() []byte
- func (b *Builder) Finish() *Node
- func (b *Builder) FreeSpace() int
- func (b *Builder) LeafEntrySize(key, value []byte, flags byte) int
- func (b *Builder) LeafEntrySizeWithPrefix(key, value []byte, flags byte) (entrySize, prefixLen, suffixLen int)
- func (b *Builder) LeafPrevKey() []byte
- func (b *Builder) PageID() uint64
- func (b *Builder) SetPageID(id uint64)
- type BuilderOptions
- type InternalEntry
- type LeafEntry
- type Node
- func (n *Node) AddInternalChild(key []byte, childPageID uint64) error
- func (n *Node) AddLeafEntry(key, value []byte, flags byte, valPtr page.ValuePtr) error
- func (n *Node) Checksum() uint32
- func (n *Node) Compact() error
- func (n *Node) Count() uint16
- func (n *Node) Data() []byte
- func (n *Node) FreeSpace() int
- func (n *Node) GetInternalChildID(index uint16) (uint64, error)
- func (n *Node) GetInternalEntry(index uint16) (InternalEntry, error)
- func (n *Node) GetInternalEntryView(index uint16) (key []byte, childID uint64, err error)
- func (n *Node) GetLeafEntry(index uint16) (LeafEntry, error)
- func (n *Node) GetLeafEntryView(index uint16) (key []byte, val []byte, valPtr page.ValuePtr, flags byte, err error)
- func (n *Node) PageID() uint64
- func (n *Node) SearchInternal(key []byte) (uint16, bool)
- func (n *Node) SearchLeaf(key []byte) (uint16, bool, error)
- func (n *Node) SetCount(c uint16)
- func (n *Node) SetPageID(id uint64)
- func (n *Node) SetType(t page.PageType)
- func (n *Node) Split(newNode *Node) ([]byte, error)
- func (n *Node) Type() page.PageType
- func (n *Node) UpdateChecksum()
- func (n *Node) UpdateLeafValuePtr(index uint16, oldPtr, newPtr page.ValuePtr) (bool, error)
- func (n *Node) VerifyChecksum() bool
Constants ¶
const ( FlagInline = 0x00 FlagPointer = 0x01 FlagTombstone = 0x02 )
const ( // NodeHeaderSize is the size of the page header (16 bytes). NodeHeaderSize = page.PageHeaderSize // DirectoryEntrySize is the size of an offset (uint16). DirectoryEntrySize = 2 )
Variables ¶
var ( ErrKeyTooLarge = errors.New("key too large") ErrValueTooLarge = errors.New("value too large") ErrNodeFull = errors.New("node is full") ErrInvalidType = errors.New("invalid node type") ErrKeyNotFound = errors.New("key not found") ErrCorruptedNode = errors.New("corrupted node: invalid offsets") )
Common errors
Functions ¶
This section is empty.
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder facilitates O(N) sequential construction of a node. It avoids the O(log N) search and O(N) shift of standard insertion.
func NewBuilder ¶
NewBuilder initializes a builder for the given buffer.
func NewBuilderWithOptions ¶
func NewBuilderWithOptions(data []byte, pType page.PageType, opts BuilderOptions) *Builder
func (*Builder) AddInternalChild ¶
AddInternalChild appends a child pointer. Assumes keys are added in sorted order.
func (*Builder) AddLeafEntry ¶
AddLeafEntry appends a leaf entry. Assumes keys are added in sorted order.
func (*Builder) AddLeafEntryWithPrefix ¶
func (b *Builder) AddLeafEntryWithPrefix(key, value []byte, flags byte, valPtr page.ValuePtr, entrySize, prefixLen, suffixLen int) error
AddLeafEntryWithPrefix appends a leaf entry using precomputed size/prefix data. The caller must ensure prefixLen/suffixLen are computed for this builder state.
func (*Builder) Finish ¶
Finish finalizes the page header and checksum. Returns a Node wrapper for convenience.
func (*Builder) LeafEntrySize ¶
LeafEntrySize returns the encoded size for a leaf entry if it were appended next, based on the builder's current prefix-compression state.
func (*Builder) LeafEntrySizeWithPrefix ¶
func (b *Builder) LeafEntrySizeWithPrefix(key, value []byte, flags byte) (entrySize, prefixLen, suffixLen int)
LeafEntrySizeWithPrefix returns the encoded size and prefix/suffix lengths for a leaf entry if it were appended next.
func (*Builder) LeafPrevKey ¶
LeafPrevKey returns the last key appended to a leaf builder. It is only maintained when leaf prefix compression is enabled.
type BuilderOptions ¶
type BuilderOptions struct {
LeafPrefixCompression bool
}
type InternalEntry ¶
InternalEntry represents a parsed entry from an Internal Node.
type LeafEntry ¶
type LeafEntry struct {
Key []byte
Value []byte
ValuePtr page.ValuePtr // Valid if Flags & FlagPointer
Flags byte
}
LeafEntry represents a parsed entry from a Leaf Node.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node is a wrapper around a raw page byte slice. It implements the Slotted Page layout.
func NewNodeView ¶
NewNodeView wraps the given page data without allocating a *Node. It is useful in hot paths that store Node values directly (e.g. iterators).
func (*Node) AddInternalChild ¶
AddInternalChild adds a child pointer to the internal node.
func (*Node) AddLeafEntry ¶
AddLeafEntry inserts a new entry into the Leaf Node. It maintains the sorted order of keys. If the key already exists, it updates it (by rewriting the entry). NOTE: This implementation assumes simple append-to-heap and shift-directory. It DOES NOT handle fragmentation (holes in heap) yet. A full implementation would compact the heap if FreeSpace check fails but logical space exists.
func (*Node) Compact ¶
Compact rebuilds the node's slotted-page layout in-place, removing heap holes created by overwrites/splits. It preserves logical entry order (directory order) and updates offsets and checksum.
func (*Node) FreeSpace ¶
FreeSpace returns the number of bytes available for new items. Free space is the gap between the end of the Directory and the start of the Heap.
func (*Node) GetInternalChildID ¶
GetInternalChildID returns only the child page ID at the given index.
func (*Node) GetInternalEntry ¶
func (n *Node) GetInternalEntry(index uint16) (InternalEntry, error)
GetInternalEntry reads the entry at the given index.
func (*Node) GetInternalEntryView ¶
GetInternalEntryView returns a view of the entry at the given index. The key slice points directly to the node's data.
func (*Node) GetLeafEntry ¶
GetLeafEntry reads the entry at the given index.
func (*Node) GetLeafEntryView ¶
func (n *Node) GetLeafEntryView(index uint16) (key []byte, val []byte, valPtr page.ValuePtr, flags byte, err error)
GetLeafEntryView returns a view of the entry at the given index. Key and Value slices point directly to the node's data when the node is not prefix-compressed. For prefix-compressed nodes, Key is reconstructed into a scratch buffer owned by the node and is only valid until the next call.
func (*Node) SearchInternal ¶
SearchInternal performs a binary search for the given key in an Internal Node. Returns the index of the child that covers the range containing key. Logic: Find largest index i such that Entry[i].Key <= key. If key < Entry[0].Key, returns index 0 (Left-most child rule usually handles this).
func (*Node) SearchLeaf ¶
SearchLeaf performs a binary search for the given key in a Leaf Node. Returns the index of the first entry where Entry.Key >= key. If key is found, found=true. If key is greater than all entries, returns Count, false.
func (*Node) Split ¶
Split moves the upper half of the items from the receiver node (n) to the given new node (newNode). It returns the "pivot" key (the first key of the new node), which is used to insert into the parent.
func (*Node) UpdateChecksum ¶
func (n *Node) UpdateChecksum()
UpdateChecksum calculates and updates the checksum in the header.
func (*Node) UpdateLeafValuePtr ¶
UpdateLeafValuePtr updates the ValuePtr bytes for the entry at index if the entry is a pointer and currently matches oldPtr. It updates the page checksum on success.
This is intended for maintenance operations (e.g. slab compaction) that need to swap pointers without rewriting the B+Tree structure.
func (*Node) VerifyChecksum ¶
VerifyChecksum validates the node's checksum.
Source Files