Bitmap index vs b-tree time complexity

Question

Are queries on bitmap indexed fields with low distinct values faster in comparison with b-tree indices?

The common idea that bitmap indices give better query performance on fields with low distinct values in comparison with b-tree indices. But is it true?

For example, SELECT * FROM some_table WHERE color = 'RED'. Here the color field has low distinct values and can be indexed with either b-tree or bitmap index:

• if color uses b-tree index, then for performing the query above, a database should do a binary search + in-order traversal (from the binary search result in both directions) which gives us O(log N + K) ~ O(log N) time complexity, where K - is the number of result rows. K <= N.
• if color uses bitmap index, then a database does a full scan which gives O(N) time complexity.

So, from my perspective, the bitmap index is even worse. Am I right?

Answer 1

In general your calculation is right. However, if fields have very few unique values, K is getting larger and close to N. Therefore O(log N + K) ~ O(N) holds.

Consider a query SELECT * FROM employees WHERE gender='M' and marriage='YES'. If M/F and YES/NO are equally distributed, this query leads to K=N/4 which is O(N).

Additionally, although bitmap doesn't improve complexity a lot (both give the complexity of O(N) in this case), bitwise operation is way more faster than normal operation.