Next: B-tree Compressed BST Based Fixed Size Data Sequences, Previous: Fixed Size Data Sequence Interface, Up: Fixed Size Data Sequences [Index]
There are available sequences constructed over binary search trees such as AVL and array based trees.
The binary search trees are compressed using a B-tree schema. The BST structure is locally collapsed into B-tree nodes. The data structure may also be viewed as a B-tree based one, with the B-tree nodes organized as self balancing binary search trees.
Data is stored exclusively in the B-tree leaf nodes.
The sequences allow for proper random access with O(logN) time.
Sequences with dynamic, AVL tree organized internal nodes:
Sequences with static, array based BST organized internal nodes: