我有一个包含数百万个键的静态字典，这些键引用存储在核心外的稀疏数据结构中的值。键的数量是值数量的一小部分，例如 10%。密钥大小通常为 64 位。键是线性排序的，查询通常由按此顺序靠近的键组成。数据压缩是一个因素，但预计对数据大小影响最大的是值而不是键。密钥压缩有帮助，但并不重要。如果可能的话，查询时间应该是恒定的，并且应该很快，因为用户正在与数据进行交互。
鉴于这些条件，我想知道一种有效的方法来查询字典以确定其中是否包含特定键。查询速度是重中之重，构建时间不那么关键。
目前，我正在研究缓存遗忘 b+-trees 和与外部存储相关的保持顺序的最小完美哈希。
在这一点上，CHD 或某种其他形式的散列似乎是一种候选。由于键是按近似线性顺序查询的，因此保持顺序的哈希似乎可以避免缓存未命中，但我没有足够的知识来说明 CHD 是否可以保留键的顺序。恒定时间查询也是可取的。搜索是 O(1)，但在键空间上查询时间的上限也是未知的。
树木似乎不那么有吸引力。尽管有一些缓存忽略和缓存特定的方法，但我认为大部分工作都是针对动态字典上的范围查询而不是恒定时间成员资格查询。一般来说，处理器和存储器不喜欢分支。
沿着这些思路提出了许多问题，但是这种情况（希望）以可能对其他人有用的方式限制了问题。
任何反馈将不胜感激，谢谢