c - 'constant database' 的快速索引格式

Question

我在linux上做c编程，遇到一个需要极快查找速度的问题。

如果一个表，像一个普通的 MySQL 表，看起来像下面这样:

ID   name   age   sex  score_a   score_b  score_c  date

并且它是常量，这意味着一旦这个表被创建并且不允许更新。它仅用于阅读。因为它是常量，所以我想必须有更好的索引格式来根据条件(如年龄、分数等)更快地查找，而不是大多数数据库中为索引实现的“B 树索引”。

Answer 1

您是要进行基于范围的搜索(“年龄在 10 到 12 岁、13 到 15 岁之间，等等”，“得分在 40 到 60 之间，61 到 70 之间，等等”)还是单值搜索(“姓名是 Quentin Smith') 还是两者兼而有之？对于单值查找，hash合适且快速；特别是对于基于范围的搜索，B 树及其变体往往是最好的。

您正在查看每行 50 字节左右区域中的原始数据，因此您将处理 1/2 GB 到 15 GB 的数据。如果它在该范围的上限，您将需要一台大机器来将普通数据保存在内存中，更不用说对其进行索引了。在该范围的低端，它完全在合理范围内。假设您为每一列编制索引，您的索引可能会占用比原始数据多一点的空间(可能多 50%)。当然，名称索引将是最大的。如果可以将 ID 列用作记录数组的索引，则 ID 列可能不需要索引，但数据中可能存在间隙，因此最好还是对其进行索引。