La mejor explicación proviene de Tom Lane, que es el autor del algoritmo a menos que me equivoque. Ver también el artículo de wikipedia.
En resumen, es un poco como un escaneo secuencial. La diferencia es que, en lugar de visitar todas las páginas del disco, un índice de mapa de bits escanea los índices aplicables AND y OR juntos, y solo visita las páginas del disco que necesita.
Esto es diferente de un escaneo de índice, donde el índice se visita fila por fila en orden, lo que significa que una página de disco puede ser visitada varias veces.
Re:la pregunta en tu comentario... Sí, eso es exactamente.
Un escaneo de índice recorrerá las filas una por una, abriendo las páginas del disco una y otra vez, tantas veces como sea necesario (algunas, por supuesto, permanecerán en la memoria, pero entiende el punto).
Un escaneo de índice de mapa de bits abrirá secuencialmente una lista corta de páginas de disco y capturará todas las filas correspondientes en cada una (de ahí el llamado estado de verificación que se ve en los planes de consulta).
Tenga en cuenta, aparte, cómo el agrupamiento/el orden de las filas afecta los costos asociados con cualquiera de los métodos. Si las filas están por todas partes en un orden aleatorio, un índice de mapa de bits será más económico. (Y, de hecho, si son realmente todos sobre el lugar, un escaneo de secuencia será más barato, ya que un escaneo de índice de mapa de bits no está exento de gastos generales).
