B树，r树，k-d树，bvh(bound volumn heuristic)树, octtree ,quadtree（待更）

引入b树是为了方便理解r树；
kd树，oct树，bvh树，oct树，quad树都是用于空间或区域（region）的管理。下面讲述按我的理解的大概的划分

b树，一种特殊的多叉树，善于描述一维的数据
r树是b树向多维的一种拓展，也是属于多叉树的一种。

多叉树相对于二叉树有一个问题就是查找时间过长，在每个中间节点上需要消耗较多的时间。所以有对b树和r树的改进方式是尽量减少树的阶数，通常取最小阶数为3，因为内部节点可以有2到3个子节点，所以3阶b树又称为2-3b树

quadtree和oct树，四叉树和八叉树是类似的，前者适用于2d，后者适用于3d，对场景从整体到细的均匀拆分，查找效率可能会不高，但是增删操作很快

k-d树，(介绍2)，本质是一种二叉树，因为是基于spatial subdivision，适合划分无交叉或重叠的场景，因为构造过程时间比较长，每次切分一个维度后，就可能需要对所有切分后数据的继续做一个排序操作，为了保持查找的高效性，k-d树更适合对静态场景进行划分和查找（主要原因是切分的轴向在生成树的时候就被固定了）。k-d树在构建时需要尽可能让左右子树平衡，以方便后面的查询操作。增删操作比较耗时。最好的应用就是用于划分空间中的点集，和光线追踪中对静态的单个物体切分用于光线求交。

bvh树（如果连接不可访问点击这里），也是一种二叉树，可以用于动态物体的添加（中文版的bvh树，链接中介绍的SPLIT_MIDDLE和SPLIT_EQUAL_COUNT因为是基于空间来划分的，只能算是启发式的kd树，划分是需要涉及到图元的拆分；而SPLIT_SAH才算是真正意义上的bvh树，因为SPLIT_SAH才算是真正意义上与空间（维度，spatial subdivision）不相关的，而是与场景中对象相关（object subdivision）），增删操作比较耗时，能很好应对交叉的情况。也可以用于对场景中静态或动态的物体的管理。

oct树和k-d树对比，两者都适用于点集管理，相对于oct树。k-d树是二叉树，octtree是八叉树，kd树相对oct树更显精简，平均查找相对来说会更高些。

r树和k-d树对比
r树相对于k-d树，r树涉及到压缩和分裂等操作，相对会操作复杂点，r树是一种平衡树，查询可能比较快，但是当阶数比较高时，查询就会效率降低，适合从整体中快速定位查找到需要的满足要求的一个范围内的东西，。
k-d树是非平衡树（不能强制转换成平衡二叉树），但是非常适合与确定物体相邻的最近的东西的查询，因为构造过程比较费时，所以相对来说适合静态的查询，并且因为无法调节平衡性，所以针对不同场景查询效率相对于其他的可能不是最优的，但是在查询已知节点的临近节点的情况时，效率是最高的，另外k-d树应对交叠的状况时效率也会变得低下。

r树和bvh树对比 1111
r树和bvh树主要用于二维或三维甚至多维的图元的管理。
r树是多叉平衡树，当为2阶时其实就是bvh树，bvh树可以是平衡二叉树。构建过程都可以是从整体到细节划分，或从细节到整体划分，或者递增的方式组装。

bvh和k-d树对比，两者适合的场景不同，前者适合图元(可以有交叉或重叠，可以是动态或静态)管理；后者适合点集管理或静态图元查找。如果将kd树应用于图元，就会涉及到繁杂的图元的拆分。bvh可以是平衡二叉树，而kd树只能是普通二叉树。另外一点就是bvh相对于kd树是灵活的，因为没有固定的轴向的切分，所以相对来说对动态物体进行管理更有优势。kd树相对于bvh树，临近查询相对来说更友好，因为bvh中的相邻的物体在子节点中可能会更分散些（与bvh构造的方法关系也很大）。
（网上查看到pbrt中用了kb树来对场景划分进行光线追踪求交）

数据结构都是死的，可能不一定适合你当前的应用环境，主要还是了解这些后构造更适合当前环境和应用以及目的的数据结构。

另外一篇类似的介绍

一种对R树的高效应用