Note that each BTreeHeader has at least one root page, even if it contains no data. In this schema, we show the root page just after the BTree it is associated to, but after a few updates, the root page may perfectly well be stored elswhere on the disk.

The Nodes and Leaves

Nodes and Leaves are logical BTree pages which are serialized on disk into one to many PageIOs. They have slightly different data structures, as Nodes contains pointers to Leaves, and no data, while Leaves contains data. In any case, both contain the keys.

On disk, each Node and Leaf are stored in PageIOs, as we said. A Node will have pointers to some other logical pages, and on disk, those pointers will be offset of the first PageIO used to store the logical page it points to.

Note that we store the size of the serialized data : this is necessary as we have to know how many PageIOs will be needed to store the logical page.

Potential improvement

We can get better performance by serializing the data differently. Instead of storing keys and values as byte arrays prefixed by their length, we could store an array of keys and values' offsets before the associated byte[]. Here is the resulting data structure, once serialized :

(The Node is not described, as it's basically the same data structure, but with one extra value).

It does not need more space to serialize the data this way, as the offsets are ints, and in the previous version, those ints are used to store the length of the keys and values anyway.

The gain is that we can have access to a given key and value without having to read all the previous keys and values. Also we can now read a leaf or a node without having to deserialize all the keys and values they contain.

Modified: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf.graphml ============================================================================== Binary files - no diff available. Modified: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf.png ============================================================================== Binary files - no diff available. Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf2.graphml ============================================================================== Binary file - no diff available. Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf2.graphml ------------------------------------------------------------------------------ svn:mime-type = application/xml Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf2.png ============================================================================== Binary file - no diff available. Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/nodeLeaf2.png ------------------------------------------------------------------------------ svn:mime-type = image/png