algorithm - 如何将重复的键插入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...}