java - B树和磁盘持久性

Question

一段时间以来，我一直在为大型数据集(约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字节)。关于如何持久存在很多类似的问题，但是很难理解我们为什么要决定像这样的问题(Persisting B-Tree nodes to RandomAccessFile -[SOLVED])实现的事物的全局。请分享您的想法。

Answer 1

这是基于此期间已知问题的具体情况对问题的另一种看法。这篇文章基于以下假设:

记录数约为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-treeish解决方案在这里唯一能超过哈希的是空间效率，因为为现有的预排序数据构造最佳树很简单。