假设我们有一棵有向树（有向图）。因此，随着时间的推移，我们将在主分支上构建，在该分支上，我们将主分支定义为距根（整棵树中的第一个节点）的最长分支，并且在构建它时，我们可以随时构建新分支通过将新节点附加到任意节点，但是在大多数情况下，我们基于尖端（在最长分支上）构建。
图节点的格式为：
struct {
int id;
int prev_node_id; // this is what links nodes together
}
假设我们选择两个随机节点X和Y。问题是：这些节点是否共享分支？
每个节点都由一个ID定义（基本上是加密哈希，此处由int简化）。解决此问题的一种方法是，我们仅从一个节点开始返回图，直到遇到另一个节点。这需要循环遍历分支中的所有节点，因此这是O（N），其中N是分支中的节点数，这可能非常非常长（数百万个节点）。我们可以在可进行此操作的节点上构建任何类型的数据O（1），而每个节点的数据大小也为O（1）？
我的解决方案排名第一（不好，因为每个节点的存储量为O（N））：
我们在数据结构中添加一个任意的长质数：
struct {
int id;
int prev_node_id;
ArbitraryPrecisionInt branch_index;
}
无论何时将节点附加到树的任何部分，我们都将branch_index定义为：
branch_index_new = branch_index_old * new_prime_number;
其中新质数来自单例生成器。假设我们有几百万个节点，这并不算昂贵。至少还算不错。
那么，节点X和Y是否共享同一分支？
如果是X % Y == 0或Y % X == 0，答案为是。
这里的问题是，该产品的尺寸将增长非常快。前1000个质数的乘积巨大。
我的解决方案第二（有点不好，因为它的搜索时间为O（log（N）），但每个节点的存储量为O（1））：
struct {
int id;
int prev_node_id;
int branch_id;
}
branch_id主要来自单例。我们从0开始，对于我们创建的每个新节点，都有两种情况。
- 如果我们添加的节点位于树的顶端（该节点上不存在其他分支），则我们添加相同的值
- 如果该节点上已经存在分支，则将数字递增1（数字是从单例生成的，因此永远不会重复）。
然后，我们创建一个数据库表，在其中写入每个新增量与每个值的高度（将高度定义为从根节点到该节点的长度）。
那么，节点X和Y是否共享同一分支？为了回答这个问题，我们先看X的branch_id，然后看数据库，然后找到创建分支的高度。我们去那里，找到之前的点的branch_id。我们一直这样做，直到到达根（失败）或找到Y的branch_id。
整个故事是我要解决的区块链问题。实际问题的细节确实很复杂，没有必要去做。但是，如果您有兴趣，随时与我聊天。我之所以这样说是因为有人肯定会将此称为XY问题。
有更好的方法吗？