MySQL模糊搜索的大O

什么是MySQL模糊搜索的大O？它是否因索引类型而异？如果是这样，什么表现最好？MySQL模糊搜索的大O

例如SELECT * FROM foo WHERE field1 LIKE '%ello Wo%';

我不确定底层的数据类型，它拥有什么样的魔法。类似于trie（https://en.wikipedia.org/wiki/Trie）的东西对于最后模糊不清的搜索者来说是很好的，例如， LIKE 'Hello Wo%'。

我猜Big-O是O(n)但希望确认。模糊搜索之间甚至可能存在差异，例如， %ello Wo%与Hello W%对比%lo World对%ell%o%W%or%

有没有不同的方法来提供更好的性能？如果是的话，对于特殊情况，你能分享一下吗？

2016-03-15 James Oravec

全文搜索使用[排名与矢量空格]（http://dev.mysql.com/doc/internals/en/full-text-search.html）。似乎大多数模糊搜索算法都是针对子线性（'O（log n）'），并且在实践中运行，但理论上是'O（n）'。见例如[这篇相关的博客文章]（http://ntz-develop.blogspot.se/2011/03/fuzzy-string-search.html）。 – dfri

拥有国内领先的通配符

MySQL将

扫描中的所有表（而不是指数）行。这被称为“表格扫描”。（假设没有其他过滤正在进行。）
对于每一行，请扫描LIKE所涉及的列;
传递未过滤的行。

大部分时间都花在步骤1，即O（N），其中N是行数。更短的时间花费在步骤2和3

没有前导通配符

使用对列的索引，如果你有一个，限制行搜索的次数。如果您在该列上有一个索引并且正在说WHERE col LIKE 'Hello W%'，它会查找以Hello W开头的索引中的所有行。它们在索引中将是连续的，这使得这一步更快。
对于其中的每一个，进入该行的数据并执行所需的任何操作。

有很多变量（缓存，行数，行的随机性等），导致＃1是否比＃2代价更高或更低。但是这可能比前导通配符的情况要快得多 - O（n），其中n是以'Hello W'开始的行数。

来源

2016-03-15 21:35:40

MySQL模糊搜索的大O

回答

相关问题