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


2.2.2.4 Static BST Internal And Sparse Array Organized Leaf Nodes Sequence

The B-tree external nodes are organized as sparse arrays, with every other slot always used. The sparse organization should provide for better editing performance over regular (contiguous) organization, as it lowers the amortized amount of data that gets shifted for edit operations. It does require maintaining a bitmap describing the slots usage. For performance reasons, the bitmap is fitted inside a machine word. The bitmap maximal size translates into an external node maximal size - the number of node slots is the number of bits in a machine word.

For small data item sizes (about one machine word or less) the sparse node organization is less time efficient than the regular (plain) organization, as the latter allows for external nodes with more slots. For greater item sizes the sparse organization outperforms the contiguous organization, and so it does for same number of slots.

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_qlrate_type {
    unsigned rate, size;
    void *trans;
} x1f4_qlrate_type;

See Fixed Size Data Sequence Types.

The extra feature in the struct x1f4_qlrate_type is the rate unsigned field, specifying log 2 the maximal population count to be stored in internal B-tree nodes. Field usage is restricted to express request and a sensible default value is provided for it.

Construction definitions:

X1f4_QLRATE_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_qlrate_type * argument is to be observed.

General library:

See Fixed Size Data Sequence Library.


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