La migliore spiegazione viene da Tom Lane, che è l'autore dell'algoritmo a meno che non mi sbagli. Vedi anche l'articolo di Wikipedia.
In breve, è un po' come una scansione sequenziale. La differenza è che, anziché visitare ogni pagina del disco, un indice bitmap esegue la scansione degli indici AND e OR applicabili insieme e visita solo le pagine del disco di cui ha bisogno.
È diverso da una scansione dell'indice, in cui l'indice viene visitato riga per riga in ordine, il che significa che una pagina del disco può essere visitata più volte.
Re:la domanda nel tuo commento... Sì, è proprio così.
Una scansione dell'indice passerà attraverso le righe una per una, aprendo le pagine del disco ancora e ancora, tutte le volte necessarie (alcune rimarranno ovviamente in memoria, ma hai capito).
Una scansione dell'indice bitmap aprirà in sequenza un breve elenco di pagine del disco e catturerà ogni riga applicabile in ciascuna di esse (da cui il cosiddetto recheck cond che vedi nei piani di query).
Nota, per inciso, in che modo il raggruppamento/l'ordine di riga influisce sui costi associati con entrambi i metodi. Se le righe sono dappertutto in ordine casuale, un indice bitmap sarà più economico. (E, infatti, se sono davvero tutti al contrario, una scansione seq sarà più economica, poiché una scansione dell'indice bitmap non è priva di sovraccarico.)
