algorithm - 倒排索引和关系型数据库如何优化 "text search"？

Question

关闭。这个问题需要更多 focused 。它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注 editing this post 的一个问题。

4年前关闭。



Improve this question




更新 2020-02-18

我再次遇到这个问题，虽然接受的答案保持不变，但我想分享我现在如何优化它(再次不使用第三方库或工具 - 即像原始问题中提到的那样从头开始重新发明轮子) .

为了简化和优化这个系统，我会在域逻辑层使用特里(前缀树)代替“倒排索引图” 和丢弃完全“表查询” SQL表的不良做法。我将举例说明:

假设应用程序的一些用户已经向数据库添加了几个对象:w、wo、woo、wood 和 woodx。

这些对象(它们是字符串/标签)将在内存中由一个 Trie 表示，每个 Trie 节点将包含该对象在树中级别(思考关联数组)的数据库发布 ID。

当用户查询一个词时，我们在Trie中搜索该词并累积所有相关ID，从搜索到的词开始向下移动(即从那里依次遍历)。我们从这些 ID 中检索所有需要的对象数据(无论是来自缓存还是数据库)。

这里有一张图来说明:

接下来，如果用户向数据库添加一个新词，例如“ woodxe ”，Trie 会相应更新。

当用户查询“ woodx ”时，发生与之前相同的过程，并额外累积一个新ID(“0x2919192131418192131418192131418192131418192131418192133141819231418192314181923141419231419231419231419433141819234315192334181924

英语词典中有一个有限的单词列表，以特定的字母序列开头，因此向下移动并获取所有子节点仍然是一个复杂度为 O(1) 的有限过程。例如，如果您在 Trie 上以“wood”开头，则英语词典中以“wood”为前缀的子节点列表是一个有限常数。是否将所有这些子节点返回给用户、定义限制(延迟加载/分页)或仅显示前 10 次点击，是个人架构偏好。

这是一张图片来说明(检查绿色添加的内容)

当用户的查询是一个多词串时，例如:“wood Furniture”，每个词都被分别解析/添加到 Trie 中，每个词都会有相应的匹配 ID 列表。

*Trie* 如何改进以前的架构？

“表查询”，这是繁琐的，不好的做法和与数据库成正比增长的巨大开销；现在已删除。

我们拥有的“倒排索引映射”产生了额外的内存开销，并且无法通过新词轻松扩展(如上面的“woodx”示例)。有人可能会争辩说，查询 Hashmap 是 O(1)，但是在内存中拥有几个大的 hashmap 实际上会在一定程度上减慢速度，并且被认为是糟糕的工程设计。

trie 的搜索复杂度为 O(m)，其中 m 是提供的字母表中的字符数。 由于用户查询的是纯粹使用英文字母的单词，因此最大的子树将等于可用的最大英文单词(常数，即 O(1))。此外，如前所述，在英语词典中以定义的单词前缀开头的子节点的数量也是一个常数，因此遍历所有组合是 O(1)。所以总的来说它是一个 O(1) 操作。

所以查询 Trie = Get key from Hashmap = O(1) 一样快。

最重要的是，在这个系统中使用 trie 的好处是:

比在内存中运行多个倒排索引哈希映射更小的内存开销

集中查询树

简单的可扩展性，其中添加到数据库的新词只需要向内存中的现有 Trie 添加几个新节点。即，不再有数据库增长和搜索查询数量增加的问题(可扩展性噩梦)。

更新 2015-10-15

早在 2012 年，我正在构建一个个人在线应用程序，实际上想重新发明轮子，因为我天生好奇，出于学习目的并提高我的算法和架构技能。我本来可以使用 apache lucene 和其他的，但是正如我所提到的，我决定构建自己的迷你搜索引擎。

问题:那么除了使用诸如 elasticsearch、lucene 等可用服务之外，真的没有办法增强这个架构吗？

原始问题

我正在开发一个 Web 应用程序，用户在其中搜索特定标题(例如:book x、book y 等)，哪些数据位于关系数据库 (MySQL) 中。

我遵循的原则是，从数据库中获取的每条记录都缓存在内存中，以便应用程序对数据库的调用更少。

我开发了自己的迷你搜索引擎，架构如下:

这是它的工作原理:

a) 用户搜索记录名称

b) 系统检查查询以什么字符开始，检查查询是否存在:获取记录。如果没有，添加它并使用两种方式从数据库中获取所有匹配的记录:

表“查询”(这是一种历史表)中已经存在的查询，因此根据 ID 获取记录(快速性能)

或者，否则使用 Mysql LIKE %% 语句来获取记录/ID(然后将用户使用的查询保留在历史表查询中以及它映射到的 ID)。
--> 然后它把记录和它们的 id 添加到缓存中，并且只将 id 添加到倒排索引映射中。

c) 结果返回到 UI

系统工作正常，但是我有两个主要问题，我找不到好的解决方案(过去一个月一直在尝试):

首要问题:
如果您检查点 (b) ，在未找到查询“历史记录”并且必须使用 Like %% 语句的情况下:当查询匹配数据库中的大量记录(而不是一两个)时，此过程将变得耗时:

从 Mysql 获取记录需要一些时间(这就是我在特定列上使用 INDEXES 的原因)

然后是保存查询历史的时间

然后是将记录/ID 添加到缓存和倒排索引映射的时间

第二个问题:
该应用程序允许用户为自己添加新记录，登录到应用程序的其他用户可以立即使用这些记录。
然而，要实现这一点，必须更新倒排索引映射和表“查询”，以便在任何旧查询与新词匹配的情况下。例如，如果添加新记录“woodX”，旧查询“wood”仍会映射到它。因此，为了将查询“wood”重新挂接到这条新记录，这是我现在正在做的事情:

新记录“woodX”被添加到“记录”表

然后我运行一个 Like %% 语句来查看表“queries”中哪个已经存在的查询确实映射到这个记录(例如“wood”)，然后用新的记录 ID 添加这个查询作为一个新行:[ wood,新身份证]。

然后在内存中，更新倒排索引 Map 的“wood”键的值(即列表)，通过将新记录 Id 添加到此列表

--> 因此，如果远程用户搜索“wood”，它将从内存中获取:wood 和 woodX

这里的问题也是时间消耗。将所有查询历史(在表查询中)与新添加的词匹配需要很多时间(匹配的查询越多，时间越长)。然后内存更新也需要很多时间。

我正在考虑如何解决这个时间问题，首先将所需的结果返回给用户，然后让应用程序使用所需的数据发布 ajax 调用以实现所有这些 UPDATE 任务。但我不确定这是不好的做法还是不专业的做事方式？
所以在过去的一个月里(多一点)，我试图为这个架构考虑最好的优化/修改/更新，但我不是文档检索领域的专家(实际上它是我构建的第一个迷你搜索引擎)。

我将不胜感激任何关于我应该做什么才能实现这种架构的反馈或指导。
提前致谢。

PS:

它是一个使用 servlet 的 j2ee 应用程序。

我正在使用 MySQL innodb(因此我不能使用全文搜索选项)

Answer 1

我强烈推荐 Sphinx Search Server，它最适合在全文搜索中进行优化。访问 http://sphinxsearch.com/ 。

它旨在与 MySQL 一起使用，因此它是您当前工作区的补充。