如何将重复的键插入b树中

Question

请回答 b 树而不是 b+ 树。我有 2 个问题。

1. 当你向 ab 树插入重复的键时会发生什么？对于以下输入，t=3 的 b 树会是什么样子？1,1,1,1,1,1,1,1,1,1,1,1,1,1

2. ab树中t=3的父节点可以是这样的吗？1,1,4,10？如果是这样，键“1”和第二个键“1”之间的儿子是否只包含值“1”？

Answer 1

就像哈希表一样，树中的每个节点都应该存储与该键关联的项目列表的链接。您将在树中存储唯一的键，但链接将指向可能包含多个项目的列表：

[node, key=1, ptr=l], l={1,1,1,1,1,1,1...}