如何跨多个服务器扩展一个 trie
How to scale a trie across multiple servers
有谁知道我如何在多台机器上扩展 Trie 树？假设第一台机器用完 space 并且我需要从一个非常大的词典中添加更多单词，我应该怎么做才能添加更多单词？ （我是一个 Java 思想家，但我相信答案可以与语言无关）。我已经意识到我不能只为每个第一个字符说一台机器，但这并没有真正扩展。
好的，假设你的两台机器都有相同的可用资源，让我们先看一个更简单的例子：
你会如何缩放二叉树？甚至更好——AVL 树？有几个例子可以做到这一点：
- 如果只有 2 台机器并且存储是你的问题，我会将根和左子树保留在一台机器上，并将右子树发送到另一台机器上。
- 如果你有 3 台机器并且还想有一个负载均衡器，根将保留在一台机器上，左右子树将拆分到其他 2 台机器上。如果您有 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-深圳
- T-Z
这里的数字 1 可能是最简单和最干净的解决方案，但可能有一些未使用的硬件。如果您可以为节点使用不同的资源，选项 1 和一个小负载均衡器可能是可行的方法。
选项 2 是一个肮脏的组合，选项 3 可能是最好的方法，但它使负载平衡器可能变得复杂且容易出错。
希望这些想法对您有所帮助。
有谁知道我如何在多台机器上扩展 Trie 树？假设第一台机器用完 space 并且我需要从一个非常大的词典中添加更多单词，我应该怎么做才能添加更多单词？ （我是一个 Java 思想家，但我相信答案可以与语言无关）。我已经意识到我不能只为每个第一个字符说一台机器，但这并没有真正扩展。
好的，假设你的两台机器都有相同的可用资源，让我们先看一个更简单的例子：
你会如何缩放二叉树？甚至更好——AVL 树？有几个例子可以做到这一点：
- 如果只有 2 台机器并且存储是你的问题，我会将根和左子树保留在一台机器上，并将右子树发送到另一台机器上。
- 如果你有 3 台机器并且还想有一个负载均衡器，根将保留在一台机器上，左右子树将拆分到其他 2 台机器上。如果您有 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-深圳
- T-Z
这里的数字 1 可能是最简单和最干净的解决方案，但可能有一些未使用的硬件。如果您可以为节点使用不同的资源，选项 1 和一个小负载均衡器可能是可行的方法。 选项 2 是一个肮脏的组合，选项 3 可能是最好的方法，但它使负载平衡器可能变得复杂且容易出错。
希望这些想法对您有所帮助。