我有一个很大的数据结构存储在内存映射文件中。数据结构非常简单：
struct Header {
...some metadata...
uint32_t index_size;
uint64_t index[]
};
此标头放置在文件的开头，它使用结构hack-可变大小的结构，最后一个元素的大小未固定，可以更改。
char* mmaped_region = ...; // This memory comes from memory mapped file!
Header* pheader = reinterpret_cast<Header*>(mmaped_region);
内存映射区域以开头，Header并且Header :: index_size包含Header :: index数组的正确长度。这个数组包含数据元素的偏移量，我们可以这样做：
uint64_t offset = pheader->index[x];
DataItem* item = reinterpret_cast<DataItem*>(mmaped_region + offset);
// At this point, variable item contains pointer to data element
// if variable x contains correct index value (less than pheader->index_size)
所有数据元素都已排序（小于为数据元素定义的关系）。它们存储在与Header相同的内存映射区域中，但从头到尾开始。数据元素不能移动，因为它们的大小可变，而不是大小可变-标头中的索引在排序过程中移动。这非常类似于现代数据库中的B树页面，索引数组通常称为间接向量。
搜索次数
使用插值搜索算法（步数有限）而不是二进制搜索来搜索此数据结构。首先，我index要搜索一个完整的数组，我正在尝试计算-如果分布均匀，可以将搜索到的元素存储在哪里。我得到一些计算得出的索引-查看此索引处的元素，它通常不匹配。比我缩小搜索范围并重复。插值搜索步骤的数量受少量限制。之后，使用二进制搜索来搜索数据结构。这对于小型数据集非常有效，因为分布通常是统一的。插值搜索的几次迭代就完成了。
问题定义。实际上，内存映射区域可能很大。为了进行测试，我使用32Gb文件支持的存储并搜索一些随机密钥。这非常慢，因为这种模式会导致大量随机磁盘读取（无法将所有数据缓存在内存中）。
在这里可以做什么？我认为使用madvisesyscall设置MADV_RANDOM可以有所帮助，但可能不是很有用。我想与B树搜索速度相提并论。也许可以使用mincoresyscall来检查在插值搜索过程中可以轻松检查哪些数据元素？也许我可以使用某种预取功能？
插值搜索似乎是一个好主意。通常，这样做的好处很小，但是在这种情况下，即使保存少量的迭代也很有帮助，因为它们的速度很慢（磁盘I / O）。
但是，实际数据库会在其索引中复制实际键值。这样做的空间开销在性能上得到了充分证明。Btree是进一步的改进，因为它们在单个连续的内存块中打包了多个相关节点，从而进一步减少了磁盘查找。
这也可能是您的正确解决方案。您应该复制密钥以避免磁盘I / O。如果您不能更改现有的标头，则可以通过将键复制到单独的结构中并将其完全保留在内存中来逃脱。
可能会有所折衷，您只需为前N个级别的二进制搜索缓存前（2 ^ N）-1个键。这意味着您必须放弃那部分搜索的插值，但是如前所述，插值无论如何并不是一个巨大的胜利。磁盘查找已保存将很容易还清。即使仅缓存中间键（N = 1），每次查找也已经为您节省了一个磁盘搜索。一旦缓存用完，您仍然可以使用插值。
相比之下，任何尝试使用内存映射参数的方法最多只能使您提高百分之几的速度。“与B树同等”将不会发生。如果您的算法需要这些物理寻道，那么您会失败。没有任何神奇的小技巧可以解决错误的算法或错误的数据结构。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句