私が理解している限り、ビットマップ インデックス検索は、以下のように 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
私は何かを誤解しましたか？ビットマップ インデックス検索の結果は、配列としてではなく、非ゼロ要素の一定時間検索を可能にする他のデータ構造として表示されますか?