Тут скорее зависит от индексов и запросов.
Пусть из нескольких миллионов нужно выбрать сотню записей - при правильных индексах данные индекса будут лежать в одном-двух блоках, чтение индекса не займет много времени.

Теперь данные: в один 8кб блок будет входить только 4 записи, так что чтение каждой записи - это скорее всего обращение к своему отдельному блоку, чтобы добраться до блока данных, нужно прочитать порядка 5ти блоков включая заголовочные.
С учетом кэширования, я думаю, можно считать, что для чтение записи нужно прочитать два блока данных - сам блок данных и вышестоящий блок указателей, остальное будет кэшироваться.
Примем время физического чтения блока за 3 мс, итого на чтение 100 записей в ОЧЕНЬ большой таблице уйдет
0.003*100*2=0.6 сек, причем будет очень слабо зависеть от размера таблицы (как только выйдет за тот размер, который можно закэшировать)

Если это много, то нужно подумать, как хранить данные ближе друг к другу, например в полях данных индекса.

Я так понимаю, битмап индексы ускоряют только работу с самим индексом, а если придется лезть в данные - то тут на порядок дольше придеться ползти до блоков с данными.