一段时间以来，我一直在为非常大的数据集(约1.9亿)创建索引。我有一个BTree，它可以插入数据集(通常是一个对象)/搜索关键字，当我搜索如何将数据持久化到磁盘中的文件时，我发现了这篇令人惊叹的文章(http://www.javaworld.com/article/2076333/java-web-development/use-a-randomaccessfile-to-build-a-low-level-database.html#resources)。这几乎给了我一个起点。
在这里，他们将String键索引到二进制对象(blob)。他们的文件格式将其分为3个区域，头(存储索引的起点)、索引(存储索引及其相应位置)和数据区域(存储数据)。他们正在使用RandomAccessFile来获取数据。
如何为btree定义类似的文件格式。我所知道的是，每次对磁盘进行读取，我都必须获得一个节点(通常是一个512字节的块)。关于如何持久化，有很多类似的问题，但很难理解我们为什么要决定像这个问题一样实现的东西(将B树节点持久化到RandomAccessFile-[SOLVED])。请分享你的想法。
以下是根据在此期间已知的问题细节对该问题的另一种看法。这篇文章基于以下假设：
- 记录数约1.9亿，已修复
- 密钥是64字节散列，如SHA-256
- 值是文件名：可变长度，但合理(平均长度<64字节，最大<页)
- 页面大小4 KiByte
数据库中文件名的有效表示是另一个主题，这里无法解决。如果文件名不合适(平均长度较长和/或Unicode)，那么哈希解决方案将通过增加磁盘读取次数(更多溢出、更多链接)或减少平均占用率(更多浪费空间)来惩罚您。然而，B树解决方案的反应更为有利，因为在任何情况下都可以构建最优树。
在这种情况下，最有效的解决方案——也是最容易实现的——是哈希，因为你的键已经是完美的哈希了。将散列的前23位作为页码，并将页面布局如下：
page header
uint32_t next_page
uint16_t key_count
key/offset vector
uint16_t value_offset;
byte key[64];
... unallocated space ...
last arrived filename
...
2nd arrived filename
1st arrived filename
值(文件名)从页面末尾向下存储，前缀为16位长度，键/偏移矢量向上增长。这样，低/高键计数和短/长值都不会造成不必要的空间浪费，就像固定大小结构的情况一样。在关键字搜索过程中也不必解析可变长度结构。除此之外，我的目标是尽可能简单——不要过早优化。堆的底部可以存储在页头、KO.[PH.key_count].value_offset(我的偏好)中，也可以计算为KO.Take(PH.key_count).Select(r => r.value_offset).Min()，这是您最喜欢的。
键/偏移矢量需要在键上保持排序，这样您就可以使用二进制搜索，但值可以在到达时写入，不需要按任何特定顺序。如果页面溢出，请在文件的当前端分配一个新的页面(将文件增加一页)，并将其页码存储在适当的头槽中。这意味着您可以在一个页面中进行二进制搜索，但所有链接的页面都需要逐个读取和搜索。此外，您不需要任何类型的文件头，因为文件大小在其他方面都是可用的，而且这是唯一需要维护的全局管理信息。
将文件创建为稀疏文件，其页数由您选择的哈希密钥位数表示(例如，23位的8388608页)。稀疏文件中的空页面不会占用任何磁盘空间，并且读起来都是0，这与我们的页面布局/语义非常吻合。每当需要分配溢出页时，将文件扩展一页。注意："稀疏文件"在这里不是很重要，因为当你构建完文件后，几乎所有的页面都会被写入。
为了最大限度地提高效率，您需要对数据进行一些分析。在我的模拟中，以随机数作为散列的替代，并假设平均文件名大小为62字节或更小，结果证明最佳值是2^23=8388608个桶/页。这意味着您将散列的前23位作为要加载的页码。以下是详细信息：
# bucket statistics for K = 23 and N = 190000000 ... 7336,5 ms
average occupancy 22,6 records
0 empty buckets (min: 3 records)
310101/8388608 buckets with 32+ records (3,7%)
这样可以将链接保持在最低限度，平均每次搜索只需要阅读1.04页。将散列密钥大小增加一个比特到24将预期溢出页面的数量减少到3，但将文件大小增加一倍，并将平均占用率减少到每页/存储桶11.3个记录。将密钥减少到22位意味着几乎所有页面(98.4%)都可能溢出——这意味着文件的大小实际上与23位的大小相同，但每次搜索必须进行两倍的磁盘读取。
因此，您可以看到对数据进行详细分析以决定用于哈希寻址的正确位数是多么重要。您应该运行一个使用实际文件名大小并跟踪每页开销的分析，看看22位到24位的实际图片是什么样子的。它需要一段时间才能运行，但这仍然比盲目构建一个千兆字节的文件，然后发现你浪费了70%的空间，或者搜索平均需要超过1.05页的读取要快得多。
任何基于B树的解决方案都会涉及更多(读：复杂)，但由于明显的原因，无法将每次搜索的页面读取次数减少到1.000以下，甚至只有在假设内存中可以缓存足够数量的内部节点的情况下。如果你的系统有大量的RAM，可以在很大程度上缓存数据页，那么哈希解决方案将与基于某种B树的解决方案一样受益。
尽管我很想找个借口来构建一个速度惊人的混合基数/B+树，但哈希解决方案只需付出很小的努力就可以提供基本相同的性能。B树解决方案在这里唯一能超越哈希的地方是空间效率，因为为现有的预排序数据构建最佳树是微不足道的。
有大量的开源键/值存储和完整的数据库引擎-休息一周，开始谷歌搜索。即使你最终没有使用它们，你仍然需要研究一个有代表性的横截面(架构、设计历史、关键实现细节)，以对主题有足够的了解，这样你就可以做出明智的决定并提出明智的问题。为了获得简短的概述，请尝试在谷歌上搜索索引文件格式的详细信息，包括IDX或NTX等历史文件格式，以及各种数据库引擎中使用的当前文件格式。
如果你想推出自己的格式，那么你可以考虑加入现有格式的潮流，比如dBASE变体Clipper和Visual FoxPro(我最喜欢)。这使您能够使用现有工具处理数据，包括Total Commander插件等。您不需要支持完整的格式，只需要为您的项目选择格式的单个二进制实例。非常适合调试、重新索引、临时查询等。即使不使用任何现有库，格式本身也非常简单，易于生成。索引文件格式不是那么琐碎，但仍然可以管理。
如果你想从头开始，那么你还有很长的路要走，因为节点内(页面内)设计和实践的基础在互联网和文献中都没有得到很好的体现。例如，一些旧的DDJ问题包含了关于前缀截断(也称为"前缀压缩")等方面的有效密钥匹配的文章，但我目前在"网络"上没有发现任何可比的东西，除了深深地埋在一些研究论文或源代码存储库中。
这里最重要的一项是有效搜索前缀截断密钥的算法。一旦你做到了，剩下的就或多或少地到位了。我在网上只找到了一个资源，那就是这篇DDJ(多布博士期刊)的文章：
- Walter Williams的增压顺序搜索
从这样的论文中也可以学到很多技巧
- DB2 LUW中高效的索引压缩
要了解更多细节和几乎所有其他内容，你可以做得比从头到脚阅读以下两本书更糟糕(两者都有！)：
- Goetz Graefe：现代B树技术(ISBN 1601984820)
- 吉姆·格雷：交易处理。概念与技术(ISBN 1558601902)
后者的替代方案可能是
- Philip E.Bernstein：《交易处理原理》(ISBN 1558606238)
它涵盖了类似的范围，似乎更亲力亲为，但似乎没有完全相同的深度。不过，我不能肯定(我订了一份，但还没有拿到)。
这些书让你对所有涉及的内容都有一个完整的概述，而且它们几乎没有脂肪——也就是说，你需要了解其中的几乎所有内容。他们会回答大量你不知道自己有的问题，或者你应该问自己的问题。它们涵盖了整个领域——从B树(和B+树)的基础知识到详细的实现问题，如并发、锁定、页面替换策略等等。它们使您能够利用分散在网络上的信息，如文章、论文、实现说明和源代码。
话虽如此，我建议将节点大小与体系结构的RAM页面大小(4 KB或8 KB)相匹配，因为这样你就可以利用操作系统的分页基础设施，而不是与之冲突。而且你可能最好将索引和blob数据保存在单独的文件中。否则，你就不能把它们放在不同的卷上，数据会破坏不属于你程序的子系统(硬件、操作系统等)中索引页的缓存。
我肯定会使用B+树结构，而不是像普通的B树那样用数据来填充索引页。我还建议使用间接向量(Graefe有一些有趣的细节)与带长度前缀的键相结合。将密钥视为原始字节，并将所有排序规则/规范化/上下无意义的内容排除在核心引擎之外。如果用户愿意的话，他们可以给你提供UTF8——相信我，你不想关心这些
在内部节点中只使用后缀截断(即区分"John Smith"one_answers"Lucky Luke"，"K"或"L"与给定的密钥一样有效)，在叶中只使用前缀截断(即存储"John Smith’和"John Smythe"而不是"John Smith‘和"John Smith")。
它简化了实现，并为您提供了可能获得的大部分好处。即，共享前缀往往在叶级别(按索引顺序在相邻记录之间)非常常见，但在内部节点(即在更高的索引级别)则不常见。相反，叶子无论如何都需要存储完整的密钥，因此没有什么可以截断和丢弃的，但内部节点只需要路由流量，并且在一个页面中可以容纳比未截断的密钥多得多的截断密钥。
针对一个充满前缀截断密钥的页面进行密钥匹配是非常有效的——平均而言，每个密钥的比较不到一个字符——但这仍然是一种线性扫描，即使所有的跳跃都是基于跳跃计数的。这在一定程度上限制了有效页面大小，因为二进制搜索在遇到截断键时会更加复杂。格雷夫对此有很多细节。启用更大节点大小(数千个键而不是数百个键)的一种解决方法是将节点布局为具有两个或三个级别的迷你B树。它可以让事情变得闪电般快(尤其是如果你尊重像64字节缓存行大小这样的神奇阈值)，但它也会让代码变得非常复杂。
我会选择一个简单而吝啬的设计(在范围上类似于IDA的钥匙/价值商店)，或者使用现有的产品/库，除非你正在寻找新的爱好。。。