Bitmap Indexes are described here, but I don't understand some part of it.
A plain indexscan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory "bitmap" data structure, and then visits the table tuples in physical tuple-location order. The bitmap scan improves locality of reference to the table at the cost of more bookkeeping overhead to manage the "bitmap" data structure --- and at the cost that the data is no longer retrieved in index order, which doesn't matter for your query but would matter if you said ORDER BY.
To visit the table tuples, you need to know the tuple-pointers. Then there must be a mapping between each bit in a bitmap and tuple-pointers. How is this mapping maintained?
I also don't understand what he meant by "sorts them using an in-memory "bitmap" data structure".