Structure of Bitmap Indexes

A bitmap index has exactly the same structure as a B-tree index except for the format of the leaf nodes that have duplicate keys. The traditional B-tree leaf page stores the key value and a list of duplicates (see Figure 18). A bitmap index instead stores a bitmap in which each bit represents one row in the tblspace.

Without any compression, a bitmap stored in this fashion could have a maximum of 2³² (or approximately 4 gigabytes) possible values, which is too large to be of any practical use in an efficient indexing scheme. To reduce the size of this value, the database server compresses the bitmap.