有谁知道如何跨多台计算机扩展 Trie?比如第一台机器已经用完了空间,我需要从一个非常大的字典中添加更多单词,我该怎么办?(我是一个Java程序员,但我相信答案可以与编程语言无关)。我已经意识到不能仅靠每个首字符使用一台计算机,因为这并不是可扩展的。
有谁知道如何跨多台计算机扩展 Trie?比如第一台机器已经用完了空间,我需要从一个非常大的字典中添加更多单词,我该怎么办?(我是一个Java程序员,但我相信答案可以与编程语言无关)。我已经意识到不能仅靠每个首字符使用一台计算机,因为这并不是可扩展的。
假设您的两台机器具有相同的资源可用性,让我们首先看一个更简单的例子:
如何扩展二叉树或者更好的是平衡二叉树?有几个例子可以做到这一点:
(请注意,平衡此类分布式树将更加复杂,因为您需要与其他计算机通信,可能需要在分布式事务内进行操作,以便能够同时回答所有请求)
所以现在是字典树,AFAIR 是一棵树/字母。如果单词中的字母分布均匀,您可以在一台机器上放置 A-M,另一台机器上放置 N-Z。这可能不起作用,但您肯定可以将其大致拆分为 50/50。
如果您现在想要添加越来越多的机器,我会保留一个主节点,它将作为负载均衡器,并将其分发到子节点,后者只需要处理几个字母。例如,您可以有以下节点:
假设您对字母 A-F 的数据量大约与字母 S 的数据量相同。 (实际上可能存在一种语言,这将至少接近于最优分布)
现在,如果您在 A-F 中收到太多字母,您可以将其拆分为 A-D 和 E-F 等。那里真的没有任何变化。问题将是如果您在 S 中收到太多字母。现在您有 3 种选择:
修改根负载均衡器以能够在节点之间指定更复杂的边界,例如现在您拥有以下节点:
这里的第一种方案可能是最简单和最干净的解决方案,但可能会有一些未使用的硬件。如果您可以为节点使用不同的资源,则使用小型负载均衡器的选项1可能是最好的选择,特别是对于字母S。 选项2是一个混合的解决方案,而选项3可能是最好的方式,但它可能使负载均衡器变得复杂和容易出错。
希望这些想法能帮助您。