如何高效过滤/查询含type与timestamp字段的有序对象列表？

1. 先缩范围再遍历非排序字段 #

既然你的列表已经按timestamp排序，先用二分查找快速定位到timestamp >= 100的起始位置和timestamp <= 300的结束位置，得到一个大幅缩小的子列表。之后只需要遍历这个子列表，检查type == 3的条件就行。这种方法不用额外占用内存，而且时间开销比全列表遍历小得多——尤其是当时间范围占原列表比例很低的时候，能省大量不必要的检查。

2. 为非排序字段建反向索引 #

如果需要频繁按type做查询，没必要存多份完整的排序列表，建个反向索引就行：用一个映射结构（比如键为type值，值为对应对象在原列表中的索引的有序列表）。因为原列表按timestamp排序，每个type对应的索引列表自然也是有序的。查询时，先从反向索引里拿到type=3的所有索引，再在这个有序列表里用二分查找筛选出timestamp在[100,300]范围内的索引，最后直接从原列表取对应对象。这种方式空间开销远小于存多份全量列表，因为只存索引，不存整个对象。

3. 预建多字段组合索引 #

如果经常需要同时按timestamp和type查询，可以预先生成组合索引：比如创建一个按(type, timestamp)排序的索引列表（里面只存原列表的对象索引就行）。查询时，先找到所有type=3的索引范围，再在这个范围内用二分查找筛选timestamp的区间，直接定位到目标对象的索引，再从原列表取数据。这种方案适合固定组合条件的高频查询，能把查询复杂度降到O(log n)级别。

4. 空间与时间的权衡 #

• 如果查询频率低、内存有限，优先用第一种方法：二分缩范围+子列表遍历，零额外空间，效率比全遍历提升明显。
• 如果查询频率高、内存充足，选反向索引或组合索引，用少量空间换查询效率的大幅提升。

内容的提问来源于stack exchange，提问作者Yaroslav Biloshytskyi