低计算量下基于双日期约束筛选物品的最优数据结构选型咨询

我有一个包含100,000条Item的列表，需要高频查询符合指定日期的有效Item（即指定日期处于Item的startDate与endDate之间）。Item结构仅需初始化一次，包含唯一ID、someInfo、startDate和endDate。我原本考虑将数据按endDate降序排序，通过二分查找定位首个endDate早于指定日期的条目以排除无效项，但还需针对startDate重新排序，请问是否有更优方案？推荐何种数据结构？

var itemList = new List<Item>();

class Item
{
     public string id {get; set;}
     public string startDate { get; set; }
     public string endDate { get; set; }
     public string someInfo { get; set; }  
}

基础优化前提 #

先把startDate和endDate从字符串转为DateTime类型，字符串比较性能差且易出现格式错误，这是所有优化的基础。

推荐方案 #

1. 区间树（Interval Tree）

这是专门针对"查询包含某个点的所有区间"场景设计的数据结构，初始化构建树后，每次查询的时间复杂度为O(logN + K)（K为匹配条目数），完美适配高频查询需求。你可以自行实现，也可以使用现成的NuGet包（比如IntervalTree）快速落地。

2. 双排序索引+哈希交集

如果不想引入第三方依赖，可做一次预处理：

• 将所有Item按startDate升序排序，生成列表A；
• 将所有Item按endDate升序排序，生成列表B；
  查询流程：
• 在列表B中用二分查找定位第一个endDate >= 指定日期的位置，此位置之后的条目满足endDate条件；
• 在列表A中用二分查找定位最后一个startDate <= 指定日期的位置，此位置之前的条目满足startDate条件；
• 为每个Item的ID建立哈希集合，快速取两个结果集的交集，得到最终有效条目。

3. 内存数据库索引

如果代码复杂度优先级更高，可以用SQLite内存模式，将Item导入后给startDate和endDate建立联合索引，直接通过SQL语句WHERE startDate <= @targetDate AND endDate >= @targetDate查询，数据库的索引优化会自动处理高效查找，实现成本极低。

初始方案的问题 #

你的方案仅处理了endDate的过滤，但startDate过滤需要重复排序，每次查询的时间复杂度会飙升至O(NlogN)，完全无法支撑高频查询需求。上面的方案均为单次预处理+O(logN)级查询，性能差距极大。

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