问题标签 [b-tree]

我正在做一个有趣的项目，我需要一个使用 B+Trees 的简单键/值存储。几年前我研究过它们，老实说，我不想重新发明轮子，所以我正在寻找一个简单的 b+tree 的 C 实现，我可以将它包含在我的项目中。

我知道 sqlite、dbm 和 tokyocabinet 的，但它们对于我的需求来说有点过于“复杂”。有什么（甚至是教学方面的）工作可以推荐给我吗？你有一些代码要分享吗？

非常感谢！

可能重复：
btree 实现中的分段错误

我们如何在下面的代码中找到 B-tree 中的层数

我相信我了解 INNODB 如何构建表（通过使用聚集 btree 索引=PK 和包含行本身的叶子）。二级索引使用相同的原则（btree clustered index=secondary index），叶子包含用作指针的PK（这就是可能需要二级索引查找的原因）。

http://www.chenyajun.com/wp-content/uploads/2008/12/3-9.jpg 所以排序是基于INNODB中的索引。

但是我真的无法理解如何使用聚类 btree 索引原理对 INNODB 中的覆盖/复合索引进行物理排序和存储。

我们开发了一个双时态模式和一个 perl 库，负责在双时态形式上制作宫内节育器。所有数据都在 SQL Server 2008 中，整个系统总是忙于太多的读取器和写入器（以双时态形式写入）。

由于 SQL Server 的内部索引是基于 B+ 树的，它会扩展/不会导致死锁吗？

在我们添加了更好的索引、明智地添加了NOLOCK、ROWLOCK之后，我们过去在非双时态系统中发生了很多死锁，现在这种死锁并不经常发生。

在双时态形式中，所有读取器和写入器主要运行范围查询。考虑到内部索引是 B+ 树，我们认为这将增加死锁问题。空间索引不应该在这里证明更好吗？

我的假设正确吗？有任何想法吗 ？

我知道如何在内存中实现 btree，但不清楚如何将 btree 存储在磁盘中。我认为有两个主要区别：

1. 内存指针和磁盘地址之间的转换，见这篇文章。
2. 插入新的 k/v 项目时如何拆分页面？在内存中实现非常容易。

谢谢

我正在使用 rails 并且有以下场景：用户有多个列表，每个列表包含许多单词，每个单词都有自己的定义。列表显示视图显示以 30 的倍数分页的所有单词。我担心 b/ca 列表可能会增长到超过 4,000 个单词，如果需要订购列表，这似乎对数据库进行分页会很昂贵按字母顺序。我想知道最快的方法是什么。也许在单词上添加索引？

我考虑在列表中保存一个字符串，其中包含列表中由空格分隔的所有单词。然后我可以在这个字符串上做一个 split(" ") 并在这个数组上使用分页，但是我需要使用正则表达式来添加和删除这个列表中的单词以及一个单词对象保存。

我还考虑过某种键值对存储，例如东京内阁。看起来 B-Tree 索引可以工作。

我的任务是从数据库中删除操作期间未受影响的所有实体。我创建了一个单独的表，它有两列，第一个是表名，第二个是该表中记录的 id。

例如，如果我有桌子

和其中的记录

如果我编辑这条记录，我会将以下数据放入edited_entities：

然后我需要删除所有未受影响的实体（其中 id 不在edited_entities 表中）并且我执行以下操作：

我想知道这种操作（MySql）的最佳引擎是什么？默认的数据库引擎是 InnoDB。我考虑过内存（堆），但我不确定它是否可以加快删除操作。

如果您有建议如何优化所需的操作，我将很高兴在这里。

我不想在小狗表中添加额外的列。

我正在尝试实现 3-4-5-6 树。如果合并导致根只有一个键（下溢），并且其子项的键总数大于 5（所以如果全部合并在一起，就会发生下溢），会发生什么？

我已经探索了T-tree和 B-/B+ 树的定义。从网络上的论文中，我了解到 B 树在分层内存中表现更好，例如磁盘驱动器和缓存内存。

我无法理解的是为什么 T-trees 甚至被用于平面内存？

它们被宣传为 AVL 树的节省空间的替代品。

在最坏的情况下，T 树的所有叶节点只包含一个元素，所有内部节点都包含允许的最小数量，接近满。这意味着平均只使用了一半的分配空间。除非我弄错了，否则这与 B 树的最坏情况相同，即 B 树的节点是半满的。

假设两棵树都将键本地存储在节点中，但使用指针来引用记录，唯一的区别是 B 树必须为每个分支存储指针。这通常会导致高达 50% 或更少的开销（在 T-tree 上），具体取决于键的大小。事实上，这接近于 AVL 树中预期的开销，假设没有父指针、嵌入在节点中的记录、嵌入在记录中的键。这是阻止我们使用 B-trees 的预期效率增益吗？

T 树通常在 AVL 树之上实现。AVL 树比 B 树更平衡。这可以与T-trees的应用联系起来吗？

我有一个使用 B+Tree 根据 key1 排序的 touples {key1, key2} 列表。此结构位于辅助存储器 (HDD) 中。我想实现一个算法，它需要在 key1 上排序的列表，但也需要使用 key2 随机访问列表。我不需要算法的整个列表，我会根据需要从磁盘中获取块，因此 B+Tree 可以很好地处理所有发生的插入和删除。

我已经苦苦挣扎了一周，我认为唯一的方法是使用第二个结构（例如第二个 B-Tree）和 key2，但这会使更新树所需的空间和时间加倍。

我对哈希表了解不多，但我认为我不能用这些将键映射到某个值，对吧？

您对可以为我提供对 key2 的随机访问而不会使数据加倍的结构有任何想法吗？

或者，我可以使用不需要随机访问的替代算法，但我想将其作为最后的解决方案。

提前致谢