问题标签 [b-plus-tree]

我正在尝试在 java 中实现 B+tree，并尝试使用来自 Internet 的帮助。关于这个主题几乎没有任何帮助，但我能够在 C++ 中找到这段代码，我正在尝试将它转换为 java。我的问题是b+tree的一个很好的实现？？

我有一个完全工作的 B 树，我想将它转换为 B + 树。有什么方法可以在不更改太多代码的情况下实现这一目标？可能吗？

我正在尝试实现 B+ 树。这是实际代码的一小部分。将对象指针传递给函数时遇到了一些问题。据我所知，在函数内部创建的那些对象随后会被销毁。那么，在不改变语义并保持函数递归的情况下改进这一点的好方法是什么。对于任何反馈，我们都表示感谢。

一段时间以来，我一直在使用B Plus Tree 的这种实现。我注意到“最近”缓存有问题。以下是该错误的产生方式：

1. 我添加了一些 KVP，并提交了树。
2. 我添加了更多的 KVP 并回滚了树。
3. 我添加了更多的 KVP 并提交了树。
4. 我重新启动我的应用程序并重复步骤 1,2 和 3

树在重新启动后执行第 3 步时抛出 InvalidNodeHandleException，这正是

以下断言失败。

因为 StorageHandle 相等返回 false，这反过来又是因为Unique两个根存储句柄的不同，而不仅仅是增量不同，它们是两个不同的随机数。问题的根源在于NodeCacheNormal.

在第一次运行创建树之后，当树在第二次执行中第一次加载时，它是通过LoadStorage()调用完成的，它只是将 设置_root.Node为RootNode从存储中读取。此读取RootNode包含Unique提交到磁盘的最后执行时间，并且永远不会与Unique在此执行中创建的新根句柄的时间进行比较，直到树回滚。

回滚导致缓存被清除，从而导致缓存中的RootNode被清除。回滚后，如果再次访问 RootNode，则从存储中取出它并插入到缓存中，但这次除外，它通过NodePin Lock(NodePin parent, LockType ltype, NodeHandle child)检查上述调用中句柄是否相等的主调用完成。

是否有任何已知的修复方法？缓存非常适合实现，我无法找到一个好的解决方法。

编辑1：

这是一个产生错误的类：

只需提供一个文件路径，创建它的实例并调用该ProduceBug()方法。

在带有InnoDB存储引擎的mysql中，当创建多列索引时，如(a,b,c)，会创建多少个B+树/B树？

如果可以，请详细说明。

假设我们在内存中实现 B+ 树，键位于内部节点，键-数据对位于叶节点。如果 B+tree 带有扇出 f，这意味着 B+ 树的高度为 log_f N，其中 N 是键的数量，而相应的 BST 的高度为 log_2 N。如果我们不进行任何磁盘读取并写道，B+tree 的搜索性能能否优于 Binary Search Tree 的搜索性能？如何？因为对于每个内部节点的 B+tree，我们已经对 F 多个选择做出了决定，而不是 1 用于 BST？

我正在开发一个高性能的单线程 java 应用程序。我的项目依赖于 B+ 树。因为性能非常关键，所以我不喜欢自己实现它，而是使用优化的公共实现。通过这种方式，我更加确信实施得到了充分优化。但我在 Github 或任何其他类似的在线资源上找不到合适的实现。

在哪里可以找到编写良好的 java B+ 树代码？

每当我在我的 B+ 树中插入一个新元素时，它似乎会在插入函数开始之前用要插入的数据点重写每个数据点。我发现的唯一可能原因是我的 bPLus 对象似乎无法访问每个节点中保存的 Professor 结构。例如，如果我在调试器中，所有教授值都是空的。另一方面，钥匙（cle）可以工作并且可以访问。可能与指针有关？

当我不使用按键时，如果我从 main 调用某些函数，我会得到“读取字符串字符时出错”，而其他函数会起作用。如果从类内的工作函数调用这些相同的函数也将起作用。我有一种感觉，这些问题都是相关的。

我已经包括了所有可能涉及的内容，我不知所措。

我对 B+ 树中的删除有点困惑。我在谷歌中搜索了很多，发现当要删除的键出现在索引中时，有两种实现：

1. 删除索引中的键
2. 将键保留在索引中

https://www.javatpoint.com/b-plus-tree-deletion的算法使用第一种方式。

https://www.cs.princeton.edu/courses/archive/fall08/cos597A/Notes/BplusInsertDelete.pdf的算法使用第二种方式。

所以我真的很想知道哪个是对的。

但我更倾向于将其视为未定义的行为。在这一点上，有人可以帮我弄清楚它们之间的优缺点吗？以及如何在它们之间进行选择？

提前致谢。

如果我添加一个指向父节点的指针以在拆分和插入过程中变得简单，它会影响很大吗？

通用节点看起来像这样：

从现在开始，我在现实生活中的数据库系统中可能会遇到哪些挑战。

我只是将它作为一个爱好项目来实施。