search - 二分查找或 Btree 索引更新问题

Question

想象一下，每天都会有一位作者送给您一本新书。这本书正在编写中。他没有告诉您他更改或添加了什么。

您的工作是确定更改和添加内容，然后仅将这些内容传递给出版商(出版商没有时间每天阅读整本书)

为了解决这个问题，这本书由 100 万行 ASCII 文本组成，并且还在不断增长(实际上是一个 MySQL 备份文件)。

我当前的想法是对每行(1k 个字符)进行安全哈希(例如 SHA256)并将其存储在 HD 上。由于哈希值只有 32 字节，因此文件只有 32MB。

然后，当我们明天获取下一个文件时，我们会逐行检查它，为每一行创建一个新的哈希值，并将其与前一天的哈希值进行比较。

该过程完成后，我们将覆盖哈希文件，为第二天做好准备。

比较使用字符串比较的二分查找方法(><操作数)这会平均返回四次迭代的结果。

我还没有编写 btree 索引解决方案，但是您将如何解决这个问题？

Answer 1

我会使用diff .

如果我需要在自己的程序中实现它，我会使用其中一种算法来查找 longest common subsequence两个序列，将每个文件视为行序列。