关于索引结构的问题的简短回答是“否”。RocksDB 和 LevelDB 对其索引使用树结构(准确地说是日志结构的合并树),这转换为 O(log N) 查询。
鉴于您有固定数量的固定大小的元素,您可以很容易地自己获得 O(1)“查询”。
只需将数据存储在二进制文件中。您可以使用 寻找适当的点istream::seekg
,然后使用 读取 512 个浮点数istream::read
。
struct record {
float data[512];
};
std::istream &read_record(istream &is, size_t record_number, record &r) {
auto read_start = record_number * sizeof(r);
is.seekg(read_start);
is.read(reinterpret_cast<char *>(r), sizeof(r));
}
然而,这是否真的提供了性能改进可能会有疑问。特别是,如果只有一百万个元素,二叉树的深度只有 20 左右。多路树甚至更浅。对于这么小的大小,很可能整个索引将一直在内存中,并且即使与最微不足道的磁盘 I/O 相比,在内存中搜索一棵小树也非常快。搜索索引不太可能显着影响读取速度。
同时,使用数据库不太可能比上面的代码更容易编写,而且几乎也不可能更快(尽管它有可能,例如,提供更有效的缓存比您的操作系统,因此在某些情况下它会更快)。