B+树和二级索引

Question

我想知道使用二级索引的B+树是如何工作的？使用二级索引，树的叶节点中可以有重复的值。当插入发生时，树如何知道除了记录之外的位置，如果它们是它正在插入的字段的重复值？

Answer 1

这个article建议了一种很好的方法来处理B+树中的重复键。在B+树中，您只将指向数据的键和指针保存在叶节点中，并且它们可能是重复的。例如，7 7 7。为了找到它们，你还在内部节点中保留了一个键7(如下所示)，右指针引用具有>= 7的键的块，即使用这3个键的块。

现在，在插入时，可能会出现新的重复键不适合节点的情况，为了平衡树，必须重新组织。但是代价很高，所以作者建议添加一个溢出块，并将其链接到包含重复键的溢出块。

------------
| 5 | 7 |  |
V---V---V---
        ---------    ---------
        |7  7  7| -> |7      |
        ---------    ---------