问题标签 [b-tree]

所以，这是我的小问题。

假设我有一个桶列表 a ₀ ... a _n分别包含 L <= c ₀ ... c _n < H 项目。我可以决定 L 和 H 的限制。我什至可以动态更新它们，尽管我认为这不会有太大帮助。

桶的顺序很重要。我不能去交换它们。

现在，我想索引这些存储桶，以便：

• 我知道物品的总数
• 我可以查找第 i 个元素
• 我可以从任何存储桶中添加/删除项目并有效地更新索引

看起来很容易吧？看到这些标准，我立即想到了一棵芬威克树。这就是他们真正的意义所在。

但是，当您考虑用例时，会出现一些其他用例：

• 如果桶数低于 L，桶必须消失（不要担心项目）
• 如果存储桶计数达到 H，则必须创建一个新存储桶，因为该存储桶已满

我还没有弄清楚如何有效地编辑 Fenwick 树：删除/添加节点而不重建整个树...

当然，我们可以设置 L = 0，这样删除就变得不必要了，但是添加项目并不能真正避免。

所以这是一个问题：

您是否知道该索引的更好结构或如何更新 Fenwick 树？

主要关注的是效率，因为我确实计划实现它缓存/内存考虑值得担心。

背景：

我正在尝试提出一种类似于 B-Trees 和 Ranked Skip Lists 但具有本地化索引的结构。这两种结构的问题是索引是沿着数据保存的，这在缓存方面效率低下（即您需要从内存中获取多个页面）。数据库实现表明，将索引与实际数据隔离开来对缓存更友好，因此效率更高。

有谁知道在哪里可以找到 B+Tree 磁盘实现？我前后浏览了谷歌，不幸的是我找不到任何明智的东西。其他线程建议可能从 sqlite、sqljet 或 bdb 中获取树，但这些树嵌套在整个数据库中，您不能真正“仅仅”过滤掉 B+Tree。我真的只是在寻找磁盘上的 B+Tree ......周围没有任何花哨的东西。

我一直在slady.net上玩非常酷的 btree 小程序。我无法理解特定行为。看一下这个起始状态：

替代文字 http://www.freeimagehosting.net/uploads/db2931c7da.jpg

通过插入以下序列达到此特定状态：10、15、30、16、70、1、9、27、45、50、55。

我的问题是当我在序列中插入下一个值 65 时 [45, ] 节点会发生什么。

替代文字 http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

[55,70] 节点将被 65 分割，作为中间值，65 将向上移动，然后也分割 [30,50] 节点。我的问题是：为什么 [45, ] 节点最终成为 [30, ] 节点的子节点？它的 parent 最初有 3 个孩子，最左边和最右边成为新的单独节点。45 介于这些值之间，似乎它也可以在 [65, ] 节点下结束......为什么？

我将在索引之前和压缩方法之后存储数 TB 的信息。

我应该使用排序文件等手动编写二叉树数据库，还是使用 MongoDB 甚至 MySQL 之类的东西？

我担心每条记录的（空间）成本，比如 MySQL 和其他数据库。我也知道有些数据库甚至允许压缩，但它们转换为只读表。这些表/记录需要经常被新数据访问和覆盖。我想如果我用 C++ 编写一些东西，我就能将每条记录的空间成本降到最低。

我该怎么办？

如果我有一组排序的数据，我想以一种最适合顺序读取和随机查找的方式存储在磁盘上，那么 B 树（或其中一个变体是一个不错的选择。 .. 假设这个数据集并不都适合 RAM）。

问题是可以在不进行任何页面拆分的情况下从一组排序的数据构建完整的 B-Tree 吗？以便排序后的数据可以顺序写入磁盘。

我需要为大学实施 B 树：

我有一个“外部”类 B-Tree，其属性为root和 _degree。表示节点的类被实现为静态成员类：

所以，现在我的问题是：当我将 Node 类实现为静态成员类时，我无法访问外部类的 degree 属性。

现在我必须选择：

1. 使 Node 类成为内部类（非静态成员类）或
2. 为 Node 类创建一个构造函数，并在每次我需要构造 Node 时传入度数。

什么是最好的选择？将其设为内部类意味着节点都将引用 Btree（外部类），但将其设为静态成员类意味着我每次都必须通过学位。

我正在尝试根据“算法简介”中的“B-Trees”一章来实现 B-Tree。

我不太明白的是“最低学位”。在书中指出，度数是一个数字，表示节点可以持有的键数的下限/上限。它进一步说：

1. 每个非根节点至少存储t - 1key 并且有tchildren。
2. 每个节点最多存储2*t - 1key 并且有2*tchildren。

所以你得到 t = 2：

1. t - 1= 1 个键和 t = 2 个孩子
2. 2*t - 1= 3 把钥匙和 4 个孩子

对于 t = 3

1. t - 1= 2 个键和 t = 3 个孩子
2. 2*t - 1= 5 把钥匙和 6 个孩子

现在问题来了：似乎 B-Tree 中的节点在它们已满时只能存储奇数个键。

为什么不能有一个节点，比如说最多 4 个键和 5 个子节点？它与拆分节点有关吗？

我想使用 b-tree 作为索引，但我想不出 OR 查询的解决方案。

对于 OR 查询，我的意思是 select * from table where id between 1 and 5 OR id between 10 and 15;

如果我使用 id 作为 b-tree 中的键，那么如何在 b-tree 上进行上述查询？

通过b-tree搜索时，假设小于6和大于6的key在不同的子树上，而不是搜索路径经过包含小于6的key的子树时，id 1 到 5 之间的可以检索，但是 10 到 15 之间的 id 呢？

我是否必须使用 b+tree，当我找到指向 id 1 的键时，我只是一个接一个地扫描叶子节点，直到找到指向 id 15 的键？这种查询是不好的解决方案：select * from table where id between 1 and 5 OR id between 10000000 and 10000005???

或者有没有其他解决方案？

非常感谢！

c#（开源）中是否有任何基于文件系统的 B+ 树实现。我找到了一些项目，但这些不是基于文件（磁盘）的实现。我专门寻找基于文件系统的 B+ 树。

POSIX 二叉树函数的手册页包括以下语句：

tdelete()返回指向已删除项的父项的指针，或者NULL如果未找到该项。

tdelete()释放树中节点所需的内存。用户负责为相应数据释放内存。

这意味着无法通过tdelete()调用访问给定键的节点数据。将需要调用tfind()（而不是tsearch()不添加给定键），执行节点数据的销毁，然后tdelete()使用相同的键调用以从二叉树中删除节点。

我是否正确解释了这一点？有没有办法解决我认为这种方法的局限性？

1. 如果键是堆分配的，则在删除节点之前不能释放它（或使其对正在使用的比较函数无用）。这需要调用tfind()以获取指向数据的指针，tdelete()删除节点，然后销毁从tfind()调用中检索到的数据。
2. 需要两次查找来删除一个节点并销毁它的封闭数据。