B 树和磁盘持久化
BTrees and Disk Persistance
有一段时间我致力于为非常大的数据集（大约 1.9 亿）创建索引。我有一个可以插入数据集（通常是 object）/搜索键的 BTree，当我搜索如何将数据保存到磁盘文件中时，我看到了这篇很棒的文章（http://www.javaworld.com/article/2076333/java-web-development/use-a-randomaccessfile-to-build-a-low-level-database.html#resources）。这几乎给了我起点。
他们在这里将字符串键索引为二进制 object (blob)。他们的文件格式分为 3 个区域，header（存储索引的起点），索引（存储索引及其对应位置）和数据区域（存储数据）。他们正在使用 RandomAccessFile 来获取数据。
如何为 btree 定义类似的文件格式。我所知道的是每次对磁盘进行读取时，我都必须获得一个节点（通常是一个 512 字节的块）。关于如何坚持有很多类似的问题，但不难理解为什么我们决定像这个问题那样实施我们实施的事情的大局（Persisting B-Tree nodes to RandomAccessFile -[SOLVED]）。请分享您的想法。
有很多开源 key/value 商店和完整的数据库引擎 - 休息一周，开始谷歌搜索。即使你最终使用了其中的 none，你仍然需要研究一个有代表性的横截面（架构、设计历史、关键实现细节）以获得对主题的足够概述，以便你可以做出明智的决定并提出聪明的问题。如需简要概述，请尝试 Google 索引文件格式的详细信息，既包括 IDX 或 NTX 等历史文件格式，也包括各种数据库引擎中当前使用的文件格式。
如果您想推出自己的格式，那么您可能会考虑搭上现有格式的潮流，例如 dBASE 变体 Clipper 和 Visual FoxPro（我的最爱）。这使您能够使用现有工具处理数据，包括 Total Commander 插件等。您不需要支持完整格式，只需支持您为项目选择的格式的单个二进制实例。非常适合调试、重建索引、即席查询等。即使您不使用任何现有库，格式本身也非常简单且易于生成。索引文件格式不是那么简单但仍然易于管理。
如果您想从头开始自己动手，那么您还有很长的路要走，因为节点内（页面内）设计和实践的基础知识在 Internet 和文献中很少见.例如，一些旧的 DDJ 问题包含有关与前缀截断 (a.k.a.'prefix compression') 相关的高效密钥匹配的文章，等等，但我目前在网上找不到可比的东西，除了深埋在一些研究论文或源代码库中。
这里最重要的一项是有效搜索前缀截断键的算法。一旦你明白了这一点，其余的或多或少就会到位。我在网上只找到一个资源，就是这篇 DDJ（Dobb 博士的期刊）文章：
- Supercharging Sequential Searches 沃尔特·威廉姆斯
很多技巧也可以从像
这样的论文中收集到
要了解更多细节和几乎所有其他内容，您可能比从头到尾阅读以下两本书（这两本书！）更糟糕：
- Goetz Graefe: Modern B-Tree Techniques (ISBN 1601984820)
- Jim Gray: Transaction Processing. Concepts and Techniques (ISBN 1558601902)
后者的替代方案可能是
它涵盖了相似的频谱，似乎更实用一些，但似乎没有完全相同的深度。不过我不能肯定地说（我已经订购了一份，但还没有收到）。
这些书为您提供了对所有相关内容的完整概述，而且它们几乎不含脂肪 - 即您需要了解其中的几乎所有内容。他们会回答无数您不知道的问题，或者您应该问自己的问题。它们涵盖了整个领域——从 B-tree（和 B+tree）基础知识到详细的实现问题，如并发、锁定、页面替换策略等。它们使您能够利用散布在网络上的信息，例如文章、论文、实施说明和源代码。
话虽如此，我建议将节点大小与体系结构的 RAM 页面大小（4 KB 或 8 KB）相匹配，因为这样您就可以利用 OS 的分页基础结构而不是 运行 有冲突。您最好将索引和 blob 数据保存在单独的文件中。否则，您不能将它们放在不同的卷上，并且数据会阻碍索引页面在不属于您的程序的子系统（硬件、OS 等）中的缓存。
我肯定会使用 B+ 树结构，而不是像在普通 B 树中那样用数据淡化索引页。我还建议使用与长度前缀键相关的间接向量（Graefe 有一些有趣的细节）。将密钥视为原始字节，并将所有 collation/normalisation/upper-lower 废话排除在核心引擎之外。如果用户愿意，他们可以为您提供 UTF8 - 您不必关心这个，相信我。
在内部节点中仅使用后缀截断（即为了区分 'John Smith' 和 'Lucky Luke'，'K' 或 'L' 工作就像以及给定的键）并且只在叶子中截断前缀（即你存储 'John Smith' 和 7+'ythe' 而不是 'John Smith' 和 'John Smythe'）。
它简化了实施，并为您提供了大部分可能获得的效果。 IE。共享前缀在叶级别（在索引顺序的相邻记录之间）往往非常常见，但在内部节点中并不常见，即在更高的索引级别。相反，叶子无论如何都需要存储完整的密钥，因此那里没有什么可以截断和丢弃的，但是内部节点只需要路由流量，您可以在页面中容纳比未截断的更多的截断键。
针对充满前缀截断键的页面进行键匹配非常有效 - 平均每个键比较的字符少于一个字符 - 但它仍然是线性扫描，即使所有基于跳过计数的向前跳跃.这在某种程度上限制了有效页面大小，因为二进制搜索在面对截断键时更加复杂。 Graefe 对此有很多详细信息。启用更大节点大小（数千个而不是数百个键）的一种解决方法是将节点布局为具有两层或三层的迷你 B 树。它可以让事情变得快如闪电（特别是如果你尊重像 64 字节缓存行大小这样的神奇阈值），但它也使代码变得非常复杂。
我会选择简单精简的设计（范围类似于 IDA's key/value 商店），或者使用现有的 product/library，除非您正在寻找新的爱好.. .
根据同时已知的问题细节，这是对这个问题的另一种看法。 post 基于以下假设：
- 记录数约1.9亿，固定
- 密钥是 64 字节的哈希值，如 SHA-256
- 值是文件名：可变长度，但合理（平均长度 < 64 字节，最大 < 页）
- 页面大小 4 KiByte
数据库中文件名的有效表示是另一个主题，无法在此处解决。如果文件名很尴尬 - 平均 and/or Unicode - 那么散列解决方案将通过增加磁盘读取计数（更多溢出，更多链接）或减少平均占用率（更多浪费 space）来惩罚你。但是，B-tree 解决方案的反应稍微温和一些，因为在任何情况下都可以构建最佳树。
在这种情况下最有效的解决方案 - 也是最简单的实现方式 - 是散列，因为您的密钥已经是完美的散列。取hash的前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 位长度为前缀，key/offset 向量向上增长。这样，low/high 键计数和 short/long 值都不会造成 space 的不必要浪费，而 fixed-size 结构就是这种情况。您也不必在键搜索期间解析 variable-length 结构。除此之外，我的目标是尽可能简单——不要过早优化。堆的底部可以存储在页面 header 中，KO.[PH.key_count].value_offset（我的偏好），或计算为 KO.Take(PH.key_count).Select(r => r.value_offset).Min()，任何你最喜欢的。
key/offset 向量需要在键上保持排序，以便您可以使用二进制搜索，但值可以在到达时写入，它们不需要按任何特定顺序排列。如果页面溢出，则在文件的当前末尾分配一个新的页面（将文件增加一页）并将其页码存储在适当的 header 槽中。这意味着您可以在一个页面内进行二进制搜索，但所有链接的页面都需要一个接一个地读取和搜索。此外，您不需要任何类型的文件 header，因为文件大小是可用的，而且这是唯一需要维护的全局管理信息。
将文件创建为一个稀疏文件，其页数由您选择的哈希键位数表示（例如，8388608 页表示 23 位）。稀疏文件中的空页不占用任何磁盘 space 并读取为全 0，这与我们的页面 layout/semantics 完美配合。每当您需要分配溢出页时，将文件扩展一页。注意：'sparse file' 在这里不是很重要，因为几乎所有页面都将在您完成构建文件后写入。
为了获得最大效率，您需要 运行 对您的数据进行一些分析。在我的模拟中——使用随机数 stand-ins 作为散列，并假设平均文件名大小为 62 字节或更小——最佳结果是 2^23 = 8388608 buckets/pages。这意味着您将哈希的前 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，但文件大小会增加一倍并将平均占用减少到每个 page/bucket 11.3 条记录。将密钥减少到 22 位意味着几乎所有页面 (98.4%) 都可能溢出 - 这意味着文件实际上与 23 位的文件大小相同，但每次搜索必须执行两倍的磁盘读取。
因此您会看到 运行 对数据进行详细分析以决定用于哈希寻址的适当位数是多么重要。您应该 运行 使用实际文件名大小并跟踪 per-page 开销的分析，以查看 22 位到 24 位的实际图片是什么样的。 运行 需要一段时间，但这仍然比盲目构建 multi-gigabyte 文件然后发现您浪费了 space 的 70% 或者搜索花费的时间远远超过 1.05 快得多页面平均阅读量。
任何基于 B-tree 的解决方案都会涉及更多（阅读：复杂）但不能将每次搜索的页面读取计数减少到 1.000 以下，原因很明显，甚至只是假设有足够的内部节点的数量可以缓存在内存中。如果您的系统具有如此巨大的 RAM，以至于可以在很大程度上缓存数据页，那么散列解决方案将与基于某种 B-tree.
的散列解决方案一样受益。
尽管我很想找个借口来构建一个速度惊人的混合 radix/B+树，但哈希解决方案只需付出很少的努力就可以提供基本相同的性能。B-treeish 解决方案唯一可以超越散列的地方是 space 效率，因为为现有 pre-sorted 数据构建最佳树是微不足道的.
有一段时间我致力于为非常大的数据集（大约 1.9 亿）创建索引。我有一个可以插入数据集（通常是 object）/搜索键的 BTree，当我搜索如何将数据保存到磁盘文件中时，我看到了这篇很棒的文章（http://www.javaworld.com/article/2076333/java-web-development/use-a-randomaccessfile-to-build-a-low-level-database.html#resources）。这几乎给了我起点。
他们在这里将字符串键索引为二进制 object (blob)。他们的文件格式分为 3 个区域，header（存储索引的起点），索引（存储索引及其对应位置）和数据区域（存储数据）。他们正在使用 RandomAccessFile 来获取数据。
如何为 btree 定义类似的文件格式。我所知道的是每次对磁盘进行读取时，我都必须获得一个节点（通常是一个 512 字节的块）。关于如何坚持有很多类似的问题，但不难理解为什么我们决定像这个问题那样实施我们实施的事情的大局（Persisting B-Tree nodes to RandomAccessFile -[SOLVED]）。请分享您的想法。
有很多开源 key/value 商店和完整的数据库引擎 - 休息一周，开始谷歌搜索。即使你最终使用了其中的 none，你仍然需要研究一个有代表性的横截面（架构、设计历史、关键实现细节）以获得对主题的足够概述，以便你可以做出明智的决定并提出聪明的问题。如需简要概述，请尝试 Google 索引文件格式的详细信息，既包括 IDX 或 NTX 等历史文件格式，也包括各种数据库引擎中当前使用的文件格式。
如果您想推出自己的格式，那么您可能会考虑搭上现有格式的潮流，例如 dBASE 变体 Clipper 和 Visual FoxPro（我的最爱）。这使您能够使用现有工具处理数据，包括 Total Commander 插件等。您不需要支持完整格式，只需支持您为项目选择的格式的单个二进制实例。非常适合调试、重建索引、即席查询等。即使您不使用任何现有库，格式本身也非常简单且易于生成。索引文件格式不是那么简单但仍然易于管理。
如果您想从头开始自己动手，那么您还有很长的路要走，因为节点内（页面内）设计和实践的基础知识在 Internet 和文献中很少见.例如，一些旧的 DDJ 问题包含有关与前缀截断 (a.k.a.'prefix compression') 相关的高效密钥匹配的文章，等等，但我目前在网上找不到可比的东西，除了深埋在一些研究论文或源代码库中。
这里最重要的一项是有效搜索前缀截断键的算法。一旦你明白了这一点，其余的或多或少就会到位。我在网上只找到一个资源，就是这篇 DDJ（Dobb 博士的期刊）文章：
- Supercharging Sequential Searches 沃尔特·威廉姆斯
很多技巧也可以从像
这样的论文中收集到要了解更多细节和几乎所有其他内容，您可能比从头到尾阅读以下两本书（这两本书！）更糟糕：
- Goetz Graefe: Modern B-Tree Techniques (ISBN 1601984820)
- Jim Gray: Transaction Processing. Concepts and Techniques (ISBN 1558601902)
后者的替代方案可能是
它涵盖了相似的频谱，似乎更实用一些，但似乎没有完全相同的深度。不过我不能肯定地说（我已经订购了一份，但还没有收到）。
这些书为您提供了对所有相关内容的完整概述，而且它们几乎不含脂肪 - 即您需要了解其中的几乎所有内容。他们会回答无数您不知道的问题，或者您应该问自己的问题。它们涵盖了整个领域——从 B-tree（和 B+tree）基础知识到详细的实现问题，如并发、锁定、页面替换策略等。它们使您能够利用散布在网络上的信息，例如文章、论文、实施说明和源代码。
话虽如此，我建议将节点大小与体系结构的 RAM 页面大小（4 KB 或 8 KB）相匹配，因为这样您就可以利用 OS 的分页基础结构而不是 运行 有冲突。您最好将索引和 blob 数据保存在单独的文件中。否则，您不能将它们放在不同的卷上，并且数据会阻碍索引页面在不属于您的程序的子系统（硬件、OS 等）中的缓存。
我肯定会使用 B+ 树结构，而不是像在普通 B 树中那样用数据淡化索引页。我还建议使用与长度前缀键相关的间接向量（Graefe 有一些有趣的细节）。将密钥视为原始字节，并将所有 collation/normalisation/upper-lower 废话排除在核心引擎之外。如果用户愿意，他们可以为您提供 UTF8 - 您不必关心这个，相信我。
在内部节点中仅使用后缀截断（即为了区分 'John Smith' 和 'Lucky Luke'，'K' 或 'L' 工作就像以及给定的键）并且只在叶子中截断前缀（即你存储 'John Smith' 和 7+'ythe' 而不是 'John Smith' 和 'John Smythe'）。
它简化了实施，并为您提供了大部分可能获得的效果。 IE。共享前缀在叶级别（在索引顺序的相邻记录之间）往往非常常见，但在内部节点中并不常见，即在更高的索引级别。相反，叶子无论如何都需要存储完整的密钥，因此那里没有什么可以截断和丢弃的，但是内部节点只需要路由流量，您可以在页面中容纳比未截断的更多的截断键。
针对充满前缀截断键的页面进行键匹配非常有效 - 平均每个键比较的字符少于一个字符 - 但它仍然是线性扫描，即使所有基于跳过计数的向前跳跃.这在某种程度上限制了有效页面大小，因为二进制搜索在面对截断键时更加复杂。 Graefe 对此有很多详细信息。启用更大节点大小（数千个而不是数百个键）的一种解决方法是将节点布局为具有两层或三层的迷你 B 树。它可以让事情变得快如闪电（特别是如果你尊重像 64 字节缓存行大小这样的神奇阈值），但它也使代码变得非常复杂。
我会选择简单精简的设计（范围类似于 IDA's key/value 商店），或者使用现有的 product/library，除非您正在寻找新的爱好.. .
根据同时已知的问题细节，这是对这个问题的另一种看法。 post 基于以下假设：
- 记录数约1.9亿，固定
- 密钥是 64 字节的哈希值，如 SHA-256
- 值是文件名：可变长度，但合理（平均长度 < 64 字节，最大 < 页）
- 页面大小 4 KiByte
数据库中文件名的有效表示是另一个主题，无法在此处解决。如果文件名很尴尬 - 平均 and/or Unicode - 那么散列解决方案将通过增加磁盘读取计数（更多溢出，更多链接）或减少平均占用率（更多浪费 space）来惩罚你。但是，B-tree 解决方案的反应稍微温和一些，因为在任何情况下都可以构建最佳树。
在这种情况下最有效的解决方案 - 也是最简单的实现方式 - 是散列，因为您的密钥已经是完美的散列。取hash的前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 位长度为前缀，key/offset 向量向上增长。这样，low/high 键计数和 short/long 值都不会造成 space 的不必要浪费，而 fixed-size 结构就是这种情况。您也不必在键搜索期间解析 variable-length 结构。除此之外，我的目标是尽可能简单——不要过早优化。堆的底部可以存储在页面 header 中，KO.[PH.key_count].value_offset（我的偏好），或计算为 KO.Take(PH.key_count).Select(r => r.value_offset).Min()，任何你最喜欢的。
key/offset 向量需要在键上保持排序，以便您可以使用二进制搜索，但值可以在到达时写入，它们不需要按任何特定顺序排列。如果页面溢出，则在文件的当前末尾分配一个新的页面（将文件增加一页）并将其页码存储在适当的 header 槽中。这意味着您可以在一个页面内进行二进制搜索，但所有链接的页面都需要一个接一个地读取和搜索。此外，您不需要任何类型的文件 header，因为文件大小是可用的，而且这是唯一需要维护的全局管理信息。
将文件创建为一个稀疏文件，其页数由您选择的哈希键位数表示（例如，8388608 页表示 23 位）。稀疏文件中的空页不占用任何磁盘 space 并读取为全 0，这与我们的页面 layout/semantics 完美配合。每当您需要分配溢出页时，将文件扩展一页。注意：'sparse file' 在这里不是很重要，因为几乎所有页面都将在您完成构建文件后写入。
为了获得最大效率，您需要 运行 对您的数据进行一些分析。在我的模拟中——使用随机数 stand-ins 作为散列，并假设平均文件名大小为 62 字节或更小——最佳结果是 2^23 = 8388608 buckets/pages。这意味着您将哈希的前 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，但文件大小会增加一倍并将平均占用减少到每个 page/bucket 11.3 条记录。将密钥减少到 22 位意味着几乎所有页面 (98.4%) 都可能溢出 - 这意味着文件实际上与 23 位的文件大小相同，但每次搜索必须执行两倍的磁盘读取。
因此您会看到 运行 对数据进行详细分析以决定用于哈希寻址的适当位数是多么重要。您应该 运行 使用实际文件名大小并跟踪 per-page 开销的分析，以查看 22 位到 24 位的实际图片是什么样的。 运行 需要一段时间，但这仍然比盲目构建 multi-gigabyte 文件然后发现您浪费了 space 的 70% 或者搜索花费的时间远远超过 1.05 快得多页面平均阅读量。
任何基于 B-tree 的解决方案都会涉及更多（阅读：复杂）但不能将每次搜索的页面读取计数减少到 1.000 以下，原因很明显，甚至只是假设有足够的内部节点的数量可以缓存在内存中。如果您的系统具有如此巨大的 RAM，以至于可以在很大程度上缓存数据页，那么散列解决方案将与基于某种 B-tree.
的散列解决方案一样受益。尽管我很想找个借口来构建一个速度惊人的混合 radix/B+树，但哈希解决方案只需付出很少的努力就可以提供基本相同的性能。B-treeish 解决方案唯一可以超越散列的地方是 space 效率，因为为现有 pre-sorted 数据构建最佳树是微不足道的.