Kd木
"k"d木（）は、"k"次元のユークリッド空間にある点を分類する空間分割データ構造である。"k"d木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。"k"d木はBSP木の特殊ケースである。
"k"d木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、"k"d木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、"k"d木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を"k"dトライと呼ぶ。また、特記すべき"k"d木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。