A bitmap index is a special type of structure used by most high-end database management systems to optimize search and retrieval for low-variability data. Although a B-tree or B+tree is the standard index structure used for highly variable data, such as identity values, names, and street addresses, this type of index structure doesn't work especially well with data that has low variability, such as gender (M, F) or nullable (Y, N). This type of situation calls for a bitmap index, which Table A shows.
A logical perspective of the bitmap index is to think of it as a grid, wherein the grid columns represent each discrete data value and the grid rows represent the position of each row in the table. Each cell will contain either a 1 or a 0, true or false. In the sample grid, RowIDs 1 and 4 are female, 2 and 3 are male.
Using bitwise operations on bitmaps built from low-variability columns, SQL Server can quickly isolate sets of rows that meet some criteria, such as all male employees or all nullable columns.