MySQL模糊搜索的大O

Question

什麼是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%

有沒有不同的方法來提供更好的性能？如果是的話，對於特殊情況，你能分享一下嗎？

Answer 1

擁有國內領先的通配符

MySQL將

1. 掃描中的所有表（而不是指數）行。這被稱爲「表格掃描」。 （假設沒有其他過濾正在進行。）
2. 對於每一行，請掃描LIKE所涉及的列;
3. 傳遞未過濾的行。

大部分時間都花在步驟1，即O（N），其中N是行數。更短的時間花費在步驟2和3

沒有前導通配符

1. 使用對列的索引，如果你有一個，限制行搜索的次數。如果您在該列上有一個索引並且正在說WHERE col LIKE 'Hello W%'，它會查找以Hello W開頭的索引中的所有行。它們在索引中將是連續的，這使得這一步更快。
2. 對於其中的每一個，進入該行的數據並執行所需的任何操作。

有很多變量（緩存，行數，行的隨機性等），導致＃1是否比＃2代價更高或更低。但是這可能比前導通配符的情況要快得多 - O（n），其中n是以'Hello W'開始的行數。