architecture - 如何在多个服务器上扩展Trie

Question

有人知道我如何在多台计算机上扩展Trie吗？假设第一台计算机的空间不足，并且我需要从一个很大的字典中添加更多的单词，那么我应该怎么做才能添加更多的单词？ (我是Java思想家，但我相信答案可能与语言无关。)我已经意识到我不能只为每个第一个字符说一台机器，但这并不能真正扩展。

Answer 1

好的，假设您的两台计算机都具有相同的可用资源，我们首先来看一个简单的示例:

您将如何缩放二叉树？甚至更好-AVL树？有几个例子可以做到这一点:

如果只有2台计算机，而存储是您的问题，那么我会将根和左子树保留在一台计算机上，然后将右子树发送到另一台计算机上。

如果您有3台计算机，并且还希望有一个负载平衡器，则根目录将保留在一台计算机上，而左，右子树将在其他两台计算机之间拆分。如果您有5个，则将子级的根级和第一级保留在负载均衡器上，并拆分其余的树。

(请注意，平衡这样的分布式树会更加复杂，因为您需要与其他计算机通信，并可能在分布式事务中进行操作，以便能够同时回答所有请求)

所以，现在是一个特里树-AFAIR-是一棵树/字母。如果您的单词中的字母分布均匀，则您可以在一台计算机上使用A-M，而另一台计算机上使用N-Z。这可能行不通，但是您肯定可以像这样或多或少地以50/50的比例进行拆分。

如果您现在想添加越来越多的计算机，我将保留一个主节点，该节点可以用作负载平衡器，并将其分配给子节点，该子节点只需要处理几个字母即可。例如你可能有节点

A-F

G-M

N-R

S

T-Z

假设，字母A-F的数据与字母S的数据大致相同。(实际上可能存在一种语言，这种语言至少接近最佳分布)

现在，如果您在A-F中收到太多字母，则可以将其拆分为A-D和E-F，例如，那里什么都没有真正改变。问题将是，如果您在S中收到太多字母。现在您将有3种可能性:

您可以为字母S创建另一个负载均衡器-这肯定很容易，因为您已经实现了负载均衡器，并且可以在任何级别的

上使用相同的功能

您将字母SA-SM(例如)保留在一个节点(将成为主节点)中，并将SN-SZ存储在单独的节点上。因此，如果您获得SP ..，则第一个负载均衡器会将其发送到您的SA-SM节点，然后将其转发到SN-SZ

您可以修改负载根负载均衡器，以能够指定节点之间的更复杂边界，例如现在有了节点

A-F

G-M

N-R

SA-SM

SN-SZ

T-Z

这里的1号可能是最简单，最干净的解决方案，但是可能有一些未使用的硬件。如果您可以为节点使用不同的资源，则可能需要选择带有字母S小的负载均衡器的选项1。
选项2是肮脏的混合，选项3可能是最好的选择，但是它使负载均衡器潜在地变得复杂且容易出错。

希望这些想法对您有所帮助。