RelationalDBDesign RelationalDBDesign 

Index Techniques   «Prev  Next»
Lesson 2Bitmapped Indexes
ObjectiveDescribe B-tree and Bitmapped Indexes.

Describe B-tree and Bitmapped Indexes

For high cardinality data or data with many possible values, B-tree indexes are most effective.
B-tree indexes are most effective for high cardinality data, or data with many possible values. A common problem with traditional B-tree indexes occurs when an indexed column has low cardinality, which means it has too few distinct values to speed query access.
For example, an index of a REGION column that has only 4 values (North, South, East, West) does not have enough distinct values to speed access for queries. It is an index column with relatively few distinct values, compared to the number of rows in the table, and is referred to as a low cardinality column.
Oracle's answer to the problem of low cardinality is the bitmapped index.

Bitmapped indexes

We know that the purpose of an index is to provide pointers to the rows in a table that contain a given key value. In a bitmap index, a bitmap for each key value is used instead of a list of ROWIDs. Each bit in the bitmap corresponds to a possible ROWID. If the bit is set, the row with the matching ROWID includes the key value. A mapping function converts the bit position to an actual ROWID, so the bitmap index functions as a regular index although it has a different internal structure. If the number of different key values is small, bitmap indexes are very space-efficient.

  1. In a bitmapped index, a binary array is created with one index row for each table row
  2. Within each index row, there are entries for each index value (North, South, East, West)
  3. Across each index row, binary values are set to zero except for the index entry where the value is true. This value is set to 1.
  4. We can see that row 1 is in the East region

Oracle Bitmap