别再问我什么是 BT 种子( 七 )

所有可能的节点 ID 都在这棵二叉树上。4 位数需要分叉 4 次,生成 2 的 4 次方即 16 条路径,每条路径的终点,就是一个节点 ID。

接下来,你作为 0100,就可以拆分这颗二叉树了,从第一次分叉开始,把不包含你的那棵子树拆分,然后在剩下的子树的第二次分叉处再次拆分,直到只剩下你自己。

这样,就拆分出了 4 个子树。

别再问我什么是 BT 种子

我们在每个子树里选 2 个点,就得到了 4 个 K 桶——K-bucket。

暂停下来想想你就会发现,用异或算法计算 0 号 K 桶和你的距离是 0001,换算成十进制就是1,1 号 K 桶里 2 个点和你的距离是 2-3,以此类推,2 号 K 桶的距离区间是 4-7,3 号 K桶的距离区间是 8-15。

别再问我什么是 BT 种子

我们刚刚算过,你的节点 ID 0110 和目标 ID 1111 之间的二进制距离是 1011,换算成十进制是 11,也就是说,离 1111 最近的,肯定是 3 号 K 桶里的 2 个节点。

推荐阅读