8.10 扩展性与存储限制 (2 / 4)
拆分大量的数据
尽管有时我们可以增加计算机的硬盘空间，不过，难免会遇到必须将数据拆分至多台计算机的情形。随之而来的问题是，哪些数据要放在哪一台机器上。下面有几种策略可供参考。
?按出现的顺序
我们可以按出现的顺序直接划分数据。也就是说，有新数据进来时，先放进当前机器，填满之后，再加一台机器。这么做的好处是不会浪费资源。然而，根据具体问题和数据集的不同，查找表可能会变得非常复杂、异常巨大。
?按散列值
另一种做法是根据数据的散列值存放数据。具体一点来说，我们会采取以下步骤：（1）根据数据挑选某种键；（2）利用散列函数得到键的散列值；（3）将散列值除以机器数量求得余数；（4）将数据存储在这个值对应的机器上。也就是说，数据会存放在编号为#[mod(hash(key),N)]的机器上。
这种做法的好处是不用创建数据查找表。每一台计算机自动掌握数据的存储位置。然而，这也会出问题，那就是某台机器的数据可能会多一些，并最终超出它的存储容量。若发生这种情况，可以将数据迁移到其他机器上，以实现更好的负载均衡（但开销很大），或者将这台机器的数据拆分到两台机器上（形成一组树状结构的机器）。
?按实际值
按散列值划分数据本质上是随机的；数据代表的具体意义与存储数据的机器之间，并不存在任何关系。在某些情况下，我们也许可以利用数据所代表的信息来降低系统延迟。
例如，假设你正在设计一个社交网站。虽然人们的朋友会来自世界各地，但实际上，相比俄罗斯普通公民，住在墨西哥的人可能拥有更多来自墨西哥的朋友。或许，我们可以将“类似”数据存储在同一台机器上，这样在查找墨西哥人的朋友时，只需访问较少数量的机器就能取得相关资料。
?随机存储
通常情况下，我们只是随机划分数据，再实现一个查找表以表明哪台机器拥有哪些数据。虽然这肯定需要一张巨大的查找表，但它简化了系统设计的某些方面，使我们得以实现更好的负载均衡。
示例：查找所有包含某一组词的文件
给定数百万份文件，如何找出所有包含某一组词的文件？我们不关心这些词出现的顺序，但它们必须是完整的单词。也就是说，“book”与“bookkeeper”不是一回事。
在着手解决问题之前，我们需要考虑findWords程序只用一次，还是要反复调用。假设需要多次调用findWords程序来扫描这些文件，那么，我们可以接受预处理的开销。
步骤1
The content is not finished, continue reading on the next page
尽管有时我们可以增加计算机的硬盘空间，不过，难免会遇到必须将数据拆分至多台计算机的情形。随之而来的问题是，哪些数据要放在哪一台机器上。下面有几种策略可供参考。
?按出现的顺序
我们可以按出现的顺序直接划分数据。也就是说，有新数据进来时，先放进当前机器，填满之后，再加一台机器。这么做的好处是不会浪费资源。然而，根据具体问题和数据集的不同，查找表可能会变得非常复杂、异常巨大。
?按散列值
另一种做法是根据数据的散列值存放数据。具体一点来说，我们会采取以下步骤：（1）根据数据挑选某种键；（2）利用散列函数得到键的散列值；（3）将散列值除以机器数量求得余数；（4）将数据存储在这个值对应的机器上。也就是说，数据会存放在编号为#[mod(hash(key),N)]的机器上。
这种做法的好处是不用创建数据查找表。每一台计算机自动掌握数据的存储位置。然而，这也会出问题，那就是某台机器的数据可能会多一些，并最终超出它的存储容量。若发生这种情况，可以将数据迁移到其他机器上，以实现更好的负载均衡（但开销很大），或者将这台机器的数据拆分到两台机器上（形成一组树状结构的机器）。
?按实际值
按散列值划分数据本质上是随机的；数据代表的具体意义与存储数据的机器之间，并不存在任何关系。在某些情况下，我们也许可以利用数据所代表的信息来降低系统延迟。
例如，假设你正在设计一个社交网站。虽然人们的朋友会来自世界各地，但实际上，相比俄罗斯普通公民，住在墨西哥的人可能拥有更多来自墨西哥的朋友。或许，我们可以将“类似”数据存储在同一台机器上，这样在查找墨西哥人的朋友时，只需访问较少数量的机器就能取得相关资料。
?随机存储
通常情况下，我们只是随机划分数据，再实现一个查找表以表明哪台机器拥有哪些数据。虽然这肯定需要一张巨大的查找表，但它简化了系统设计的某些方面，使我们得以实现更好的负载均衡。
示例：查找所有包含某一组词的文件
给定数百万份文件，如何找出所有包含某一组词的文件？我们不关心这些词出现的顺序，但它们必须是完整的单词。也就是说，“book”与“bookkeeper”不是一回事。
在着手解决问题之前，我们需要考虑findWords程序只用一次，还是要反复调用。假设需要多次调用findWords程序来扫描这些文件，那么，我们可以接受预处理的开销。
步骤1
The content is not finished, continue reading on the next page