How does a bitmap index work?

Question

Is there anyone can help me to get the logical represntation of a bitmap index and reverse key index?

Answer 1

A reverse key index (in Oracle) is just a regular (B-tree) index with the keys reversed (1234 becomes 4321). This may prevent unbalanced indexes if you add incrementing keys. It also makes range scans impossible, so you should know what you are doing when using this.

A bitmap index is completely different from a B-tree index. You can think of it as a long bit array for every key value, with one entry for every row, set to true if the row has this value, false if not. This works better (than B-tree indexes) for columns with only a few distinct values (just MALE, FEMALE for example). You can compress these bit arrays, and then they become very compact and fast to scan.

The main problem with bitmap indexes is that it is a lot of work to update them, so that they are more suited for warehousing scenarios, where the data gets loaded in a nightly batch and then only queried (and not changed) during the day.

Wikipedia has a good page about bitmap indexes, too.