我现在正在通过阅读经典论文Kademlia：基于XOR Metric的点对点信息系统来学习Kademlia网络。我想了解其操作的复杂性，但仍然无法弄清楚。
在3 证明草图部分，本文给出了两个定义：
- 节点深度 （h）：160 − i，其中 i 是非空存储桶
- 节点 y 在节点 x 中的存储桶高度：x 将在其中插入 y 的存储桶的索引减去 x 最不重要的空存储桶的索引。
还有三个结论：
- 对于具有 n 个节点的系统，任何给定节点的高度极有可能在 log n 的常数内。
- 最接近第 k 个节点中 ID 的节点的存储桶高度可能在log k 的常量范围内。
- 如果此节点的 h 个最重要的 k 桶中没有一个是空的，则查找过程将在每一步中找到一个接近一半（或者更确切地说，其距离短一点）的节点，从而以 h − log k 步长打开节点。
所以我的问题是：
- 什么是"最不重要的空桶"和"最重要的 k 桶"？
- 如何以视觉方式解释深度和铲斗高度？
- 如何理解第二个和第三个结论，比如说，为什么对数k和h-log k？
一段时间没有真正阅读这篇论文了，所以我主要是从我的实现经验中拼凑起来，而不是试图将我脑海中的概念与论文中的正式定义相匹配，所以对以下内容持保留
态度<小时 />什么是"最不重要的空桶"和"最重要的 k 桶"？
这基本上是指按相对于节点自身 ID 的 XOR 距离排序的存储桶
如何以视觉方式解释深度和铲斗高度？
每个存储桶覆盖一个密钥空间区域。 例如，从0x0000简化为 2 个字节到 0x0FFF 个密钥空间的 1/16。这可以用类似 CIDR 的掩码表示，0x0/4（4 个前缀位）。这或多或少是一个桶的深度。
有几种方法可以组织路由表。"正确"的方法是根据存储桶表示的最低 ID 将其表示为树或排序列表。此方法允许某些路由表优化要求的任意存储桶拆分操作，也可用于实现节点多宿主。
简化的实现可以改用固定长度的数组，并将每个存储桶放在相对于节点自身 ID 的共享前缀位的位置.即数组中的位置 0 将有 0 个共享前缀位，它是最远的存储桶，存储桶覆盖 50% 的密钥空间，存储桶中最重要的位是节点自身 ID 的倒置 MSB。
在这种情况下，深度只是数组位置。
如何理解第二个和第三个结论，比如说，为什么对数k和h-log k？
假设您正在寻找一个离您自己的节点 ID 最远的 ID。然后，您将只有一个存储桶覆盖密钥空间的该部分，即它将覆盖密钥空间的一半，其中最重要的位与您的密钥空间不同。因此，您从该存储桶中询问一个（或多个）节点。由于它们的 ID 位与您的查找目标具有共同的第一个位，因此可以或多或少地保证将其拆分为两个或多个，即目标空间的密钥空间覆盖范围至少是其两倍。因此，他们可以提供至少 1 位更好的信息。
当您查询离目标更近的节点时，它们在目标区域附近也将具有更好的密钥空间覆盖范围，因为这也更接近它们自己的节点 ID。
冲洗，重复，直到找不到更近的节点。
由于每个跃点一次至少缩短 1 位距离，因此您基本上需要一个 O（log（n）） 跃点计数，其中 n 是网络大小。由于网络大小基本上决定了节点之间的平均距离，因此决定了主存储桶所需的存储桶深度。
如果目标密钥更接近您自己的 ID，则需要的步骤更少，因为您将更好地覆盖密钥空间的该区域。
由于 k 是一个常量（每个存储桶的节点数），因此日志 k 也是如此。将存储桶中的节点数加倍，其分辨率将是给定键空间区域的两倍，因此（概率上）生成的节点比 k/2 大小的存储桶更接近目标一点。即，对于要保存的每个跳跃的每个额外位，您必须将每个存储桶的条目数加倍。
<小时 />编辑：这是实际的单宿主bittorrent DHT路由表的可视化，按其前缀排序，即不相对于本地节点ID：
Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4
buckets: 23 / entries: 173
000... entries:8 replacements:8
00100... entries:8 replacements:0
0010100... entries:8 replacements:2
0010101000... entries:8 replacements:4
00101010010... entries:8 replacements:7
001010100110000... entries:8 replacements:3
0010101001100010... entries:8 replacements:3
00101010011000110000... entries:8 replacements:1
001010100110001100010... entries:3 replacements:0
0010101001100011000110... entries:6 replacements:0
0010101001100011000111... entries:6 replacements:0
0010101001100011001... entries:8 replacements:2
001010100110001101... entries:8 replacements:1
00101010011000111... entries:8 replacements:2
00101010011001... entries:7 replacements:0
0010101001101... entries:8 replacements:0
001010100111... entries:8 replacements:0
001010101... entries:8 replacements:1
00101011... entries:7 replacements:0
001011... entries:8 replacements:0
0011... entries:8 replacements:8
01... entries:8 replacements:8
1... entries:8 replacements:8
接受的答案很棒！
- 我认为围绕 h - logk 的解释可以简化。这就是我对 h - log k 的看法。
从特定节点 u 的角度考虑问题。
对于 k 个最近的节点，您拥有邻域的完整信息。这是因为您将项目存储在大小为 k 的存储桶中，并且没有足够的键进入这些存储桶，因此基本上下部的叶子将始终具有空的 k 个存储桶。所以你会知道你所有最近的邻居。
现在树中第 k 个最近的邻居有多高。有 1 个键 1 位远（最终位不同）有 2 个键 2 位（最后两位不同）有 4 个键 3 位（最后 3 位不同）所以第 k 个最近节点的高度 n 为
1 + 2 + 4 + ... + 2^n = k
=> 2^n = k + 1
=> n = log(k+1)
所以第 k 个远节点在高度 log（k）
这告诉我们的是，当您搜索距离为 <= logk（第 k 个节点的高度）的节点时。我们可以立即回答，因为我们知道完整的邻域，并且我们不需要花费logk步骤在每个步骤中获取1位信息，就像当请求的节点更远时我们需要做的那样。
因此，当我们搜索深度为 h 的节点时。您将查询在最坏情况下深度减小 1 的节点，直到到达所请求节点的深度为 log k 的节点，并且该节点可以立即回答查询。
阿拉伯数字。以压倒性的概率在数学上回答您的第一个问题节点高度为 O（log n）
考虑一个网络，其中密钥是 M 位，网络中有 N 个节点。现在我们从特定节点 u 的角度查看路由树。这棵树将挤向高阶位，因为 1/2 可能的键落在顶部桶中，1/4 落在秒中，依此类推。
So what is the probability that your first q slots
in the routing tree with distance
from 2^0 - 2^1 to 2^q-1 - 2^q are empty.
This requires that all the N nodes fall in the buckets greater than q
To select a key in bucket greater than q you
need to ensure that your maximum prefix match is less than M-q.
So there are 2^M total keys of which 2^q keys
have the same prefix of length (M-q) as the node u.
So the favourable cases are 2^M - 2^q.
Total cases are 2^M
Assume all N key draws are independent
So the probability that q lowest slots are empty is (1 - 1/2^(M-q))^N
So we plug in q = M - clog(n) which would mean
that there are clog(n) filled buckets
with M-clog(N) lower buckets empty
P = (1-1/2^(clog(N)))^N
= (1-1/N^c)^N
this is approximately equal to
1-1/N^(c-1)
因此，随着 c 的增加，概率变为 1，我们很可能在路由表中只填充了 clog（n） 个顶部插槽。