时空事件重叠查询是物流调度、安防监控和出行订单系统中的常见需求。一个事件通常同时携带时间区间和空间范围，例如某辆车在特定时间段内占用某块配送区域。查询时需要同时判断时间是否交叉、空间是否相交。数据量较小时，简单的遍历比较可以快速完成；但当事件数量进入百万级后，每次查询都全量扫描会带来无法接受的延迟。本文从Java实现的角度，整理几种可落地的时空重叠查询策略。

一、重叠判定条件与朴素算法的问题

两个时间区间是否重叠，可以用简单的边界关系表达。假设事件A的时间范围是[a, b]，事件B的时间范围是[c, d]，它们存在交集的充要条件是a < d且c < b。如果使用闭区间且允许边界重叠，可以改成a <= d和c <= b，但要注意重复边界的业务语义。空间范围如果是矩形，同样可以拆成经度区间和纬度区间分别判断交集；如果是不规则多边形，则需要引入几何计算库。

朴素算法通常使用两层循环，依次比较每个事件与其他事件。假设总共有N个事件，时间复杂度是O(N²)。在小规模数据下这并没有问题，代码也最容易维护。下面是一个最基础的Java实现，展示了时间矩形和空间矩形同时重叠的判断逻辑。

public class TimeEvent {
    private final long startMillis;
    private final long endMillis;
    private final double minLng;
    private final double maxLng;
    private final double minLat;
    private final double maxLat;
    public TimeEvent(long startMillis, long endMillis,
                     double minLng, double maxLng,
                     double minLat, double maxLat) {
        this.startMillis = startMillis;
        this.endMillis = endMillis;
        this.minLng = minLng;
        this.maxLng = maxLng;
        this.minLat = minLat;
        this.maxLat = maxLat;
    }
    public boolean overlaps(TimeEvent other) {
        boolean timeOverlap = this.startMillis < other.endMillis
                && other.startMillis < this.endMillis;
        boolean spaceOverlap = this.minLng <= other.maxLng
                && other.minLng <= this.maxLng
                && this.minLat <= other.maxLat
                && other.minLat <= this.maxLat;
        return timeOverlap && spaceOverlap;
    }
}

这段代码判断逻辑清晰，但当数据量从十万级增长到千万级时，单次查询的延迟会从几毫秒恶化到数秒甚至更高。问题不在于单次比较的开销，而在于大量不可能相交的事件也被逐一检查。优化方向主要有三类：减少候选集、建立索引、以及充分利用数据库的时空索引能力。

二、基于时间轴扫描线的批量检测优化

扫描线算法的核心思想是把每个事件的开始时间和结束时间看作时间轴上的端点。将端点按时间排序后，维护一个当前活跃的事件集合。当遇到一个开始端点时，只需要把该事件与当前活跃集合中的事件进行空间重叠判断；遇到结束端点时，则把该事件从活跃集合中移除。这样做的好处是，只有时间上真正存在交叉的事件才会进入候选比较，避免了大量时间无交集的无效比较。

在实际Java实现中，可以先按查询时间范围过滤掉不可能满足条件的事件，再构造端点列表进行扫描。下面是一个简化的扫描线查询实现，假设所有事件都至少与查询时间范围有部分交叉。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Endpoint {
    long time;
    boolean isStart;
    TimeEvent event;
}
public class SweepLineQuery {
    public List<TimeEvent> queryOverlapping(List<TimeEvent> events,
                                                TimeEvent query) {
        List<Endpoint> endpoints = new ArrayList<>();
        for (TimeEvent event : events) {
            if (event.getStartMillis() > query.getEndMillis()
                    || event.getEndMillis() < query.getStartMillis()) {
                continue;
            }
            Endpoint start = new Endpoint();
            start.time = event.getStartMillis();
            start.isStart = true;
            start.event = event;
            endpoints.add(start);
            Endpoint end = new Endpoint();
            end.time = event.getEndMillis();
            end.isStart = false;
            end.event = event;
            endpoints.add(end);
        }
        endpoints.sort(Comparator.comparingLong(e -> e.time));
        List<TimeEvent> result = new ArrayList<>();
        List<TimeEvent> active = new ArrayList<>();
        for (Endpoint ep : endpoints) {
            if (ep.isStart) {
                for (TimeEvent existing : active) {
                    if (existing.overlaps(ep.event)) {
                        result.add(ep.event);
                        result.add(existing);
                    }
                }
                active.add(ep.event);
            } else {
                active.remove(ep.event);
            }
        }
        return result;
    }
}

这段代码在时间分布比较均匀、事件跨度较短的场景下效果很好。但它仍然依赖活跃集合的大小。如果大量事件在时间上长期重叠，例如年度合同、会员周期等，活跃集合会变得很大，扫描线退化为近似全量比较。此时需要进一步引入区间树或空间索引来降低单次扫描的候选数量。

扫描线算法还非常适合离线批量计算，例如夜间跑批任务中找出所有两两重叠的事件对。在线实时查询时，它更适合作为内存索引的辅助手段，而不是唯一方案。

三、使用区间树与R树构建多维索引

区间树是一种专门为区间重叠查询设计的平衡二叉树结构。它的每个节点除了保存区间本身，还额外记录以该节点为根的子树中区间的最大右端点。查询时，如果当前节点的左子树最大右端点小于查询区间的左端点，就可以整棵左子树剪枝。这样查询时间复杂度可以降到O(log n + k)，其中k是实际重叠的区间数量。

Java标准库没有直接提供区间树，但可以使用TreeMap或自己实现增广红黑树。实际项目中，如果只处理时间维度，区间树已经足够。然而时空事件同时包含空间维度，这时需要把区间树和空间索引结合。空间索引常用R树，例如JTS库的STRtree。R树将空间对象按最小外包矩形组织成树状结构，查询时先找到与目标区域相交的候选集，再对候选集做精确的时间判断。

import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.index.strtree.STRtree;
import java.util.List;
public class SpatialTimeIndex {
    private STRtree spatialIndex;
    public SpatialTimeIndex(List<SpatioEvent> events) {
        this.spatialIndex = new STRtree();
        for (SpatioEvent event : events) {
            Envelope env = new Envelope(event.getMinLng(), event.getMaxLng(),
                                        event.getMinLat(), event.getMaxLat());
            spatialIndex.insert(env, event);
        }
        spatialIndex.build();
    }
    public List<SpatioEvent> query(double minLng, double maxLng,
                                    double minLat, double maxLat,
                                    long startMillis, long endMillis) {
        Envelope queryEnv = new Envelope(minLng, maxLng, minLat, maxLat);
        List<SpatioEvent> candidates = spatialIndex.query(queryEnv);
        List<SpatioEvent> result = new ArrayList<>();
        for (SpatioEvent event : candidates) {
            if (event.getStartMillis() < endMillis
                    && event.getEndMillis() > startMillis) {
                result.add(event);
            }
        }
        return result;
    }
}

这段代码展示了先空间后时间的查询顺序。如果空间查询的选择性很低，例如查询区域覆盖了大部分地理范围，可以先按时间过滤，再对剩余事件做空间判断。实际优化时，需要根据数据的分布统计决定先过滤哪个维度。可以通过日志或计数器观察两个维度的过滤率，动态调整执行顺序。

区间树的另一个优势是支持高效的删除和插入，适合需要实时更新索引的场景。R树在插入删除方面实现复杂一些，JTS的STRtree构建后通常用于静态数据集，频繁更新时需要重建。

四、数据库时空查询与内存索引的取舍

很多业务系统的事件数据本来就存储在关系型数据库中，因此可以先利用数据库自身的时空索引完成初筛，再把小候选集加载到Java内存中做精确判断。PostgreSQL配合PostGIS可以使用GiST或SP-GiST索引同时加速时间和空间查询。MySQL 8.0支持空间索引，但对于时空组合查询，优化器不一定能高效合并两个索引，通常需要手动拆分条件。

下面是一个PostGIS参数化查询的例子。查询条件包括时间区间和空间范围，使用ST_Intersects处理几何相交，使用参数占位符避免SQL注入。

SELECT id, start_time, end_time, geom
FROM spatio_event
WHERE start_time < ? AND end_time > ?
  AND ST_Intersects(geom, ST_MakeEnvelope(?, ?, ?, ?, 4326));

数据库方案的优点是持久化、事务和并发控制都由数据库完成，Java端代码更简单。缺点是每次查询都有网络往返，延迟受限于数据库负载。内存索引方案把热点事件缓存在JVM堆内，使用区间树或R树直接查询，延迟可以降到亚毫秒级，但需要自行处理数据一致性和缓存失效。对于读多写少、数据规模单机可容纳的场景，内存索引往往能带来数量级的性能提升。

折中方案是使用本地缓存保存最近活跃的事件，例如最近24小时或未来7天的事件。查询时先查本地索引，如果结果不完整再回源数据库补查。这样既降低了数据库压力，也保证了查询的实时性。

五、并发更新与GC压力的优化实践

时空事件索引在实时系统中往往面临高频更新，例如网约车订单持续产生、车辆位置持续变化。如果使用ArrayList存储事件，每次插入删除都可能触发数组复制，而且并发读写需要加锁。Java并发包中的ConcurrentSkipListMap可以作为时间维度的有序索引，它基于跳表实现，支持高效的并发读写。空间维度则可以使用分段R树或者按地理网格拆分，每个网格维护独立的R树索引，减少锁竞争。

频繁创建临时对象会加重GC负担，尤其在高吞吐查询场景。一个常见的优化是复用Envelope对象和查询结果容器，避免在循环中大量分配新对象。例如使用ThreadLocal持有可复用的Envelope，在查询时重置其边界。对于结果列表，可以在调用方维护一个可清空的ArrayList，而不是每次返回新列表。这些细节在压测中会明显影响P99延迟。

如果空间索引采用STRtree，它构建后通常是不可变的，更新频繁时可以采用双缓冲策略：后台线程定期用最新数据构建新索引，构建完成后原子替换引用，旧索引等待无引用后回收。对于时间维度，可以维护一个按天分片的索引，每天一个区间树文件或内存对象，过期分片直接丢弃，避免全局重建。