问题标签 [b-tree]

我正在寻找用 C 编写的 B 树库的精益且构建良好的开源实现。它需要在非 GPL 许可下才能用于商业应用程序。理想情况下，该库支持将 B-tree 索引存储/操作为磁盘文件，以便可以使用可配置（即：最小）RAM 占用空间构建大型树。

注意：由于似乎有些混淆，二叉树和 B-Tree不是一回事。

想象一下，您每天都会收到一位作者的新书。这本书正在进行中。他没有告诉你他改变或增加了什么。

您的工作是识别更改和添加内容，并仅将它们传递给出版商（他们没有时间每天阅读整本书）

出于这个问题的目的，这本书由 1m 行的 ascii 文本组成，并且还在不断增长（实际上是一个 MySQL 备份文件）。

我目前的想法是对每行（1k 个字符）进行安全哈希（例如 SHA256）并将其存储在 HD 上。由于散列只有 32 字节，因此文件只有 32MB。

然后当我们明天得到下一个文件时，我们逐行检查它，为每一行创建一个新的散列，并将其与前一天的散列进行比较。

当该过程完成后，我们会覆盖为第二天准备的哈希文件。

比较使用字符串比较（ > < 操作数）的二进制搜索方法，这将返回平均四次迭代的结果。

我还没有编写 btree 索引解决方案，但你将如何解决这个问题？

阅读了有关此主题的一些内容：

缓存 MySQL 查询

http://www.danga.com/memcached/

我的 SQL 缓存问题： http ://www.petefreitag.com/item/390.cfm

http://framework.zend.com/manual/en/zend.cache.html#zend.cache.introduction

我有一组非常独特（狭窄）的查询，我认为我可以在我当前的 FastCGI C API 可执行文件（不是 PHP）中很容易地实现一些缓存。

Zend 将他们的框架描述为：缓存记录通过一个灵活的 ID 和标签系统通过后端适配器（文件、Sqlite、Memcache...）进行存储。

这是如何实施的？

由于如果表已更改，相同的查询可能会返回不同的结果，因此我不仅需要监视查询，还需要监视 UPDATE、INSERT 和 DELETE（现在是 MySQL）因为这只发生在我的一个进程中，我可以轻松地添加一个表更改时删除缓存的语句。

客户端只允许 SELECT，在这种情况下，我可以对查询进行哈希处理并将它们与指向包含结果的文件的指针一起存储在哈希表或 btree 索引中。

有没有更好的办法？

假设我有一个基于文件的数据结构，例如 B+ 树。我的理解是，数据预计存储在磁盘上，但索引通常加载在内存中。如果你有一个如此大的文件，甚至它的索引也不适合内存怎么办？这通常是如何处理的？其次，由于索引是一棵树，而不是一组线性数据，它通常如何在磁盘上布局？

我基本上很好奇它是如何在现实世界的项目中完成的（比如 Berkeley DB）。显然，我对广泛的笔触感兴趣。我希望得到一个想法，所以当我深入研究我的数据库书的 B-Tree 部分时，我有一些背景信息（或者从几年前的 CS XYZ 中回忆起我的记忆）

我最近一直在优化我的 Postgres 数据库，而传统上，我只使用过 B-Tree 索引。但是，我在 Postgres 8.3 文档中看到 GiST 索引支持非唯一的多列索引。

但是，我看不出它们之间的实际区别是什么。我希望我的程序员同事能够解释它们之间的优缺点，更重要的是，为什么我会使用其中一个而不是另一个？

我想在磁盘文件中保存一个 Btree（不确定是二进制的）。然后将其读入内存。一些级别顺序遍历可能是二叉 Btree 的好方法。但如果它不是二进制的。我在内存中建立了从叶子节点到根节点的 Btree。我相信我必须在磁盘文件中定义一些结构并输出树节点。使用一些额外的标签来识别文件中的节点？如何遍历可能是这里的关键问题。我想不出保存节点和指针的好方法。然后阅读它。在内存中重新构造树。有什么好主意吗？多谢。

这是一个简单的问题：在 Java 中是否有用于绘制B-tree的 API？我只是不想花太多时间重新发明轮子。我对每个 si的算法没有问题，经过大量阅读（特别是 Lafore 的 Java 中的数据结构和算法）后，我的工作非常好，我只是不知道如何以一种好的方式打印 B-tree。

提前致谢。

当只需要功能时，我正在尝试决定使用哪种数据结构来存储键值对

• 插入
• 抬头

具体来说，我不需要能够删除对或遍历键/值/对。

键是整数元组，值是指针（引用等）。我只存储了几百万对，分布在（许多）对象上。

目前我正在考虑使用

• 哈希表
• kd树
• b树

我倾向于哈希表（对于O(1)插入/查找时间），但我想确认我的倾向。

您会推荐哪种结构（上述结构或其他结构），为什么？如果您推荐一个哈希表，我应该为每个对象创建一个单独的表，还是只创建一个表并将对象的 id 作为键元组的一部分？

任何人都知道 Javascript 中简单 BTree 实现的任何好的例子吗？我有一堆“东西”随机到达，并希望有效地插入每一个。

最终，每个新的都将根据它在树中的最终位置插入到 DOM 中。

我可以从头开始编写代码，但不想重新发明任何轮子。

谢谢

作为程序员，我什么时候应该考虑使用 RB 树、B-树或 AVL 树？在决定选择之前需要考虑哪些关键点？

有人可以为每个树结构解释一个场景，为什么参考关键点选择它而不是其他树结构？