据我了解，位图索引搜索将返回一个由 0 和 1 组成的数组，如下所示：
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
数组中的每个索引都映射到数据库中某个其他数组中的某个记录，因此要获得结果，您需要找到结果数组中非零元素的索引。
我不明白的是你如何在恒定时间内找到这些指数？我能想到的最好的算法是遍历数组中的每个元素，检查它是否非零，如果它非零，则将该元素的索引写入其他地方。但是，这意味着按顺序查看数组中的每个元素，这是线性时间。所以返回结果所花费的时间将与结果数组的大小成正比，与表中的总行数相同。
但是，我读过的位图索引论文似乎表明查询时间仅与命中数成正比，而不与表中的总行数成正比。参考：
http://crd-legacy.lbl.gov/~kewu/ps/LBNL-59952.pdf
我是不是误会了什么？位图索引搜索的结果不是以数组的形式呈现，而是以其他一些数据结构呈现，可以对非零元素进行恒定时间搜索？