我有一种算法和性能问题要用java来解决。我收集了大量的二维点（假设有10万个）我想得到一组在搜索点sp（x_sp，y_sp）周围给定区域内的点，以便得到满足条件的点p（x y）：
x在x_sp-constvalue和x_sp+constvalue之间，y在y_sp-constvalue和y_sp+constvalue之间
为了让您了解数字关系，constValue将类似于2、5或10，x、y将介于0和1000之间这意味着它是一个webservice，因此必须考虑到同时搜索多个不同点的可能性。
由于这些是固定点（不会由于计算或其他原因而改变），我认为最好是提供一个按x排序的对象列表和另一个按y排序的对象列表。然后，我将首先获取x范围内的点，并使用引用从另一个列表（按y排序）中获取该点的集合。然后我将选择范围缩小到Y，从而得到给定区域中的点。
我不太了解Java，所以我想咨询一下最优化的方法我应该使用哪些对象来存储已排序的点，以便快速搜索范围内的对象？或者我必须为这个任务实现我的自定义算法此外，在将这些点存储到数据库中时，sql查询是否足够快以交付结果？或者NoSQL数据库更适合这个？
我要进行我自己的测试，但我正在寻找一个开始的候选人。
最佳答案
我可能会使用一个TreeMap<Integer, TreeSet<Integer>>，其中地图的键是x坐标，对于每个x坐标，您都有一个y坐标列表。然后，您可以使用floorEntry和ceilingEntry找到您范围内的x坐标然后，对于您得到的每个TreeSet<Integer>集合，您可以使用ceiling和floor来获得适当的条目。
当然，这只给你框边界的坐标（四个角）但是TreeSet也有一个subset可以给你一个范围的值您必须使用两次；一次用于边界内的x坐标列表（您可以使用地图的keySet方法获取关键点集），然后对于每个x坐标，使用边界内的y坐标所以伪代码应该是这样的：
List<Point> result = new ArrayList<>();
int lowerX = points.ceilingKey(x - c);
int upperX = points.floorKey(x + c);
for each x coordinate in points.entrySet().subset(lowerX, upperX)
TreeSet<Integer> yCoordinates = points.get(x);
lowerY = yCoordinates.ceiling(y - c);
upperY = yCoordinates.ceiling(y + c);
for each y coordinate in yCoordinates.subset(lowerY, upperY)
result.add(new Point(x, y))
我还没有测试出来，所以可能有一些错误或我错过的东西。告诉我，我会更正答案的。
我相信
floor和ceiling调用都是log(n)调用——这是您获得性能优势的地方，因为如果您使用列表，则查找该列表将是O(n)调用。注：我不知道这是否是最有效的因此，通常不适合这样一个开放式的问题，这样你可能会在其他地方有更多的运气。