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_ysrate_type { unsigned quarter, rate, size; void *trans; } x1f4_ysrate_type;
See Fixed Size Data Sequence Types.
The extra features in the struct x1f4_ysrate_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_YSRATE_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_ysrate_type *
argument is to
be observed.
X1f4_YSRATE_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_ysrate_type *
argument is to be
observed.
General library:
See Fixed Size Data Sequence Library.
See Fixed Size Data Sequence Ordered Library.
call
data structure size retriever:
int x1f4_call_ysrate(unsigned *);
case
data structure state retriever:
int x1f4_case_ysrate(void *);
fast
sequence constructor routine:
int x1f4_fast_ysrate(void *, unsigned, struct x1f4_ysrate_type *);
find
plain search routine:
int x1f4_find_ysrate(void *, void *, int (*)(void *, void *), void **);
fini
sequence regular destructor routine:
int x1f4_fini_ysrate(void **);
flat
sequence destructor routine:
int x1f4_flat_ysrate(void *);
flow
data structure integrity check routine:
int x1f4_flow_ysrate(void *);
high
data purge routine:
int x1f4_high_ysrate(void *);
init
sequence regular constructor routine:
int x1f4_init_ysrate(void **, unsigned, struct x1f4_ysrate_type *);
land
sort insertion routine:
int x1f4_land_ysrate(void *, void *, int (*)(void *, void *), void **);
lime
data traversal routine:
int x1f4_lime_ysrate(void *, void *, int (*)(void *, void *));
peek
plain data retrieval routine:
int x1f4_peek_ysrate(void *, unsigned, void **);
push
plain data insertion routine:
int x1f4_push_ysrate(void *, unsigned, void **);
seek
data search routine:
int x1f4_seek_ysrate (void *, void *, int (*)(void *, void *), unsigned *, void **);
size
size retriever:
int x1f4_size_ysrate(void *, unsigned *);