B-树/ B+Trees和重复键

Question

我正在研究为我的应用程序组合一个自定义存储方案的可能性。我认为，重新发明轮子的努力是值得的，因为性能和存储效率都是主要目标，而且它上的数据和操作比RDBMS提供的所有东西(无更新、无删除、预定义的查询集)都要简单得多。

我只使用了一小部分我找到的关于B树和B+树的网络资源-维基百科，http://www.bluerwhite.org/btree/，http://slady.net/java/bt/view.php，http://www.brpreiss.com/books/opus6/html/page342.html (最后一个是最有价值的)。

重复的键

我试图解决的第一个问题是如何处理重复的键--这棵树将充当一个DB索引，例如，不会只有一个‘东西’带有'color=red'，所以在这个树中查找'red‘应该会产生很多结果。

到目前为止，我已经想出了两个解决方案。第一种方法是在树中简单地为每种方法创建多个条目。但是当树上有100,000或100,000,000个“红色”的东西时..对于树形结构来说，这是非常有效的吗？第二种方法是每个键只有一个条目，但与每个键关联的“有效负载”指向不同的数据块，这是一个指向所有“红色”项实例的链表。

有没有通用的/更好的选择？

B+Tree节点更改类型

我想验证一下我所做的假设。假设你有一个高度为2的B+-树--2级的外部(叶)节点保存“实际数据”。那么插入就需要对叶节点进行拆分--叶节点不再持有“实际数据”。从实现的角度来说，因为数据可能有很大的大小，所以你可以存储一种“指针”作为“实际数据”--所以如果一个叶子节点变成了一个分支节点，那么(相同大小的)指针就会被更新为指向新的子树，这样的想法是正确的吗？

我的意思是，内部节点和外部节点的大小应该是一样的，因为外部节点可能会变成内部节点，而打乱数据不是一个好主意吗？

(因为我是在C#中从头开始实现的，所以添加了C#标记。)

Answer 1

试图回答我自己的问题..我也欢迎其他的答案。

重复的密钥

如果可能出现相同键的重复条目，则树将存储对具有给定键的项的列表(存储器)或链接表(盘)的引用。

B+Tree节点，更改类型

在内存中，我的节点有一个object引用，在内部/分支节点的情况下可以指向另一个节点(本身就是另一个有效的B+Tree)，或者在外部/叶节点的情况下直接指向数据。在磁盘上，这将以非常相似的方式工作:每个“链接槽”的64位值，就像我选择给它们命名的那样-如果指向子节点，则为文件中的偏移量；如果直接指向数据，则为块编号(或者在问题第一部分提到的情况下，为链表的头部)。

Answer 2

Kieren，我相信你现在已经知道B+树是通过向上拆分来生长的，所以叶节点总是叶节点，内部节点总是内部节点。最后，您必须拆分根节点，将其转换为两个内部节点，然后定义一个新的根节点。因此，要回答问题的第二部分，您不需要更改节点类型。

关于问题的第一部分，当您从数据库中删除数据记录时，您将需要找到指向该特定记录的所有键，并删除它们。如果你必须查看长长的线性列表来做到这一点，删除将会很慢。我假设您在节点中使用二进制搜索，以便快速找到正确的节点元素(键+指针)，因此，如果您使“节点搜索”机制包含请求特定键+指针组合的能力，则可以快速找到要删除的正确键元素。换句话说，使数据记录指针成为搜索的一部分(仅当搜索特定数据记录的关键字时)。这确实意味着重复的关键字将以“数据指针”的顺序存储在节点中，因此只要重复关键字的顺序不重要，这种机制就会起作用。

Answer 3

B+树的主要特性是最小化磁盘寻道。如果你只是“存储指针”，那么你失去了这个好处，你的代码将追逐文件指针，你将到处寻找磁盘头。你不能从磁盘读取100个字节，所有的读写都是在对齐的块中进行的。

叶父节点:数据总是在叶中，每个叶只有一个关键字在节点中(它们是叶的直接父节点)。该节点允许您通过查看该叶中的第一个键的副本来“窥视”该叶的内容。

节点父级:子节点中第一个键之前的键在节点的父级中。

数据的重复并不坏。例如，如果每个叶有207条记录，每个节点有268条记录，那么您将为每207条记录存储一个额外的键。如果有超过207*269个叶子，则每207*269条记录需要多一个键。

您似乎混淆了B-树和B+树。B+树总是将数据放在叶子中，而节点中永远不会有任何数据。节点中只存在每个子级的最低键的样本。数据永远不会在B+树中“上移”，每个子节点只有一个最低键的拷贝会向上传播。

开销以对数增长。最小的复制节省了大量的查找。

(真的)复制密钥

为了处理B+树中的重复键，就像在具有相同值的多个行中一样，实现通常通过向表附加一个额外的隐藏列，并在创建记录时为其分配一个自动递增的值来强制它是唯一的。隐藏列被添加到索引键的末尾，这保证了它始终是唯一的。索引以索引列开始，因此排序将按指定的顺序进行，但附加的隐藏值可保证唯一性。

如果表已经有一个主键，那么它可以使用主键来强制唯一性，而不是添加隐藏列。