四分木
領域四分木は、2次元の空間を同じ大きさの4つの象限に再帰的に分割していくもので、各ノードは特定の領域に対応したデータを保持する。各ノードは4つの子ノードを持つか、あるいは全く子ノードを持たないか(つまり葉ノード)のどちらかである。領域四分木は、分割位置がデータに依存していないため、厳密には木構造ではないとされる。より厳密に言えばTrieに近い。
深さ n の領域四分木は、 2 n ∗ 2 n {\displaystyle 2^{n}*2^{n}} ピクセルで各ピクセルの値が0か1の画像を表現するのにも使われる。根ノードはその画像領域全体を表している。ある部分領域に属するピクセルが全て0あるいは1でない場合、その部分領域はさらに分割される。つまり、各葉ノードは全ピクセルが0あるいは1のブロックを表している。
領域四分木は、平面上のデータの分布を表すのにも使われる。例えば、ある領域の温度の分布を四分木に格納すると、葉ノードは同じ温度の領域を表すことになる。
座標データ群(例えば、都市の緯度と経度)を四分木に格納する場合、各葉ノードが最大1つの座標点を格納する状態になるまで分割が行われる。
辺四分木 (edge quadtree) は、点ではなく線を格納するのに使われる。曲線はセルを微細に分割することで近似的に表す。結果として得られる木構造は非常にアンバランスであり、インデックス付けの用途には向かない。