Kotlin地图开发：如何为二维x,y坐标建立索引并高效查询区间点位

为什么TreeMap方案比全量遍历更慢 #

你的方法2性能更差的核心原因有两个：

• TreeMap的subMap返回的是视图对象，遍历的时候需要逐个跳转到红黑树的下一个节点，内存寻址开销远高于遍历连续存储的普通列表，如果你用了非基本类型的key，还会产生额外的拆箱装箱开销
• 单维索引过滤后的点占总点数比例偏高时，过滤带来的收益会被遍历开销抵消：如果你的x轴筛选后还剩超过20%的总点数，遍历筛选y的开销已经接近全量遍历的开销，再加上TreeMap的遍历 overhead，自然比全量遍历更慢

你贴的两段代码的问题也很明显：方法2中xIndex的value如果是单个点的话，相当于拿到x范围的所有点之后还是要全量遍历判断y，完全没用到y维度的索引能力，浪费了优化空间。

适合地图场景的二维坐标索引实现方案 #

1. R树/R*树（首选） #

这就是MySQL空间索引底层使用的数据结构，专门针对二维空间范围查询做了优化，会将地理上相邻的点打包成矩形节点存储，查询时直接跳过和目标查询范围不相交的节点，查询效率极高，同时支持点位的动态增删，适合绝大多数地图应用场景。Kotlin/Java生态有成熟的实现可以直接复用，不需要从零实现。

2. 静态网格索引（适合点位基本不更新的场景） #

如果你的点位数据是静态的（很少有新增删除），可以用实现更简单的网格索引：

• 把整个地图范围按固定粒度划分成等大小的网格
• 每个网格存储对应范围内的所有点位的列表
• 查询时先计算目标坐标范围覆盖了哪些网格，直接取出这些网格的点位，再做一次精细的坐标校验即可，性能非常稳定。

3. 优化现有TreeMap方案 #

如果不想更换数据结构，可以对你现有的方案做改造，性能会有明显提升：
把xIndex的value从单个点改为按y坐标排序的点位列表，拿到x范围的子Map之后，不需要遍历所有点位判断y值，直接对每个有序y列表做二分查找，就能快速筛选出符合y范围的点位，改造后的示例代码如下：

// 构建索引时，相同x的点按y排序后存储
val xIndex: TreeMap<Double, List<Point>> = points.groupBy { it.x }
    .mapValues { it.value.sortedBy { point -> point.y } }
    .toSortedMap()

// 查询逻辑
val satisfiedPoints = mutableListOf<Point>()
xIndex.subMap(startX, true, finishX, true).values.forEach { sortedYPoints ->
    // 二分查找y的上下界，不需要遍历所有点
    val left = sortedYPoints.binarySearch { it.y.compareTo(startY) }.let { if (it < 0) -it - 1 else it }
    val right = sortedYPoints.binarySearch { it.y.compareTo(finishY) }.let { if (it < 0) -it - 2 else it }
    if (left <= right) {
        satisfiedPoints.addAll(sortedYPoints.subList(left, right + 1))
    }
}

内容的提问来源于stack exchange，提问作者Cho Gyuhong