BSP树：
空间数据结构的组织通常是分层的，这意味着，最高层包含一些子层，每个子层定义自己的空间体积，而这些空间又包含自己的子层，因此，该结构是嵌套的，具有递归性质，这个层次结构中的一些元素引用了几何体。使用层次结构的主要原因是,对不同类型的查询会更快,通常一个能够从O (n)提升到 O (log n)。也就是说,与其搜索所有n对象,我们只需要访问一小部分再执行操作,比如在一个给定的方向寻找最接近的对象。
虽然查找变快了，但是，空间数据结构的构造却可能需要花费时间。并且这取决于其内部几何形状的数量和所需的数据结构的质量，然而，该领域的重大进展大大减少了构造时间，在某些情况下甚至可以实时完成。使用lazy计算和增量更新，可以进一步减少构建时间。