Static BST Internal And Sparse Array Organized Leaf Nodes Sequence (libx1f4l2)

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.

The call data structure size retriever:
```
int x1f4_call_qlrate(unsigned *);
```
The case data structure state retriever:
```
int x1f4_case_qlrate(void *);
```
The ever record retriever:
```
int x1f4_ever_qlrate(void *, void **);
```

The fast sequence constructor routine:

int x1f4_fast_qlrate(void *, unsigned, struct x1f4_qlrate_type *);

The fini sequence regular destructor routine:
```
int x1f4_fini_qlrate(void **);
```
The flat sequence destructor routine:
```
int x1f4_flat_qlrate(void *);
```
The high data purge routine:
```
int x1f4_high_qlrate(void *);
```

The init sequence regular constructor routine:

int x1f4_init_qlrate(void **, unsigned, struct x1f4_qlrate_type *);

The lead record retriever:
```
int x1f4_lead_qlrate(void *, void **);
```

The lime data traversal routine:

int x1f4_lime_qlrate(void *, void *, int (*)(void *, void *));

The miss plain data deletion routine:

int x1f4_miss_qlrate(void *, unsigned);

The peek plain data retrieval routine:

int x1f4_peek_qlrate(void *, unsigned, void **);

The push plain data insertion routine:

int x1f4_push_qlrate(void *, unsigned, void **);

The size size retriever:

int x1f4_size_qlrate(void *, unsigned *);

The swap data swap routine:
```
int x1f4_swap_qlrate(void *, void *);
```