问题标签 [b-tree]

我正在做一个需要 btree 或 b+tree 数据结构的项目。有谁知道 btree 或 b+tree 的现有实现（带有插入、删除、搜索算法）？它应该接受字符串作为输入并形成这些字符串的 btree 或 b+tree。

假设有一个 8 阶的 B 树。这意味着它可以有 8 个指针和 7 个元素。假设字母 A 到 G 存储在这个 B 树中。所以这个 B 树只是一个包含 7 个元素的节点。

然后你尝试将 J 插入到树中。没有空间，所以你必须拆分节点并创建一个新的根节点。哪个元素被提升到根节点？

B-tree 是 4 阶的，这意味着一个节点可以保存 4 个指针和 3 个键。

插入以下内容：AGIY

由于它们不能全部放在一个节点中，我知道该节点会分裂。所以我知道在插入这些东西后会有一个带有 2 个子节点的根节点，但我不知道它们会是什么样子。

如何计算 B 树的最大深度？

假设你有一个 1625 阶的 B 树，这意味着每个节点有 1625 个指针和 1624 个元素。

如果树包含 85,000,000 个键，它的最大深度是多少？

我发现这个网站可以让你在 B-tree 中插入和删除项目，并直观地向你展示 B-tree 的样子：

java b树

我正在寻找与此类似的另一个网站或程序。该站点不允许您指定 4 阶（4 个指针和 3 个元素）的 B-tree，它只允许您指定具有偶数个元素的 B-tree。另外，如果可能的话，我希望能够插入字母而不是数字。

我想我实际上找到了一个不同的网站，但那是不久前的事了，现在找不到了。

In this B+ tree 5 appears twice.

B+ tree

我有一个文本文件，其中包含有关文件系统中所有文件的范围的一些信息，如下所示 C:\Program Files\abcd.txt 12345 100 23456 200 C:\Program Files\bcde.txt 56789 50 26746 300 .. .

现在我有另一个二进制文件，它试图找出所有文件的范围。现在我正在使用线性搜索来查找上述文本文件中文件的范围信息。这是一个耗时的过程。有没有更好的编码方式？就像实现任何好的数据结构，比如 BTree。如果使用 B+ 树，我需要使用什么关键分支因子？

如果我将字母 A、G、I 和 Y 插入到 4 阶 B 树（意味着每个节点中有 4 个指针和 3 个元素），我得到以下 B 树。

如果使用插入时重新分配，它看起来会有所不同吗？插入时的重新分配如何工作？

我想知道 CouchDB 数据库 B 树中实际存储了什么？CouchDB：权威指南告诉数据库 B-tree 用于仅附加操作，并且数据库存储在单个 B-tree 中（除了 per-view B-trees）。

所以我猜附加到数据库文件的数据项是文档的修订，而不是整个文档：

这是真的吗？

如果是真的，那么如何根据这样的 B-tree 确定文档的当前版本？

这是否意味着，CouchDB 需要一个单独的“视图”数据库来索引文档的当前版本以保留 O(log n) 访问权限？在构建这样的索引时不会导致竞争条件吗？（据我所知，CouchDB 不使用写锁）。

如果我们正在寻找线的交叉点（仅限水平线和垂直线）并且我们有 n 条线，其中一半是垂直的并且没有交叉点，那么

使用合并排序对 y 值上的行端点列表进行排序将花费 N log N

每次插入删除和搜索我们的数据结构（假设它是一个 b-tree）将是 < log n

所以总搜索时间将是 N log N

我在这里缺少什么，如果使用合并排序的时间需要 N log N 并且插入和删除需要 < log n 的时间，我们是否会丢弃常数因子以给出 N log N 的总时间。如果不是，那么< log n 怎么会在 ONotation 总运行时间中丢失？

谢谢