B 树/B+树和重复键
我正在研究为我的应用程序组合自定义存储方案的可能性。我认为，重新发明轮子的努力是值得的，因为性能和存储效率都是主要目标，并且其上的数据和操作比 RDBMS 提供的所有内容简单得多（没有更新、没有删除、预定义的查询集） ）。
我只使用了我发现的有关 B 树和 B+ 树的一小部分网络资源 - 维基百科，http://www .bluerwhite.org/btree/，http://slady.net/java/bt/view.php< /a>,http://www.brpreiss.com/books/opus6/html/page342.html（最后一个一个是最有价值的）。
重复键
我试图解决的第一个问题是如何处理重复键 - 这棵树将充当数据库索引，例如，不会只有一个带有“color=red”的“东西”，所以看起来在这棵树上“红色”应该会产生很多结果。
到目前为止我想出了两种解决方案。第一个是在树中为每个条目都有多个条目。但是，当树中有 100,000 或 1,000,000 个“红色”事物时……这对于树结构来说非常有效吗？第二种是每个键只有一个条目，但与每个键关联的“有效负载”指向不同的数据块，该数据块是指向“红色”项目的所有实例的链接列表。
有通用/更好的选择吗？
B+Tree 节点改变类型
我想检查我所做的假设。假设您有一个 B+ 树，高度为 2 - 第 2 层的外部（叶）节点保存“实际数据”。然后，插入需要分割叶节点 - 叶节点不再保存“实际数据”。我的想法是否正确，在实现方面，因为数据可能很大，所以您会存储一种“指针”作为“实际数据” - 因此，如果叶节点成为分支节点，则该指针（相同的大小）而是更新为指向新的子树？
我的意思是，内部和外部节点，它们实际上应该具有相同的大小，因为外部节点可能会变成内部节点，并且重新整理数据不是一个好主意吗？
（添加了 C# 标签，因为我是在 C# 中从头开始实现的。）
I'm investigating the possibility of putting together a custom storage scheme for my application. It's worth the effort of potentially reinventing the wheel, I think, because both performance and storage efficiency are a main objective and the data and operations on it are far simpler than everything provided by an RDBMS (no updates, no deletes, predefined set of queries).
I'm using just a small handful of web resources I've found about B-Trees and B+-Trees - Wikipedia, http://www.bluerwhite.org/btree/, http://slady.net/java/bt/view.php, http://www.brpreiss.com/books/opus6/html/page342.html (the last one is the most valuable).
Duplicate keys
The first problem I'm trying to solve is how to deal with duplicate keys - this tree will be acting as a DB index and for example there won't just be one 'thing' with 'color=red', so looking up 'red' in this tree should yield many results.
There are two solutions I have come up with so far. The first is simply having multiple entries in the tree for each of these. But when there are 100,000 or 1,000,000 'red' things in the tree.. is that very efficient for a tree structure? The second was to have just one entry for each key, but the 'payload' associated with each key points to a different block of data, which is a linked list pointing to all instances of items that are 'red'.
Is there a common / better option?
B+Tree nodes changing types
I wanted to check an assumption I'm making. Say you have a B+-Tree, height 2 - the external (leaf) nodes at level 2 hold 'actual data'. Then an insertion necessitates a split of a leaf node - the leaf node no longer holds 'actual data'. Am I right in thinking that in implementation terms because the data might be of a substantial size that you would instead store a kind of 'pointer' as the 'actual data' - so if a leaf node becomes a branch node, that pointer (of the same size) is instead updated to point to the new subtree?
By that I mean, internal and external nodes, they should be the same size really since external nodes might become internal ones, and shuffling data around isn't a good idea?
(Added the C# tag since I'm implementing this from scratch in C#.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
Kieren，我相信您现在已经明白 B+ 树是通过向上分裂来生长的，因此叶节点始终是叶节点，内部节点始终是内部节点。最终，您必须拆分根节点，这会将其变成两个内部节点，并定义一个新的根。因此，要回答问题的第二部分，您不需要更改节点类型。
关于问题的第一部分，当您从数据库中删除数据记录时，您将需要找到指向该特定记录的所有键，并将其删除。如果您必须查看很长的线性列表才能做到这一点，那么删除速度会很慢。我假设您在节点内使用二分搜索，以便快速找到正确的节点元素（键+指针），因此，如果您使“节点搜索”机制包括请求特定键+指针组合的能力，您可以快速找到要删除的正确关键元素。换句话说，使数据记录指针成为搜索的一部分（仅当搜索特定数据记录的键时）。这确实意味着重复键将以“数据指针”顺序存储在节点中，因此只要重复键的顺序不重要，这种机制就可以工作。
Kieren, I'm sure you figured out by now that B+ trees grow by splitting upwards, so that a leaf node is always a leaf node, and internal nodes are always internal nodes. Eventually, you must split the root node, which turns that into two internals, and you define a new root. So to answer the second part of your question, you don't change node types.
Regarding the first part of your question, when you delete a data record from the DB, you will need to find all the keys that point to that particular record, and remove them. If you have to look through long linear lists to do that, deleting will be slow. I am assuming you are using a binary search within a node in order to quickly find the correct node element (key + pointer), so if you make that "node searching" mechanism include the ability to ask for a particular key + pointer combination, you can quickly find the correct key element to remove. In other words, make the data record pointer part of the search (only when searching for a particular data record's key). This does mean that the duplicate keys will be stored in the nodes in "data pointer" order, so as long as ordering of the duplicate keys is not important, this mechanism will work.
试图回答我自己的问题..我也欢迎其他答案。
重复键
如果可能存在相同键的重复条目，则树将存储对具有给定键的项目的列表（内存）或链接列表（磁盘）的引用。
B+Tree 节点，更改类型
在内存中，我的节点有一个
object引用，在内部/分支节点的情况下，它可以指向另一个节点（本身是另一个有效的 B+Tree），或者在外部/叶节点的情况下直接数据。在磁盘上，这将以非常相似的方式工作：每个“链接槽”都有一个 64 位值，正如我选择的那样命名它们 - 要么是文件中的偏移量（如果指向子节点），要么是块号如果直接指向数据（或者在问题第一部分提到的情况下指向链表的头）。Attempting to answer my own question.. I would welcome other answers too.
Duplicate Keys
The tree will store a reference to a list (memory) or linked-list (disk) of items with the given key, if duplicate entries for the same key is a possibility.
B+Tree nodes, changing types
In-memory, my nodes have an
objectreference, which can point to another node (in itself another valid B+Tree) in the case of an internal/branch node, or indeed data directly in the case of an external/leaf node. On disk, this would work in a very similar way: a 64-bit value for each 'link slot', as I have chosen to name them - either an offset in the file if pointing at a sub-node, or a block number if pointing to data directly (or the head of a linked-list in the case mentioned in the first part of the question).B+树的主要特点是最小化磁盘寻道。如果你只是“存储指针”，那么你就失去了这个好处，你的代码将追逐文件指针，并且你将到处寻找磁盘头。您无法从磁盘读取一百个字节，所有读取和写入都在对齐的块中。
叶子父节点：数据始终位于叶子中，每个叶子中只有一个键位于节点（叶子的直接父节点）中。该节点允许您通过查看该叶子中位于节点中的第一个键的副本来“窥视”叶子的内容。
父节点：子节点中第一个键之前的键位于该节点的父节点中。
数据的重复还不错。例如，如果每个叶子有 207 条记录，每个节点有 268 条记录，那么您将为每 207 条记录存储一个额外的键。如果您的叶数超过 207*269，则每 207*269 记录还需要一个密钥。
您似乎混淆了 B 树和 B+ 树。 B+树的叶子中总是有数据，而节点中从来没有任何数据。节点中仅存在每个子节点的最低键样本。数据永远不会在 B+ 树中“向上移动”，只会向上传播每个子节点的一个最低键的副本。
开销呈对数增长。最少的重复可以节省大量的搜索次数。
（确实）重复键
为了处理 B+ 树中的重复键（如具有相同值的多行中的重复键），实现通常通过向表附加一个额外的隐藏列来强制其唯一，并在以下情况下为其分配一个自动递增值：创建一条记录。隐藏列被添加到索引键的末尾，这保证了它始终是唯一的。索引从索引列开始，因此排序将按照指定进行，但附加的隐藏值保证唯一性。
如果表已经有主键，那么它可以只使用它来强制唯一性，而不是添加隐藏列。
The main feature of B+ trees is minimizing disk seeks. If you just "store pointers" then you defeat that benefit, and your code will be chasing file pointers, and you will be seeking the disk head all over the place. You can't read a hundred bytes from disk, all reads and writes are in aligned blocks.
Leaf parents: data are always in a leaf, and just one key per leaf are in the nodes (that are immediate parents of the leaves). The node lets you "peek" at the leaf's contents by looking at a copy of the first key in that leaf, right there in the node.
Node parents: The key before the first key in the child node is in the node's parent.
The duplication of data is not bad. For example, if there are 207 records per leaf, and there are 268 records per node, then you will store one extra key for every 207 records. If you have more than 207*269 leaves, then you need one more key per 207*269 records.
You seem to be confusing B-trees and B+ trees. B+ trees always have the data in the leaves, and there is never any data in nodes. Only a sample of the lowest key per child is present in a node. Data never "moves up" a B+ tree, only copies of one lowest key per child are propagated upward.
The overhead grows logarithmically. The minimal duplication saves a lot of seeks.
(Really) Duplicate keys
To handle duplicate keys in a B+ tree, as in multiple rows that have the same value, implementations typically force it to be unique by appending an additional hidden column to the table, and assigning it an auto-incrementing value when a record is created. The hidden column is added to the end of the indexed key, which guarantees that it will always be unique. The index starts with the indexed column(s) so the ordering will be as specified, but the appended hidden value guarantees uniqueness.
If the table already has a primary key, then it could just use that to enforce uniqueness instead of adding a hidden column.
当您处理重复的键时，您总是会碰到包含您搜索的给定键的叶子。
由于叶子将所有键组合在一起，因此您只需将叶子向左移动（位置 -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]
我倾向于使用第一个解决方案，因为它也适用于多叶重复中间的叶子。
When you deal with duplicate keys you always hit a leaf containing the given key you searched for.
Since a leaf groups all keys together you just need to walk the leaf to the left (position -1) to find the first entry with the given key. If you find the first key of the leaf, you need to inspect the previous leafs.
Since there is no possible assumption about the leaf you will hit for a duplicated key, you need to walk all previous leafs until you find a leaf which first key is not the key you search. If the last key of that leaf is not the key you search for (<) than its the next leaf otherwise this leaf.
The search over the leafs is linear inside the leaf you have log n to find the first key entry.
If you can sort the key entries in the leaf by the data they hold you can easily find the leaf to find a certain entry (which is great for contains and remove operations).
for a high chance of duplicates it is best to look for an other storage model by storing key -> datas. Especially if the data does not change often.
[Update]
There is a chance of forgetting a key:
Node N [L1 |3| L2]
Leaf L1 [1,2,3] -> L2 [ 3, 4, 5]
You remove the 3 in L2 you result in.
Node N [L1 |3| L2]
Leaf L1 [1,2,3] -> L2 [ 4, 5]
When you now search you find that 3 is not in L2. You might now look in the previous leaf to find the 3.
Another way is to update the key to the actual first key of the leaf, resulting in (resulting in potential update propagation):
Node N [L1 |4| L2]
Leaf L1 [1,2,3] -> L2 [ 4, 5]
Or you borrow from the left leaf the element.
Node N [L1 |3| L2]
Leaf L1 [1,2] -> L2 [3, 4, 5]
I tend to use the first solution since it works also for leafs in the middle of multi leaf duplicates.