R木
入力は探索矩形(クエリボックス)である。R木での探索はB木での探索によく似ている。探索は根ノードを始点とする。内部ノードには外接矩形とそれに対応した子ノードへのポインタがあり、葉ノードには空間オブジェクトの矩形がある。それぞれのノードにある矩形について、探索矩形と重なるかどうかを判断する。重なるなら、対応する子ノードについても探索を行う。探索はこのように再帰的に行われ、全ての重なりを持つノードが探索される。葉ノードに到達すると、そこに格納されている外接矩形についても同様の比較が行われ、対応する空間オブジェクトが探索矩形内にあるかどうか(探索結果に含められるか否か)が決定される。
Sort-Tile-Recursive (STR)
Packed ヒルベルトR木 - ノードを矩形の中心のヒルベルト値を使ってソートし、再帰的に木構造を構築する。
Nearest-X - X座標の値に従って矩形をソートし、ノードを生成する。