Appendix B The Bitmapped B-tree

The bitmapped B-tree minimizes data back and forth moving during B-tree editing by not enforcing its contiguity withing B-tree nodes and by maintaining a bitmap for each node describing the data layout instead. Furthermore, to improve node lookup every other slot is used. Such, fast binary search is allowed for node operations (fast here implies that the offsets for the search may be precomputed). Also, the one on one off pattern in data layout renders bitmap examination required only for the last binary search iteration.

Since the regular bitmapped B-tree node data layout may not imposed on the root node – for that would require the root node to be at least half full at all times – the root node itself conforms the more regular B-tree contiguous data layout.