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