问题标签 [b-plus-tree]

我正在尝试实现 B+ 树（用 C 语言），每个键都是一些数据（int/float/string），对应的值是一个列表，其大小不固定。

我想将此树存储在一个文件中，并在需要时稍后访问。您可以考虑如下实现：

• 每个搜索键对应于文件中的一个页面，并且
• 每个页面都包含与该键对应的一组值

问题是：我不能只将一个页面分配给一个键，因为它可能消耗很少并且浪费整个页面。所以我需要一种在文件系统中实现 B+ 树的持久方法，而不是主内存。

我正在使用螃蟹技术开发 B+Tree 的内存版本（在释放父锁之前，您必须获得子锁）。

我的目标实现语言是 C# 在我的实现中我有一个支持Dictionary<Page, Node>，对于 XS 和 U 锁存器，我为 Dictionary 中的每个可用节点使用不同的 ReaderWriterLockSlim。所以获得 SLatch 基本上看起来像：

当我运行多线程测试时，我在树的行为中看到了一个非常奇怪的模式。对于测试，我使用了 16 核机器和 10 000 000 个多头。树键计数为 16，因此有近 600 000 个 DataNode 对象和 70 000 个 IndexNode 对象。

当我在 8 个线程上同时在树中插入值时运行测试。我看到起初核心使用率从 1 core 线性上升到 3 。但在开始一段时间后，它平均恢复到 1.5 个核心，并且核心使用率变得恒定。在并行分析器中，我看到在峰值之前 3 个核心进程大部分都在休眠，但在峰值之后，它们开始互相等待被阻塞。

任何人都可以提出任何想法，我应该在哪里查看问题或我使用的方法有哪些缺陷。

谢谢。

在 B+ 树中，是否可以存在非叶节点以删除其键值？这意味着 B+ 树在其中间非叶节点中具有值，但在其任何叶节点中都没有。

考虑以下结构。我在研究 B+ 树时遇到了这个问题。在这个结构中，13 不是叶节点。但它是一个非叶子节点。（实际上在前面的说明中已删除。图片链接。在此链接中转到页面底部）

如果是，那么数据是如何被删除的？

这是一个错误还是我遗漏了什么？

我试图从我之前创建的 B 树实现中创建一个 B+ 树，但我真的迷失了在这里......我尝试实现的 B 到 B+ 的唯一区别是将密钥存储在叶子上而不是删除它们。
示例：
最终 B 树
3 6 假
1 2 真
4 5 真
7 8 9 10 真

最终 B+ 树
3 6 假
1 2 真
3 4 5 真
6 7 8 9 10 真

这就是我为 B 树所拥有的（我真的不想发布整个代码，但是解释所有代码会更加困难和混乱）。我至少会欣赏一些想法......

主要

B树节点

B树

我在一个数据文件上构建了一个类似于非聚集 B+ 树索引（在字段上说 K）的数据结构，其中文件偏移量作为我的叶节点值。现在对于任何查找，我需要从文件上的随机点读取。据我了解，Java 上的大多数 I/O 方法都针对批量查找进行了优化。但由于我已经在另一个字段上有一个聚集索引，所以不能按 K 排序。Java中是否有任何选项可以优化从随机偏移量中批量读取文件？

谢谢 ！！

我似乎无法找到 B* 树是什么的可靠答案。我知道 B 树将键和数据存储在其内部节点和叶节点中，B+ 树将键存储在其内部节点中，数据存储在其叶节点中，但是 B* 树有何不同？

我在我的一篇练习论文上有这个问题，我想知道我该怎么做。欢迎任何帮助。

考虑下面的 B+-tree，其中一个节点可以包含两个搜索键值和三个指针。

插入搜索键值为 38 的新记录后重绘 B+-树。（为简单起见，您的图可能仅包括受影响的节点）

这就是我认为应该是答案

我正在使用 CSharpTest.Net.BPlusTree 库进行数据存储。如何从不同进程的同一棵树中读取？

我有数十亿个对象，我试图将它们构建在序列化为 HDD 的 B+Tree 中。我使用BPlusTree库作为数据结构，使用protobuf-net进行序列化/反序列化。在这方面，我将我的类定义为：

我将我的序列化器/反序列化器定义如下：

然后我在 B+Tree ( This library ) 数据结构中使用它们，该数据结构定义为：

B+Tree 被定义为键值对的字典。My key(ie, C) 是一个整数，序列化器是BPlusTree库的默认序列化器。MyValue是一个自定义对象B<C,M>，使用protobuf-net.

我的问题肯定会发生，但几乎是随机的；总是在搜索Keys，它突然开始反序列化Valueand 在第一次调用B<C, M> ReadFrom(System.IO.Stream stream)它时要求TypeModel.CS和ProtoReader.CS文件。我从NuGet.

我正在使用两个很棒的库BPlusTree和Protobuf-net来从磁盘存储/检索大量项目。我被允许修改任何序列化的项目......到目前为止一切都很完美。在第一次修改时速度下降到 1/3，在第二次修改时下降到 1/4，依此类推，如下图所示：

每条线代表对相同数据的不同运行；重要的一点是，当修改集合中的项目时，在所有测试中速度都会降低。修改的项是一个类的列表；直到第一次降级（即第 22 组 - 大约第 22*200,000 个项目），此列表仅包含一个实例。之后项目一个接一个地更新为具有更多的类的两个对象，直到第 42 组（大约 42*200,000 个项目），当每个项目开始有 3 个实例时，依此类推。

我的物品来自“B”类，其实现如下：

我将我的（反）序列化器定义如下：

我怎么能说_lambda<...>尺寸是速度下降的原因？请检查以下图表以进行澄清。正如您所注意到的，时刻_lambda<...>大小发生了变化，我开始受到速度惩罚。

有什么建议吗？

PS：这项工作有数千行，但缩小代码范围似乎是由“ReadFrom”和“WriteTo”函数引发的。因此，我在这里只放这些行。