如何跨多台服务器扩展特里树

Question

有谁知道我如何在多台机器上扩展 Trie？假设第一台机器空间不足，我需要从一个非常大的字典中添加更多单词，我该怎么做才能添加更多单词？（我是一名 Java 思想家，但我相信答案可能与语言无关）。我已经意识到我不能只为每个第一个角色说一台机器，但这并不能真正扩展。

Answer 1

好的，假设你的两台机器都有相同的可用资源，让我们先看一个更简单的例子：

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

1. 如果只有 2 台机器并且存储是您的问题，我会将根和左子树保留在一台机器上，并将右子树发送到另一台机器。
2. 如果您有 3 台机器并且还想要一个负载均衡器，则根将留在一台机器上，左右子树将在其他 2 台机器上拆分。如果您有 5 个，则将根节点和第一级子节点保留在负载均衡器上并拆分树的其余部分。

（请注意，平衡这样的分布式树会复杂得多，因为您需要与其他机器进行通信并可能在分布式事务中进行，以便能够同时回答所有请求）

所以，现在一个特里，它 - AFAIR - 是一棵树/字母。如果您单词中的字母分布均匀，您可以在一台机器上使用 AM，在另一台机器上使用 NZ。这可能行不通，但您肯定可以像这样或多或少 50/50 拆分它。

如果你现在想添加越来越多的机器，我会保留一个主节点作为负载均衡器并将其分配给子节点，它只会处理几个字母。例如你可以有节点

• 自动对焦
• 通用汽车
• NR
• 秒
• 天地

假设字母 AF 的数据量与字母 S 的数据量大致相同。（实际上可能存在一种语言，这至少接近于最佳分布）

现在，如果您在 AF 中得到太多字母，您可以将其拆分为 AD 和 EF，例如，那里没有任何真正的变化。问题是如果你在 S 中得到太多字母。现在你有 3 种可能性：

1. 您为字母 S 制作另一个负载均衡器 - 这肯定很容易，因为您已经实现了一个负载均衡器，并且您可以在任何级别使用相同的功能
2. 您将字母 SA-SM（例如）保存在一个节点中，该节点将成为主节点，将 SN-SZ 存储在一个单独的节点上。因此，如果您获得 SP .. 第一个负载均衡器会将其发送到您的 SA-SM 节点，然后该节点会将其转发到 SN-SZ

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

   • 自动对焦
   • 通用汽车
   • NR
   • SA-SM
   • SN-SZ
   • 天地

这里的数字 1 可能是最简单、最干净的解决方案，但可能有一些未使用的硬件。如果您可以为节点使用不同的资源，那么选项 1 可能是使用字母 S 的小型负载均衡器的方法。选项 2 是一个肮脏的组合，选项 3 可能是最好的方法，但它使负载平衡器可能变得复杂且容易出错。

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