As far as I understand it, a bitmap index search will return an array of 0s and 1s, like below:
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
Each index in the array is mapped to some record in the database in some other array, so to get results you need to find the indices of the nonzero elements in the results array.
What I don't understand is how do you find these indices in constant time? The best algorithm I can think of is to go through each element in the array, check if it's nonzero, and if it's nonzero then write the index of that element somewhere else. However, this would mean looking at every element in the array sequentially, which is linear time. So the time taken to return the results will be proportional to the size of the results array, which is the same as the total number of rows in the table.
However, the bitmap index papers I've read seem to suggest that the query time is only proportional to the number of hits and not to the total number of rows in the table. Reference:
http://crd-legacy.lbl.gov/~kewu/ps/LBNL-59952.pdf
Did I misunderstand something? Is the result of the bitmap index search not presented as an array but some other data structure that enables constant time search for nonzero elements?
The key is to properly store the index: say, using the Run-Length-Encoded compression you mentioned in another question. Each suitable lookup will take O(hits) time then.