C# 中高性能搜索的最佳数据结构

Question

我想知道哪种数据结构能为我的场景提供更好的性能...... 我的要求是： 可能有数百万条记录的巨大数据集，我只会写一次，并且在执行生命周期内不会再更改它，我不需要它以排序的方式存储...... 我本想使用 List 但如果我使用 Linq 查询并在 where 条件中调用 InRange 性能非常糟糕...如果我执行 foreach，性能不会那么好...我很确定有最好的方法（我正在考虑使用结构和/或实现 IEquatable 但性能没有提高...... 女巫是 C# 中查询速度最快且性能最佳的数据结构吗？ 我想要的是一个数据结构来存储 Rnage 类的数百万个实例

class Range
{
    public int Low {get; set;}
    public int High {get; set;}    
    public bool InRange(int val) { return val >= Low && val <= High; }
}

一个逻辑示例是 List 但我担心 List 类没有针对我的要求进行优化...因为它已排序并且我不需要排序这对表演影响很大...

感谢您的帮助！

Answer 1

我想你可能想要一棵区间树。 Stackoverflow 用户 alan2here 最近就他正在从事的项目提出了几个问题； Eric Lippert 向他指出了其中一个中的区间树结构。