空間インデックス
グリッドベースの空間インデックスは、まずオブジェクトを適切な位置に置き、そのオブジェクトの識別子と対応するグリッドセルの識別子を結びつけたインデックスを生成し、高速アクセスを可能にする。これは「空間駆動型」またはデータ独立型手法の例だが、逆の「データ駆動型」またはデータ依存型手法は Rigaux et al. (2002) で論じられている。グリッドベースの空間インデックスの利点は、インデックスの構造を先に作成でき、データはそのインデックス構造を変化させることなく後から随時追加できる点である。実際、様々な種類のデータに共通のグリッドを使ってインデックスを付けていた場合、それらインデックスは様々なソースから集めてマージ可能である。一方、データ駆動型構造のR木などは、データ量と検索速度は効率的だが既存のデータとインデックス構造が密接に結びついていることが多い。
このような空間インデックスはデジタルデータに限ったものではない。例えば、地図帳の地名索引はページ番号とそのページの地図内の矩形グリッド番号で示される。これも空間インデックスの一例である。