如何将 kademlia 路由 table 表示为数据结构
How to represent a kademlia routing table as data structure
kademlia paper talks about the the organization of buckets, splitting, merging and finding the correct bucket to insert in abstract, and 项。
§2.2 讨论了一组固定的 160 个桶，每个桶覆盖键空间的一个固定子集。但后面的章节涉及额外的拆分和覆盖键空间不同部分的桶。这不太适合固定列表
组织存储桶的正确方法是什么？
Meta：由于混淆反映在许多问题中，部分信息分散在许多答案中，因此此问答旨在提供易于链接的澄清
混乱源于。
平面布局
这来自预印本，主要用于以理论方式概述 kademlia 的基本属性，并且仍然反映在完整版的 §2.2 和 §3 中。
许多现实世界的实现都实现了这种方法，但它们没有实现桶拆分、合并或 node multihoming。
它涉及将联系人放入与节点共享 i 个前缀位的第 i 个桶中。这意味着布局使用相对于节点自身 ID 的距离。
基于树的布局
这在 §2.4 部分中有描述。
实现改进，例如处理 described towards the end of §2.4 or deeper non-local splitting described in §4.2 one needs to associate each bucket with the keyspace range it covers, ，即起始 ID 和共享的前缀位数以屏蔽 ID 的尾部。
通过将前缀位的数量增加一位并将添加的位分别设置为两个新桶的0和1来执行拆分桶。
与平面布局不同，此结构不涉及相对于节点自身 ID 的距离，尽管一些决定是基于节点自身 ID 是否会落入桶中。
由于这种路由 table 中的桶数随时间变化，因此必须在可调整大小的数据结构中表示，§2.4 中提到了这一点。由于无法再通过固定索引进行访问，因为在检查前缀范围之前不知道将覆盖任何特定节点 ID 的确切存储桶，如果想要避免，则需要某种 O(log n) 搜索每次扫描整个遗愿清单。
按桶将覆盖的最低 ID 对桶进行排序是实现此目的的自然方法。可以使用 B 树或排序数组结合二进制搜索来实现此目的。
无论您采用哪种方法，都会使用与请求目标相匹配的正确联系人集 填充对 find_node 请求的响应，因为任何单个存储桶都可能不足以填充它，因此会出现多个需要遍历桶。扫描整个路由 table 以获得最佳可用候选回复可能更简单。
经过一些在线研究和 re-reading 论文几次后，我想我明白了。在论文的最终版本第 2 节（系统描述）的某处，它说：
The remainder of this section fills in the details and makes the lookup algorithm more concrete. We first define a precise notion of ID closeness, allowing us to speak of storing and looking up pairs on the k closest nodes to the key. We then give a lookup protocol that works even in cases where no node shares a unique prefix with a key or some of the subtrees associated with a given node are empty
定义 "a precise notion of ID closeness" 的部分在 2.1 小节中完成。所以这个 "allows" 我们在 2.2 和 2.3 小节中谈到 "storing and looking up pairs on the k closest nodes to the key" 并且我们将了解查找过程是如何工作的。 2.4 节现在将解决在没有节点与键共享唯一前缀（又名不平衡树）的情况下查找的问题，这里是实际完成的 "lookup protocol"。
因此，数组结构在开始时用作 dummy-strucuture，我们用它来理解查找过程，在了解查找过程的工作原理后，我们将介绍更高级的树结构。
这可能是作者的想法。
kademlia paper talks about the the organization of buckets, splitting, merging and finding the correct bucket to insert in abstract,
§2.2 讨论了一组固定的 160 个桶，每个桶覆盖键空间的一个固定子集。但后面的章节涉及额外的拆分和覆盖键空间不同部分的桶。这不太适合固定列表
组织存储桶的正确方法是什么？
Meta：由于混淆反映在许多问题中，部分信息分散在许多答案中，因此此问答旨在提供易于链接的澄清
混乱源于
平面布局
这来自预印本，主要用于以理论方式概述 kademlia 的基本属性，并且仍然反映在完整版的 §2.2 和 §3 中。
许多现实世界的实现都实现了这种方法，但它们没有实现桶拆分、合并或 node multihoming。
它涉及将联系人放入与节点共享 i 个前缀位的第 i 个桶中。这意味着布局使用相对于节点自身 ID 的距离。
基于树的布局
这在 §2.4 部分中有描述。
实现改进，例如处理
通过将前缀位的数量增加一位并将添加的位分别设置为两个新桶的0和1来执行拆分桶。
与平面布局不同，此结构不涉及相对于节点自身 ID 的距离，尽管一些决定是基于节点自身 ID 是否会落入桶中。
由于这种路由 table 中的桶数随时间变化，因此必须在可调整大小的数据结构中表示，§2.4 中提到了这一点。由于无法再通过固定索引进行访问，因为在检查前缀范围之前不知道将覆盖任何特定节点 ID 的确切存储桶，如果想要避免，则需要某种 O(log n) 搜索每次扫描整个遗愿清单。
按桶将覆盖的最低 ID 对桶进行排序是实现此目的的自然方法。可以使用 B 树或排序数组结合二进制搜索来实现此目的。
无论您采用哪种方法，都会使用与请求目标相匹配的正确联系人集 find_node 请求的响应，因为任何单个存储桶都可能不足以填充它，因此会出现多个需要遍历桶。扫描整个路由 table 以获得最佳可用候选回复可能更简单。
经过一些在线研究和 re-reading 论文几次后，我想我明白了。在论文的最终版本第 2 节（系统描述）的某处，它说：
The remainder of this section fills in the details and makes the lookup algorithm more concrete. We first define a precise notion of ID closeness, allowing us to speak of storing and looking up pairs on the k closest nodes to the key. We then give a lookup protocol that works even in cases where no node shares a unique prefix with a key or some of the subtrees associated with a given node are empty
定义 "a precise notion of ID closeness" 的部分在 2.1 小节中完成。所以这个 "allows" 我们在 2.2 和 2.3 小节中谈到 "storing and looking up pairs on the k closest nodes to the key" 并且我们将了解查找过程是如何工作的。 2.4 节现在将解决在没有节点与键共享唯一前缀（又名不平衡树）的情况下查找的问题，这里是实际完成的 "lookup protocol"。
因此，数组结构在开始时用作 dummy-strucuture，我们用它来理解查找过程，在了解查找过程的工作原理后，我们将介绍更高级的树结构。
这可能是作者的想法。