Node
Node
Class Node.
class NodeRepresents a node in a B-tree data structure, supporting internal and leaf nodes, file-backed storage, and caching for efficient access. Provides methods for reading, writing, splitting, and managing child nodes and records.
Each node occupies one page of the file. A page is laid out as:
- Node type (1 byte)
- Number of bytes of entries that follow (2 bytes, little endian)
- The entries, each one
[varint key length][key bytes][4 byte pointer], in key order - Zero padding up to the page size
Keys are compared as binary strings (strcmp()) and are stored exactly as given. In an internal node the key of each child is an upper bound for every key in that child's subtree.
Constants
NODE_PTR_SIZE
public const NODE_PTR_SIZE = 4NODE_HEADER_SIZE
public const NODE_HEADER_SIZE = 3Properties
ptr
Pointer to the node's position in the file.
public int $ptrType: int
pageSize
Size of the page the node is stored in, in bytes.
public int $pageSizeType: int
cacheSize
Maximum number of records to cache for this node.
public int $cacheSize = 128Type: int
children
The node's entries, keyed by key, in key order. Leaf entries point to records and internal entries point
public array $childrenType: array
to child nodes.
Integer-like keys are converted to integers by PHP, so they are always cast back with (string).
nodeType
Type of the node (internal or leaf).
public NodeType $nodeTypeType: Hazaar\Util\BTree\NodeType
file
public mixed $fileType: mixed
nodeCache
Cache for nodes to avoid excessive file reads.
private array $nodeCacheType: array
recordCache
Cache for records to avoid multiple reads from the file.
private array $recordCacheType: array
This is a static property to allow sharing across instances.
parentNode
public self $parentNodeType: self
Methods
__construct
public __construct(mixed $file, ?int $ptr, int $pageSize = 4096): voidParameters
| Parameter | Type | Description |
|---|---|---|
$file | mixed | |
$ptr | int | |
$pageSize | int |
resetCache
Resets the static caches for nodes and records.
public resetCache(): voidReturns: void
This method clears both the node cache and the record cache by setting their respective static arrays to empty. Use this to ensure that cached data is discarded and fresh data will be loaded on subsequent accesses.
resetCaches
Drops the cached nodes and records for a file, so they're read again from disk.
public resetCaches(mixed $file): voidReturns: void
Parameters
| Parameter | Type | Description |
|---|---|---|
$file | mixed |
create
Create a new, empty Node instance.
public create(mixed $file, NodeType $type = 'NodeType::INTERNAL', int $pageSize = 4096): NodeReturns: Hazaar\Util\BTree\Node
Parameters
| Parameter | Type | Description |
|---|---|---|
$file | mixed | The file resource where the BTree is stored |
$type | Hazaar\Util\BTree\NodeType | |
$pageSize | int |
maxKeyLength
Returns the longest key that can be stored in a page of the given size.
public maxKeyLength(int $pageSize): intReturns: int
A key may use at most a quarter of the page, so that at least four entries always fit in a node and a node that overflows by one entry can always be split into two that fit.
Parameters
| Parameter | Type | Description |
|---|---|---|
$pageSize | int |
entrySize
Returns the number of bytes an entry for the key uses in a page.
public entrySize(string $key): intReturns: int
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string |
separator
Returns the shortest key that sorts after (or equal to) $left and before $right.
public separator(string $left, string $right): stringReturns: string
This is used as the separator between two nodes, as it only has to route lookups and a shorter key leaves more room in the parent node. $left must sort before $right.
Parameters
| Parameter | Type | Description |
|---|---|---|
$left | string | |
$right | string |
byteSize
Returns the number of bytes the node uses in its page, including the header.
public byteSize(): intReturns: int
read
Reads the node data from the file at the specified pointer.
public read(?int $ptr): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$ptr | int | The pointer to the node in the file. If null, uses the current node's pointer. |
write
Writes the node data to the file at the specified pointer.
public write(?int $ptr, ?string $data): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$ptr | int | The pointer to write the node in the file. If null, writes to the end of the file. |
$data | string | the encoded entries, if they have already been encoded by Hazaar\Util\BTree\Node::encode |
add
Adds the first key-value pair to an empty B-tree.
public add(string $key, mixed $value): boolReturns: bool
This method creates a new leaf node, sets the provided key and value, and adds the node as a child to the current node. Only internal nodes can have children; attempting to add a record to a non-leaf node will throw a RuntimeException.
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to add to the node |
$value | mixed | the value associated with the key |
set
Sets the value for the specified key in the node.
public set(string $key, mixed $value, bool $append): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to set |
$value | mixed | the value to associate with the key |
$append | bool | true if the key is being added after every other key in the tree, so that a full node is split at the end instead of the middle |
get
Gets the value for the specified key from the node.
public get(string $key): mixedReturns: mixed
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to get |
has
Checks if the specified key exists in the node.
public has(string $key): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to check |
remove
Removes the specified key from the node.
public remove(string $key): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to remove |
addNode
Adds a child node to the current node.
public addNode(self $node, string $key, bool $append): voidReturns: void
Parameters
| Parameter | Type | Description |
|---|---|---|
$node | self | the node to add as a child |
$key | string | the key to add the node under, which must sort after (or equal to) every key in the node |
$append | bool | true if the node is being added at the end of the tree, so that a full node is split at the end instead of the middle |
addRecord
Adds a record to the current node.
public addRecord(Record $record): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$record | Hazaar\Util\BTree\Record | the record to add |
verifyTree
Verifies the integrity of the B-Tree from this node downwards.
public verifyTree(?Node $node, ?string $minKey, ?string $maxKey): boolReturns: bool
Checks that the keys in every node are in order, that every key falls within the range its parent gives it, and that every node fits in its page.
Parameters
| Parameter | Type | Description |
|---|---|---|
$node | Hazaar\Util\BTree\Node | The node to verify. If null, starts from the current node. |
$minKey | string | every key in the node must sort after this key |
$maxKey | string | every key in the node must sort before or equal to this key |
countRecords
Counts the total number of child nodes in the subtree rooted at this node.
public countRecords(): intReturns: int
If the node is a leaf, returns the number of its children directly. Otherwise, recursively counts the children of all descendant nodes.
lookupLeafNode
Looks up the leaf node that would contain the specified key.
public lookupLeafNode(string $key): ?NodeReturns: Hazaar\Util\BTree\Node
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key to look up |
lookupInsertLeafNode
Finds the leaf node that a key should be inserted into.
public lookupInsertLeafNode(string $key, ?bool $append): ?NodeReturns: Hazaar\Util\BTree\Node
A key that sorts after every key in the tree goes into the last leaf, and the keys of the nodes on the way down are raised to it, so they stay an upper bound for their subtree.
Parameters
| Parameter | Type | Description |
|---|---|---|
$key | string | the key that will be inserted |
$append | bool | set to true if the key sorts after every key in the tree |
leaf
Returns a generator that yields all leaf nodes in the subtree rooted at this node.
public leaf(): \GeneratorReturns: Generator
This method traverses the B-tree and yields each leaf node it encounters. It can be used to iterate over all leaf nodes in the B-tree.
encode
Encodes the node's entries as they are stored in its page, after the header.
private encode(): stringReturns: string
save
Writes the node, or splits it if it no longer fits in its page.
private save(bool $append): boolReturns: bool
Parameters
| Parameter | Type | Description |
|---|---|---|
$append | bool | passed on to Hazaar\Util\BTree\Node::split |
child
Returns the child node at the pointer, from the cache if it has been read already.
private child(int $ptr): selfReturns: self
Parameters
| Parameter | Type | Description |
|---|---|---|
$ptr | int |
splitIndex
Picks where to split the node's entries, by bytes.
private splitIndex(bool $append): intReturns: int
Parameters
| Parameter | Type | Description |
|---|---|---|
$append | bool | if true, everything but the last entry stays together, so that keys added in order leave full nodes behind |
split
Splits the current node into two nodes when it no longer fits in its page.
private split(bool $append): voidReturns: void
The entries are divided by bytes, the first part is moved into a new node, and the new node is added to the parent. The root node stays where it is, so instead both halves are moved into new nodes and the root becomes their parent.
Parameters
| Parameter | Type | Description |
|---|---|---|
$append | bool | true if the node overflowed because a key was added after every other key in the tree |
spawn
Creates and writes a new node of the same type holding the given entries.
private spawn(array $children): selfReturns: self
Parameters
| Parameter | Type | Description |
|---|---|---|
$children | array |
cacheNode
Caches the specified node.
private cacheNode(self $node): voidReturns: void
Parameters
| Parameter | Type | Description |
|---|---|---|
$node | self | the node to cache |
Generated by Hazaar API Doc Generator on Sun, 08 Nov 2026 03:36:15 +0000