Thus, one quadrant is always empty. First, the computers A through L will correspond to positions 1 through 12 of the bit vectors, respectively. Exercise 5.4.6 Suppose that pointers require p bits, and keys require k bits. The contribution of k is a little tricky. Thus, for a reasonable sized file, the space required by the bitmap and B-tree are comparable under our assumptions above.
Keys require many bits, but the number of different key values is small.
There are a number of advantages to the B-tree, even when it takes more space, including the ability to handle range queries efficiently and the speed with which access to single records is provided.