Next: , Previous: , Up: B-tree Compressed BST Based Fixed Size Data Sequences   [Index]


2.2.2.3 Static BST Internal And Array Organized Leaf Nodes Sequence

The B-tree external nodes are organized as plain arrays.

The B-tree internal nodes are organized as self balancing, array based BSTs. The editing of the array based BSTs has linear complexity, whereas the editing of the dynamic AVL BSTs has logarithmic complexity. Nonetheless, for their regular memory layout the array based BSTs may outperform the AVL BSTs for small enough sizes. The retrieval complexity is for the arrays based BSTs (as is for the AVL BSTs) logarithmic.

Types:

typedef struct x1f4_qsrate_type {
    unsigned quarter, rate, size;
    void *trans;
} x1f4_qsrate_type;

See Fixed Size Data Sequence Types.

The extra features in the struct x1f4_qsrate_type are the quarter and rate unsigned fields, specifying quarter the maximal population count to be stored in external B-tree nodes and log 2 the maximal population count to be stored in internal B-tree nodes, respectively. Both fields usage is restricted to express request and sensible default values are provided for them.

Construction definitions:

X1f4_QSRATE_FOUR_FRAME

indicates the sequence constructor routines that the quarter the maximal population count to be stored in external B-tree nodes specified by the quarter field of their struct x1f4_qsrate_type * argument is to be observed.

X1f4_QSRATE_RATE_FRAME

indicates the sequence constructor routines that the log 2 the maximal population count to be stored in internal B-tree nodes specified by the rate field of their struct x1f4_qsrate_type * argument is to be observed.

General library:

See Fixed Size Data Sequence Library.


Next: , Previous: , Up: B-tree Compressed BST Based Fixed Size Data Sequences   [Index]