如何在多台服务器上扩展一棵trie树

Question

有谁知道如何跨多台计算机扩展 Trie？比如第一台机器已经用完了空间，我需要从一个非常大的字典中添加更多单词，我该怎么办？（我是一个Java程序员，但我相信答案可以与编程语言无关）。我已经意识到不能仅靠每个首字符使用一台计算机，因为这并不是可扩展的。

- Katedral Pillon

Answer 1

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

如何扩展二叉树或者更好的是平衡二叉树？有几个例子可以做到这一点:

1. 如果只有 2 台机器且存储是您的问题，我将在一台机器上保留根和左子树，并将右子树发送到另一台机器。
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 种选择：

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

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

   • A-F
   • G-M
   • N-R
   • SA-SM
   • SN-SZ
   • T-Z

这里的第一种方案可能是最简单和最干净的解决方案，但可能会有一些未使用的硬件。如果您可以为节点使用不同的资源，则使用小型负载均衡器的选项1可能是最好的选择，特别是对于字母S。 选项2是一个混合的解决方案，而选项3可能是最好的方式，但它可能使负载均衡器变得复杂和容易出错。

希望这些想法能帮助您。

- peter

---

非常感谢！！！我已经将您的回答标记为解答。但现在我有一个疯狂的情况要问。如果一个单词 - 只是一个单词 - 太大而无法存储在一个服务器上，该怎么办？我知道这是一个疯狂的问题。但是你如何处理这种情况？ - Katedral Pillon

你如何创建字典树？因为我所学的方法是，将一个单词/句子/<任何你想索引的东西>的每个现有字符放在第一层，每个后续层都会按顺序添加下一个字符，这基本上是查找文本中是否存在一系列字符的方法。这样，如果文本（单词）不符合要求，您只需要在索引过程中识别它并根据我描述的三种方法之一拆分字典树即可。 - peter

另一方面，如果您只是为以某个字符序列开头的单词建立索引，则您的trie将小得多，但是您是正确的，拆分不适合的单词/文本将更加困难。我想唯一的解决方法是拆分掉一些中间层，然后如果您访问该层，它实际上会将调用转发到另一台机器，在那里存储了其余的数据。但是要找出在哪里进行切割当然更加复杂。 - peter

这可能看起来是一个非常幼稚的问题，但我想问一下，像 trie（或其部分）如何存储在计算机中。Trie 是一种数据结构，意味着它可以驻留在 RAM 中。然而，对于 DB，我们可以有 Nosql 或 Sql。我们将如何将 trie 映射到 DB。 - Nikhil Kumar vats