[prev] 44 [next]

Bitmap Indexes (cont)

Storage costs for bitmap indexes:
  • one bitmap for each value/range for each indexed attribute
  • each bitmap has length ceil(r/8) bytes
  • e.g. with 50K records and 8KB pages, bitmap fits in one page
Query execution costs for bitmap indexes:
  • read one bitmap for each indexed attribute in query
  • perform bitwise AND on bitmaps (in memory)
  • read pages containing matching tuples
Note: bitmaps could index pages (shorter bitmaps, more comparisons)