Next: , Previous: , Up: Overview   [Contents][Index]


1.2 The B-trees

The idea of organizing b-tree nodes as critical bit trees is certainly not new. And there is appeal to it, as it transforms the b-trees to naturally suited data structures for variable length data (critical bit trees are such structures, classical b-trees are more abused than used in this role).

Critical bit trees are radix based structures, and this nature they project on the nonblonde b-trees require client applications to provide for themselves when it gets to associating lists of items with single keys. Fortunately, it is not difficult to do that, and in fact the applications have better knowledge on how to organize their own data in lists than a generic library can possibly have.

The nodes of nonblonde b-trees are variable in total size, though they do have a fixed size navigational part. The number of items a node can store depends solely on the latter size, as the size of an item navigational part is fixed itself (and in the 16 to 32 bytes range, depending on the library version and the machine word sizes).

Keys and data are stored in the b-tree nodes, except for when they are exceedingly large for the node storage class (the threshold may be something like 512 bytes).

The nonblonde b-trees are of the b+ variant and they store no client data in internal nodes.

The client application would select internal and external (navigational part) node sizes bases on their expectation of key and data sizes (an external block with a navigational size of 1k would store 32 to 64 items, and if the key/data sizes are maximal (close to the node class storage threshold, say 512 bytes), the entire block may get to 32kB to 64kB in size).

Node sizes (i.e. node navigational part sizes) are specified in powers of two for this library version (non two powers are rounded to a nearby one).


Next: Tables, Previous: Databases, Up: Overview   [Contents][Index]