我有一个包含图像感知散列的大型数据库（16M 行）。
我希望能够在合理的时间范围内通过汉明距离搜索行。
目前，据我正确理解这个问题，我认为这里最好的选择是实现BK-Tree的自定义 SP-GiST 实现，但这似乎需要做很多工作，而且我对实际操作仍然很模糊正确实施自定义索引的详细信息。计算汉明距离很容易处理，不过我确实知道 C。
基本上，这里的适当方法是什么？我需要能够在哈希的某个编辑距离内查询匹配项。据我了解，具有相等长度的字符串的 Levenshtein 距离在功能上是汉明距离，因此至少有一些现有的支持我想要的东西，尽管没有明确的方法可以从中创建索引（请记住，我正在查询的值变化。我无法预先计算与固定值的距离，因为这只对那个值有用）。
哈希当前存储为包含哈希的二进制 ASCII 编码的 64 字符字符串（例如“10010101...”），但我可以很容易地将它们转换为 int64。真正的问题是我需要能够相对快速地查询。
似乎可以通过 实现我想要的东西pg_trgm，但我有点不清楚三元组匹配机制是如何工作的（特别是，它返回的相似性度量实际上代表什么？看起来有点像编辑距离）。
插入性能并不重要（计算每一行的哈希值非常昂贵），所以我主要关心搜索。
摩尔答案！
好的，我终于花时间编写了一个自定义 PostgreSQL 索引扩展。我使用了SP-GiST 界面。
这是相当具有挑战性的，主要是因为 Posgres很大。
无论如何，像往常一样，它在github 上。
在性能方面，它目前比我对这个问题的另一个答案中的纯内存实现慢约 2-3 倍，但使用起来更方便我会很高兴地吃掉性能损失（实际上，它是 ~50 ms/query - 150 ms/query，仍然很小）。
好吧，我花了一段时间研究编写一个自定义的 postgres C 扩展，最后只写了一个 Cython 数据库包装器，它在内存中维护一个 BK-tree 结构。
基本上，它维护数据库中 phash 值的内存副本，并且对数据库的所有更新都重播到 BK 树中。
这一切都在 github 上。它也有很多单元测试。
在包含 1000 万个哈希值的数据集中查询距离为 4 的项目会触及树中约 0.25%-0.5% 的值，并且需要约 100 毫秒。