1.1.2 Bitmapped B-tree Fixed Size Data Arrays

There are available sorted, fixed size data associative arrays constructed over bitmapped B-trees. The arrays may be constructed over such B-tree flavors as plain B-tree and B+ tree.

The arrays record data in B-trees, with tree nodes storing up to few tens of data items. Provided that the data size is small enough this allows for better cache access over such associative arrays that store one data item per node. Balancing the tree requires moving data around - intra node or between nodes. Hence recording the data address in a trivial manner is not possible as it is for the one data item per node data structures (tracking the data address is nonetheless possible for the data is moved via an application supplied method).

The bitmapped B-tree array methods (such as insertion and deletion) require the application to provide for data specific methods. Such data methods would implement operations as trivial as data comparison or moving. For performance considerations the application is also required to provide for some non trivial methods placing data within a B-tree node.

See The Bitmapped B-tree.

Such methods need to observe the B-tree node organization (and while non trivial they need not be exceedingly engineered).

The B+ tree based array uses slightly more memory than the B-tree based one, about 1 / (size of pointer expressed in bits). It only implements the pointer set library.