ElasticSearch搜索引擎之倒排索引及其底层算法

一、搜索引擎

1、什么是搜索引擎？

搜索引擎就是根据用户需求与一定算法，运用特定策略从互联网检索出制定信息反馈给用户的一门检索技术。如网络爬虫技术、检索排序技术、网页处理技术、大数据处理技术、自然语言处理技术等。
—百度百科

2、搜索引擎的分类

搜索引擎分类一般是按搜索方式分类的：

• 全文搜索引擎：一般是在没有明确检索意图情况下进行的索引，这种搜索方式方便、简捷，并容易获得所有相关信息，但搜索到的信息过于庞杂。例如：百度、搜狗、谷歌等
• 元搜索引擎：不同的搜索引擎性能及其信息反馈能力各有不同。而元搜索引擎就是利用其他搜索引擎之间的优势互补进行搜索的。
• 垂直搜索引擎：有明确搜索意图的情况下进行的检索。例如：汽车之家、小米有品。
• 目录搜索引擎：一般是网站内部常用的检索方式。

3、常用的搜索引擎

对于程序员来说，搜索引擎可是开发面试中经常碰到的。例如：Lucene、Nutch、ElasticSearch、Solandra、IndexTank、Compass、Solr、LIRE、Egothor等等。

4、搜索引擎的特点

• 快：他们都有高效的压缩算法，能够快速编码解码。
• 准确：查询的信息准确率比较高。
• 召回率高
  • 底层算法采用了FOR压缩算法跟RBM算法。解决了速度问题。
  • 底层采用了使用了BM25和TF-IDF算法。提高了准确率和召回率。例如：ElasticSearch、Lucene使用了倒排索引，最底层的算法是FOR压缩算法跟RBM算法。

二、倒排索引

1、简介

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。[百度百科]
啥意思？意思是，倒排索引是专门用来通过文件或字符串进行定位文件位置的索引。也就是通过字符串或者是文件内容来搜索文件的索引。

2、为什么倒排索引不用B+树

说起这个，就要不得不提一下数据库的索引，数据库的索引大家都知道，底层数据结构大都是B树或者是B+树。
拿mysql为例，一张数据表：

id	goods_name	……
1	小米	……
2	小米至尊纪念版	……
3	小米 NFC 手机	……
4	蓝牙耳机	……
5	小米耳机	……

1.创建时间长，文件大。

分别以id建立索引和goods_name建立索引。通过B+的数据结构，能够发现，B+树存储索引信息了，当咱们以goods_name建立索引就会发现，索引文件会特大。当咱们的索引字段数据越多那索引文件就会越大。建立索引时间也就越长。
别忘了，goods_name这只是咱们制造的数据，一般倒排索引建立索引的字段都是大型文本。

2.其次，树深，IO次数可怕。

随着数据越多，比起规律的id字段，goods_name字段数据长度不一致，为了不增加索引树的深度，也就意味，需要增加分支数量。分支数量一多，那就意味每层树的IO判断增加，效率反而下降。极端下，可能会出现层数N*分支数量M的次数IO读写。

3.索引可能会失效。

4.精准度差。

由此可见