B-树/ B+树和重复键
本文关键字： | 更新日期: 2023-09-27 18:04:25
我正在研究为我的应用程序组合一个自定义存储方案的可能性。我认为，重新发明轮子的努力是值得的，因为性能和存储效率都是一个主要目标，它的数据和操作比RDBMS提供的一切都要简单得多(没有更新，没有删除，预定义的查询集)。
我只使用了我找到的关于B树和B+树的一小部分网络资源——维基百科，http://www.bluerwhite.org/btree/， http://slady.net/java/bt/view.php, http://www.brpreiss.com/books/opus6/html/page342.html(最后一个是最有价值的)。
复制键我要解决的第一个问题是如何处理重复的键-这棵树将作为一个数据库索引，例如，不会有一个'东西'与'color=red'，所以查找'红色'在这棵树应该产生许多结果。
到目前为止，我已经想出了两个解决方案。第一种方法是在树中对每个元素都有多个条目。但是当树中有100,000或1,000,000个"红色"的东西时……这对树形结构来说是很有效的吗?第二种方法是每个键只有一个条目，但与每个键相关联的"有效载荷"指向不同的数据块，这是一个指向所有"红色"项实例的链表。是否有一个共同的/更好的选择?
B+树节点改变类型
我想检查我做的一个假设。假设你有一个B+树，高度为2 -外部(叶)节点在第2层保存"实际数据"。然后插入需要对叶节点进行拆分——叶节点不再保存"实际数据"。我认为在实现方面，因为数据可能是一个相当大的大小，你会存储一种"指针"作为"实际数据"-所以如果一个叶子节点成为一个分支节点，指针(相同的大小)被更新为指向新的子树?
我的意思是，内部节点和外部节点，它们应该是相同的大小，因为外部节点可能会变成内部节点，打乱数据不是一个好主意?
(添加了c#标签，因为我是在c#中从头开始实现的。)
Kieren，我相信你现在已经知道B+树是通过向上分裂生长的，所以叶子节点总是叶子节点，内部节点总是内部节点。最后，必须拆分根节点，这将把它变成两个内部节点，并定义一个新的根。所以要回答你问题的第二部分，你不需要改变节点类型。
关于你问题的第一部分，当你从DB中删除一个数据记录时，你需要找到指向该特定记录的所有键，并删除它们。如果你必须遍历很长的线性列表，那么删除将会很慢。我假设您在节点内使用二进制搜索以快速找到正确的节点元素(键+指针)，因此，如果您使"节点搜索"机制包括请求特定键+指针组合的能力，则可以快速找到要删除的正确键元素。换句话说，使数据记录指针成为搜索的一部分(仅在搜索特定数据记录的键时)。这确实意味着重复键将以"数据指针"顺序存储在节点中，因此只要重复键的顺序不重要，这种机制就可以工作。
试图回答我自己的问题…我也欢迎其他的答案。
复制键如果可能存在相同键的重复条目，树将存储对具有给定键的项的列表(内存)或链表(磁盘)的引用。
B+树节点，改变类型
在内存中，我的节点有一个object引用，在内部/分支节点的情况下，它可以指向另一个节点(本身是另一个有效的B+树)，或者在外部/叶子节点的情况下直接指向数据。在磁盘上，这将以非常相似的方式工作:每个"链接槽"的64位值，因为我选择了命名它们-如果指向子节点，则文件中的偏移量，或者如果直接指向数据，则块号(或者在问题的第一部分提到的情况下，链表的头)。
B+树的主要特性是最小化磁盘查找。如果您只是"存储指针"，那么您就失去了这个好处，您的代码将会跟踪文件指针，并且您将到处寻找磁盘磁头。你不能从磁盘读取一百个字节，所有的读写都在对齐的块中。
叶父:数据总是在一个叶中，每个叶中只有一个键在节点中(这些节点是叶的直接父节点)。该节点允许您通过查看该节点中第一个键的副本来"窥视"叶节点的内容。
节点父节点:子节点中第一个键之前的键在节点的父节点中。
数据的重复并不坏。例如，如果每个叶子有207条记录，每个节点有268条记录，那么您将为每207条记录存储一个额外的键。如果您有超过207*269个叶子，那么每207*269条记录需要多一个键。
你似乎把B树和B+树搞混了。B+树总是在叶节点上有数据，而在节点上没有任何数据。每个子节点中只存在最低键的样本。数据永远不会在B+树中"上移"，每个子节点只有一个最低键的副本向上传播。
开销呈对数增长。最小的重复节省了大量的查找。
(真的)重复的钥匙
为了处理B+树中的重复键，例如在具有相同值的多行中，实现通常通过向表中添加额外的隐藏列并在创建记录时为其分配自动递增的值来强制它是唯一的。隐藏列被添加到索引键的末尾，这保证了它始终是唯一的。索引从被索引的列开始，因此排序将按照指定的顺序进行，但是附加的隐藏值保证唯一性。
如果表已经有一个主键，那么它可以使用它来强制唯一性，而不是添加一个隐藏列。
当您处理重复的键时，您总是击中包含您搜索的给定键的叶子。
由于叶子将所有键组合在一起，因此您只需要向左(位置-1)遍历叶子以找到具有给定键的第一个条目。如果你找到了叶子的第一个键，你需要检查前面的叶子。
因为没有可能的假设，你会遇到一个重复的键，你需要遍历所有以前的叶子，直到你找到一个叶子，第一个键不是你要搜索的键。如果该叶的最后一个键不是你要搜索的键(<)，那么它就是下一个叶，否则就是这个叶。
在叶节点上的搜索是线性的在叶节点中你需要log n才能找到第一个键项
如果你可以根据叶子中的数据对键项进行排序，你可以很容易地找到叶子来找到某个条目(这对于包含和删除操作很有用)。
对于重复的可能性很高的情况，最好通过存储key ->数据来寻找其他存储模型。尤其是在数据不经常变化的情况下。
(更新)有可能忘记钥匙:
节点N [L1 |3| L2]叶片L1 [1,2,3] -> L2 [3,4,5]
去掉L2中的3，得到
节点N [L1 |3| L2]叶片L1 [1,2,3] -> L2 [4,5]
当你现在搜索时，你发现3不在L2中。现在您可以在前一页中查找3.
另一种方法是将键更新为叶子的实际第一个键，导致(导致潜在的更新传播):节点N [L1 |4| L2]叶片L1 [1,2,3] -> L2 [4,5]
或者从左叶借用元素
节点N [L1 |3| L2]叶片L1 [1,2] -> L2 [3,4,5]
我倾向于使用第一种解决方案，因为它也适用于多叶副本中间的叶子。