Previous: , Up: Fixed Size Data Sequences   [Index]

2.2.2 B-tree Compressed BST Based Fixed Size Data Sequences

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 leaves 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: