B-Tree vs Bitmap database indexes

Question

Can someone explain the different between the bitmap and b tree indexes. in what situations will you use both of these? What are the advantages/disadvantages of each.

Answer 1

From wikipedia: B-Trees and bitmap indexes. The use cases:

• B-Trees are the typical index type used when you do CREATE INDEX ... in a database:

  1. They are very fast when you are selecting just a small very subset of the index data (5%-10% max typically)
• They work better when you have a lot of distinct indexed values.
• Combining several B-Tree indexes can be done, but simpler approaches are often more efficient.
• They are not useful when there are few distinct values for the indexed data, or when you want to get a large (>10% typically) subset of the data.
• Each B-Tree index impose a small penalty when inserting/updating values on the indexed table. This can be a problem if you have a lot of indexes in a very busy table.


This characteristics make B-Tree indexes very useful for speeding searches in OLTP applications, when you are working with very small data sets at a time, most queries filter by ID, and you want good concurrent performance.

• Bitmap indexes are a more specialized index variant:

  1. They encode indexed values as bitmaps and so are very space efficient.
  2. They tend to work better when there are few distinct indexed values
  3. DB optimizers can combine several bitmap indexed very easily, this allows for efficient execution of complex filters in queries.
  4. They are very inefficient when inserting/updating values.

  
  Bitmap indexes are mostly used in data warehouse applications, where the database is read only except for the ETL processes, and you usually need to execute complex queries against a star schema, where bitmap indexes can speed up filtering based on conditions in your dimension tables, which do not usually have too many distinct values.

As a very short summary: use B-Tree indexes (the "default" index in most databases) unless you are a data warehouse developer and know you will benefit for a bitmap index.