fender0107401 发表于 2016-12-10 21:26

数据库里面的like这个操作是使用什么算法实现的，计算复杂性如何？

{:yct5:}


不太懂，问问，嘿嘿。

codechurch 发表于 2016-12-11 14:24

mysql 是分词索引的，说白了，就是搜索引擎的技术。

比如，where some like '%china%'

在语义上，它假设china是一个有意义的名词。
标注了分词索引的字段，根据字段内容进行分词索引。

windoze 发表于 2016-12-13 16:33

like有个毛线分词，mysql里还不是用一个石器时代的KMP。
理论上说用KMP在长度为m的字符串里找一个长度为n的子串的时间复杂度为O(m+n)，再乘上记录数就是你要的复杂度。

fender0107401 发表于 2016-12-13 20:33

windoze 发表于 2016-12-13 16:33
like有个毛线分词，mysql里还不是用一个石器时代的KMP。
理论上说用KMP在长度为m的字符串里找一个长度为n ...

貌似很差啊。{:yct12:}

windoze 发表于 2016-12-13 21:46

回复 4# fender0107401

所以这玩意儿很慢啊。

hellioncu 发表于 2016-12-14 08:46

like不一定按“词”的，所也只能kmp之类的算法了

fender0107401 发表于 2016-12-14 22:20

hellioncu 发表于 2016-12-14 08:46
like不一定按“词”的，所也只能kmp之类的算法了

打算采用其他方案，就不用like这个feature了。

sxcong 发表于 2016-12-15 15:25

其实就是字符串的*匹配
慢是肯定的，但SQL发明的时候，没有想到今天会有这么大的数据量。
还好，有了hadoop之类的方案，可以事先做处理，然后从缓存里查询，这样数据库本身的压力就小多了。
简单地可以用solr, elasticsearch

cjaizss 发表于 2016-12-20 09:04

没好算法

wlmqgzm 发表于 2016-12-26 16:09

数据库里面的like这个操作，分多种情况：
１）如果like的字段有索引，并且是前缀模式，类似like 'abcd%', 　那么将会在索引上执行　查找　 >=abcd\0 并且<=abcd\255
执行会很快，非常快
２）如果like的字段有索引，但是其他模式，例如：like '%abcd%'部分数据库会先在索引中全扫描，扫描后再到实际表中处理，速度要慢很多, 但是也比全表扫描要快。
３）部分数据库只做全表扫描，很慢。
页: [1] 2
查看完整版本: 数据库里面的like这个操作是使用什么算法实现的，计算复杂性如何？