我应该使用哪种数据结构来存储大型10,000个数据集并执行最快的搜索，并占用最少的内存？

Question

*假设我有10,000个圆（x，y，r）的值，并且我想找到一个点（p1，p2）位于哪个圆圈内，以便为此查询获得最快的响应我应该使用哪些数据结构来存储这些10,000个圆圈数据。 这是一个静态数据，意味着一次构造，

但是最常见的操作是搜索查询。它不会是一个基于范围的搜索或不是最近的邻居搜索

如何B树，B +树或R树或四叉树或线性插值搜索或任何位图类，解决方案应占用最少的内存，权衡是好的*

Answer 1

你至少有三种选择：

• 使用包围体层次（BVH）;在这种情况下，我认为2D球体树（圆形树）将成为一种方式;所以你构造了一个每个节点都是圆形的树。每个节点可以包含儿童圈。你的输入圈子将在叶子上。这种方式点搜索将在时间logN，但结构将在空间NlogN。但是，一般BVH可能难以构建。
• 使用基于树的N元空间分区（二元空间分区，qudtree，2D kd-tree）;这次你划分空间，每个空间可能包含一些球体。这些算法与BVH具有相同的复杂度，但最有可能的效率会低于BVH - 我怀疑用于圆圈的较小的thight拟合。但是，一些空间分区（例如四叉树）可以更容易构建。
• 使用空间散列。这是空间将被分割成具有确切大小的立方体（桶）并且这些立方体被散列。基本上，您可以将其视为一个统一的像素网格（但巧妙地存储），每个像素都有一个包含圆圈的列表。这在理论上给出了O（1）的搜索。但空间可能更难预测。它在理论上是O（N），但由于常数因子可能比BVH大 - 并且最可能取决于圆的面积和位置的分布（例如，具有圆的像素的数量）。