|
BNode
Up
BTreeContainer
Extents
| |
The BTreeContainer holds information about the structure of a B-Tree. It tells
you how many nodes are located in the structure, how large each node is and whether or not
they are leaf nodes. Leaf nodes contain the actual information. Non-leaf nodes
are used to navigate further down the tree when you're looking for specific information.
By looking at the key field in non-leaf nodes and comparing it with the value you're
looking for, you can locate a specific leaf node. Once you found the non-leaf BNode
which contains the range of key values which encompasses the key value you're looking for,
you can use it to find the BNodeContainer containing more detailed information on that
part of the tree. Keep going down the tree, each time picking the BNode containing
your key value, until you reach a BNodeContainer containing leaf nodes. Now check if
your key value is among those leaf nodes and if it is you will have found the information
you were looking for.
| Field |
Type |
Description |
| nodecount |
UWORD |
The number of BNode structures stored in the bnode array. |
| isleaf |
UBYTE |
TRUE if the BNodes in the bnode array are leaves, otherwise FALSE. |
| nodesize |
UBYTE |
The size in bytes of a single BNode structure in the BNode array.
Leaf BNodes and normal BNodes can be different sizes. Use this field to determine
how many bytes each entry in the bnode array occupies. The size of a BNode is always
a multiple of 2. |
| bnode |
struct BNode |
An array of BNodes. The size of each entry is determined by the
nodesize field. The number of BNodes in this array is stored in the nodecount field. |
struct BTreeContainer {
UWORD nodecount;
UBYTE isleaf;
UBYTE nodesize;
struct BNode bnode[0];
};
|
