【无标题】

普通检索

       类比一下图书馆找书的例子,想要从中找到一本书,当我们没有任何印象放在哪里时,我们可能会从左往右挨个查找。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kV1wKgxd-1662299737090)(/upload/2022/09/2560px-HK_Shek_Tong_Tsui_Public_Library_%E7%9F%B3%E5%A1%98%E5%92%80%E5%85%AC%E7%9C%BE%E5%9C%96%E6%9B%B8%E9%A4%A8_Bookcase_Learning_reference_book_back_Oct-2010-2a46f14299834ed1aa14d2c0128c3873.jpg)]

       这样做的效率非常低,当书特别多时,我们想要找到目标书的难度会大大增大。为了让用户更加方便地找到书,有些图书馆可能会将书籍按名称字典序排序,并且设立标志,例如A开头的放第一排,B开头的放第二排,这样用户通过首字母开头便可以定位到大致的搜索范围,这就是索引的基本原理:通过缩小范围来提高效率。

普通检索的弊端

       上述例子是顺序查找,在mysql中,使用的是二分查找,它使用了b+树作为索引的数据结构。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YiDBYr7Z-1662299737092)(/upload/2022/09/%E7%BB%98%E5%9B%BE1-a2e79b1e881d4a73882f3ee121663e7b.jpg)]

       在上图中,一个大的方框代表一页数据,连线代表一次IO查找,在上述例子中,仅需要最多三次IO便可以查找到任何一个目标数据。虽然b+树索引能够大大提供搜索效率,但是它仅支持前缀匹配,对于后缀模糊查询就无能为力了。最重要的是,B+树索引是对完整的数据建立索引,即字段的整体值作为排序,如果存储的是文章,那么则会把整篇文章用来二分查找,检索效率非常低。因此Mysql对字符串索引长度作了限制,并且text类型只能建立前缀索引,长度不能超过767 bytes。

       对于很多搜索场景而言,精准匹配不是特别重要,重要的是返回足够多的满足用户诉求的结果。 例如:从大量的文章中搜索包含“炸鸡”的文章,如果是普通检索,由于普通索引仅支持前缀匹配,因此搜索退化到不能使用索引的情况,即全表扫描,因此效率会非常低下。为了解决这个问题,全文检索出现了。

全文检索

       全文检索的场景是根据用户输入的关键字,查找包含这些关键字的文档,常用的全文检索引擎有ElasticSearch、Lucene,以及Mysql的myisam引擎也支持全文检索。
       目前业界广泛使用的全文搜索引擎——ElasticSearch,它是典型的非关系型数据库,为了从海量文章中匹配出目标关键字,全文检索使用的关键技术是倒排索引

倒排索引

       倒排索引的基本思想是:将文档按照一定规则分词,然后再将词汇和文档的关系保存,最后对词汇建立索引。检索时,先将搜索内容进行分词,再通过索引查找对应的文档。

       举个例子,现在有文章A和B,
       A:我正在学习ElasticSearch。
       B:我要去图书馆学习了。
       对它们建立倒排索引:

       [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z6F8rTxR-1662299737093)(/upload/2022/09/image-c127268a2fe74376a2f312ed7c3420ac.png)]
       对两份文档的分词结果共出现8个词汇(根据不同的分词规则分词数量、结果可能不一致),上述就是简单的倒排索引表模型。利用此倒排索引,当用户输入“学习”关键字时,可以从索引表中快速找到有文档A和B满足要求。

倒排的含义

       倒排索引英文名为Inverted Index,我一直觉得中文翻译不太好,应该称为逆索引。有人说正排索引是通过主键找其他字段,而倒排索引则是通过其他字段找主键,但实质上Mysql也可以对任何字段建立索引,并指向主键,因此其实从这个区分上来讲,只要不是对主键建立的索引都可以称为“倒排”索引,这个解释明显有点牵强。
       虽然Mysql可以对除主键的其他字段建立索引,但如果要查找全部字段数据则需要回表,即对主键索引再查找一次。因此大多数情况上是通过主键查找关键数据(使用覆盖索引除外),它的核心是主键索引。倒排索引的核心是分词,并将分词结果指向文档ID(主键)。因此存在字段分词结果N->文档1的映射关系,而Mysql虽然也可以对非主键建立B+树索引,但是由于没有分词,因此只存在文档字段1->文档1的映射关系。

分词

排序


版权声明:本文为cg_Amaz1ng原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>