想象一下，您每天都会收到一位作者的新书。这本书正在进行中。他没有告诉你他改变或增加了什么。
您的工作是识别更改和添加内容，并仅将它们传递给出版商（他们没有时间每天阅读整本书）
出于这个问题的目的，这本书由 1m 行的 ascii 文本组成，并且还在不断增长（实际上是一个 MySQL 备份文件）。
我目前的想法是对每行（1k 个字符）进行安全哈希（例如 SHA256）并将其存储在 HD 上。由于散列只有 32 字节，因此文件只有 32MB。
然后当我们明天得到下一个文件时，我们逐行检查它，为每一行创建一个新的散列，并将其与前一天的散列进行比较。
当该过程完成后，我们会覆盖为第二天准备的哈希文件。
比较使用字符串比较（ > < 操作数）的二进制搜索方法，这将返回平均四次迭代的结果。
我还没有编写 btree 索引解决方案，但你将如何解决这个问题？
“然后当我们明天得到下一个文件时，我们逐行检查它，为每一行创建一个新的哈希值，并将其与前一天的哈希值进行比较。”
明白了：今天的 100 万行哈希值与昨天的 100 万行哈希值相比。
是否插入或删除行？如果不是，这是一组简单的并行读取，以查看哈希是否不同。
如果有添加或删除，则必须使用 diff 算法来确定更改的范围。
这一切都很好。实施起来难度不大。
在这种情况下，以下内容毫无意义。
比较使用字符串比较（ > < 操作数）的二进制搜索方法，这将返回平均四次迭代的结果。
哈希值是否有某种排序？还是一些树结构？
100 万行的书是巨大的：每页可能有 30 到 50 行，所以让我们大方地假设每页 100 行，这意味着书中有 10,000 页。
1 KB 的行也比正常的大得多；基本的可读性表明每行的字符数远不及那么多。您打算散列最多 1 KB 的行，还是将文件分块为 1 KB 块？您的方案的一个问题是任何重复的行都会有重复的散列；您永远无法确定何时添加或删除了这些行之一。
您可能还需要通知发布者删除的行。
与 Glomek 一样，我会diff在文件上使用。如果您将文件保留在 RCS 或 CVS 控制下，您将只保存文件的当前版本以及存储先前版本之间的差异。有了这个，您也可以提供一周或一个月的累积差异。
而且我可能不会开发自己的 B-Tree 索引。
您描述的解决方案有点类似于 rsync 算法。重要的一点是 rsync 必须识别目标文件中任何位置的现有块，与原始文件的任何偏移量。
如果您的文件确实是记录结构，您可以按照您的建议进行一些简化。如果没有，您需要滚动校验和。
另外，您是否必须识别重新排序？还是只有插入/删除/替换？
最通用的情况是完整的 rsync 算法，如下所示：
参数定义：
旧文件的签名：
使用新文件和旧文件签名创建“补丁”：
将补丁应用于旧文件
这是一种用于数据仓库增量加载的技术。在您无法识别源系统中更改的数据的情况下，您可以取出数据的快照并将其与上一个快照进行比较以识别差异。这种技术甚至在Ralph Kimball 关于该主题的书中得到了提及，并被用于我参与设计的应用程序中。
您需要一个具有非常宽密钥的散列算法，因为这种方法容易受到生日攻击。MD5 或任何 SHA 系列都可以。如果没有通过差异寻找丢失的自然键的后处理，它也无法检测到删除。这种计算实际上需要知道表结构。
您的方案的一个问题是任何重复的行都会有重复的散列；您永远无法确定何时添加或删除了这些行之一
很好的一点，但不是问题。重复的行是重复的，所有重复的都在下一个处理阶段被删除。所以是的，你是对的，但这不是问题。
“差异”链接将我带到一个页面，其中描述了我认为是应用程序的内容？没有下载链接，没有任何语言的代码......我在这里错过了什么？
你们中的一些人谈到了字节级粒度。这不是必需的。只需要行级别的粒度，因为如果行中的任何内容发生了更改，则必须重新处理整行（记录），因为行内的任何更改都会影响整行。
因此，我们在两个文件（今天的快照和昨天的快照）中比较大约 1000 个字符（无二进制）的行，每个文件大约 1m 行。
因此，使用 SHA256 之类的安全哈希（MD5 有冲突，相比之下速度较慢）我可以在我的 HO 笔记本电脑上处理大约 30MB/秒。服务器当然会更快地咀嚼它。
因此，如果文件是 1GB 左右，那么制作所有的 hases 大约需要 33 秒，而使用 Windows 页面内存读取 1Gb 文件大约需要 30 秒。不可怕
现在我们有两个哈希数组，代表每个文件中的行。如果我们对它们进行排序，我们现在可以使用二进制搜索，因此我们遍历新文件哈希以寻找旧文件哈希中的匹配项。如果我们没有找到它，该行将添加到更改文件中。
请记住，行书（遗留数据库）在各个方面都是未知的。无法保证行的顺序、更改的位置、更改的类型。
逐页阅读前文的建议很好，但假设这两个文件在第一次更改之前是按 smae 顺序排列的。这是不能假设的。行（行）可以是任何顺序。选择任意块大小也违反了行的粒度。出于此任务的目的，行是不可变的。
来自关于 invrementa 加载的优秀链接：文件比较捕获：此方法也称为快照差异方法。此方法通过保留与数据仓库相关的文件的前后图像来工作。比较记录以查找更改，比较记录键以查找插入和删除。由于触发器通常不存在并且事务日志不存在或采用专有格式，因此该技术最适合遗留系统的情况。由于大多数遗留数据库都有一些将数据转储到文件中的机制，因此该技术会创建定期快照，然后比较结果以生成更改记录。当然，静态捕获的所有问题都存在于此。比较整行信息以及密钥识别和匹配的挑战引入了额外的复杂性。这种技术本质上很复杂，通常是不可取的，但在某些情况下，它可能是唯一的解决方案。
这一点在这里最为相关：随着我们进入 TB 级数据仓库领域，每晚从头开始重建数据仓库的能力将步履蹒跚。更新数据仓库的逻辑和有效方法涉及某种形式的增量更新策略。
所以我想我是在正确的轨道上？btree 索引没有优势吗？