B.2 Bitmapped B-tree Non Root Node Layout

For fast access the nodes have a power of two number of slots. The first slot is used to store the bitmap. Consequently, a node slot needs to be large enought to store as many bits as slots per node. Every other slot is always used, starting with the first – the first for the bitmap, every other for data items.

The number of node slots in the bps trees is the size of pointer expressed in bits. The bit corresponding the bitmap slot is set.

A half full node (least full, since nodes are never less than half full) is organized as:

        B * X * X * X * X * X * X * X * X * X * X * X * X * X * X * X *

The first slot is the leftmost. It corresponds the first bitmap bit, the 0 shift and 1 mask bit. The bitmap slot is the B, the used slots the Xs and the empty slots the *s.