logo.gif (6996 bytes)
BTreeContainer

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];
}; 

All rights reserved.
For comments, problems or questions regarding this page contact John Hendrikx.
Last updated: 17 oktober 1998.