一. 为什么不使用MySQL？
MySQL只适用于结构化数据的检索，而不适用于全文检索，全文检索简单来说就是要在大量文档中找出包含某个单词的所有文档
那么什么叫做全文检索呢？
数据总体分为：
● 结构化数据：指具有固定格式或有限长度的数据，如数据库，元数据等。
● 非结构化数据：指不定长或无固定格式的数据，如邮件，word文档等。
● 半结构化数据：如XML，HTML等，根据需要可按结构化数据来处理，也可抽取出纯文本按非结构化数据来处理。
非结构化数据又一种叫法叫全文数据。
比如我们想从海量的商品数据中，想检索包含“自行车”的所有商品，在MySQL中可能会想用like:
select * from item where name like '%自行车%'
但是熟悉MySQL innoDB存储引擎的同学都知道，由于B+树索引是是按照「索引值」有序排列存储的，只能根据前缀进行比较，也就是最左匹配原则，所以这个左右模糊匹配不会走索引，也就是会全表扫描，查询效率就会很低
此外，使用MySQL的缺点有：
● 搜索效果差，只能首尾位模糊匹配，无法实现复杂的搜索需求
● 无法使用数据库索引，需要全表扫描，性能差
● 无法得到文档与搜索条件的相关性
所以需要创建一种高效的索引结构来支持全文检索。
二. 如何创建索引
传统上，我们去查找一篇文章中的某个单词，这个过程是文档-->单词的映射，而我们现在的需求是：想在海量文档中，找出包含特定单词的所有文档，也即已知单词，欲求文档，也即从单词-->文件的映射，两者恰恰相反。于是如果索引总能够保存从字符串到文件的映射，则会大大提高搜索速度。
由于从单词-->文件的map是文档-->单词的map的反向过程，于是保存这种信息的索引称为反向索引，也是倒排索引。
目前主流的索引方式都是倒排索引，倒排索引是区别于正排索引的概念：
● 正排索引：是以文档对象的唯一 ID 作为索引，以文档内容作为记录的结构。
● 倒排索引：Inverted index，指的是将文档内容中的单词作为索引，将包含该词的文档 ID 作为记录的结构。
因此，要构建索引，首先需要处理我们的文档，真实情况下涉及自然语言处理(NLP)，这里简单说一下过程：
假设我们有两个文档(Documents)：
文档一：This is some nice cars, My friend want to buy one car.
文档二: My friend drove me to buy it in his red car
（1）分词-Tokenize
分词主要做以下工作：
- 将文档分成一个一个单独的单词。
- 去除标点符号。
- 去除停词(Stop word)。停词(Stop word)指语言中最普通的一些单词，没有特别的意义，大多数情况下不能成为搜索的关键词，如“the”, “a”，“this”等。
分词处理完的结果称为Token，比如在本例中处理完的结果为：
nice，cars，want，buy，My，friend，My，friend，drove，me，buy，his，red，car
（2）词项处理-Linguistic Processor
这一步骤主要做以下工作： - 归一化：将所有英语单词转小写，并且归一
○ USA - U.S.A. [缩写]
○ 7月30日 - 7/30 [中英文]
○ color - colour [通假词]
○ 开心 - 高兴 [同义词扩展范畴] - 词形归并：比如car, cars, car's, cars' -> car
- 词根还原：比如driven，drove，driving -> drive
经过上面处理后的结果称为Term：
nice，car，want，buy，friend，drive，buy，he，red, car, my
（3）索引构建-Indexing
这一步骤主要做以下工作： - 利用得到的词(Term)创建一个字典。
- 对字典按字母顺序进行排序。
- 合并相同的词(Term)成为文档倒排(Posting List)链表。
Term Doc id
buy 1, 2
car 1, 2
drive 2
friend 1，2
he 2
my 1，2
nice 1
red 2
want 1
根据倒排索引的概念，我们可以用一个 Map来简单描述这个结构。这个 Map 的 Key 的即是分词后的单词Term，这一系列的 Term 组成了倒排索引的第一个部分 —— Term Dictionary (索引表，可简称为 Dictionary)。
倒排索引的另一部分为 Postings List（记录表），也对应上述 Map 结构的 Value 部分集合。
除此之外，在此表中，有几个定义：
● Document Frequency 即文档频次，表示总共有多少文件包含此词(Term)。
● Frequency 即词频率，表示此文件中包含了几个此词(Term)。
所以对词(Term) “car”来讲，总共有两篇文档包含此词(Term)，从而词(Term)后面的文档链表总共有两项，第一项表示包含“car”的第一篇文档，即1号文档，此文档中，“car”出现了2次，第二项表示包含“car”的第二个文档，是2号文档，此文档中，“car”出现了1次，到此为止，索引已经创建好了。
三. 如何进行搜索
搜索主要分为以下几步：
第一步：用户输入查询语句。
举个例子，用户输入语句：car AND buy NOT drive。
说明用户想找一个包含car和buy然而不包括drive的文档。
第二步：词法分析&语法分析
主要是识别token和关键字，经过词法分析后：
token：car, drive, buy
关键字：AND NOT
构建语法树：
第三步：搜索索引，得到符合语法树的文档。
此步骤有分几小步：
-
首先，在反向索引表中，分别找出包含car，drive，buy的文档链表。
-
其次，对包含car，buy的链表进行合并操作，得到既包含car又包含buy的文档链表。
-
然后，将此链表与drive的文档链表进行差操作，去除包含drive的文档，从而得到既包含car又包含buy而且不包含drive的文档链表。
-
此文档链表就是我们要找的文档：doc1。
第四步：根据得到的文档和查询语句的相关性，对结果进行排序。
向量空间模型的算法(Vector Space Model)
- 计算权重(Term weight)的过程。
影响一个词(Term)在一篇文档中的重要性主要有两个因素：
● Term Frequency (tf)：即此Term在此文档中出现了多少次。tf 越大说明越重要。
● Document Frequency (df)：即有多少文档包含次Term。df 越大说明越不重要。
term的权重公式为：
$w_{t, d}=t f_{t, d} \times \log \left(n / d f_{t}\right)$
● w(t,d)是term t在文档d 中的权重
● tf(t,d)是term t在文档d中的出现次数
● n是总文档数
● df(t)是包含term t的文档数
- 相关性打分
文档由一系列词(Term)组成，每一个词(Term)都有一个权重(Term weight)，不同的词(Term)根据自己在文档中的权重来影响文档相关性的打分计算。
我们把所有此文档中词(term)的权重(term weight) 看作一个向量。
$Document = <term1, term2, …… ,term N>$
$Document Vector = <weight1, weight2, …… ,weight N>$
同样我们把查询语句看作一个简单的文档，也用向量来表示。
$Query = <term1, term 2, …… , term N>$
$Query Vector = <weight1, weight2, …… , weight N>$
我们把所有搜索出的文档向量及查询向量放到一个N维空间中，每个词(term)是一维。
通过 计算夹角的余弦值作为相关性的打分，夹角越小，余弦值越大，打分越高，相关性越大。
相关性打分公式为
$\operatorname{score}(q, d)=\frac{\vec{V}{q} \cdot \vec{V}{d}}{\left|\vec{V}{q}\right|\left|\vec{V}\right|}=\frac{\sum_{i=1}^{n} w_{i, q} w_{i, d}}{\sqrt{\sum_{i=1}^{n} w_{i, q}^{2}} \sqrt{\sum_{i=1}^{n} w_{i, d}^{2}}}$
然后返回相关性最高的文档给用户即可。向量空间模型采用统计学方法，将文档和查询信息表示为向量，实现了相关性排序，但是它的缺点是假设了关键词之间彼此独立，实际上用户一个搜索请求背后的逻辑往往不是这么简单。比如还有BM25算法
$\operatorname{Score}(Q, d)=\sum_{i}^{n} \operatorname{IDF}\left(q_{i}\right) \cdot \frac{f_{i} \cdot\left(k_{1}+1\right)}{f_{i}+k_{1} \cdot\left(1-b+b \cdot \frac{d l}{\text { avgdl }}\right)}$
四. 空间索引
GeoHash
如何知道离自己50m的范围内的所有餐馆？
传统暴力做法：使用精度与纬度，利用球面距离公式，计算地球上所有POI与自己的距离，然后保留距离<50m的POI
GeoHash，根据经纬度进行二分，然后编码，举例北海公园的经纬度是(39.928167, 116.389550)
以纬度为例，经度不再赘述：
bit min mid max
1 -90.000 0.000 90.000
0 0.000 45.000 90.000
1 0.000 22.500 45.000
1 22.500 33.750 45.000
1 33.7500 39.375 45.000
0 39.375 42.188 45.000
0 39.375 40.7815 42.188
0 39.375 40.07825 40.7815
1 39.375 39.726625 40.07825
1 39.726625 39.9024375 40.07825
通过上述计算，
纬度产生的编码为10111 00011，
经度产生的编码为11010 01011。
偶数位放经度，奇数位放纬度，把2串编码组合生成新串：11100 11101 00100 01111。
最后使用用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，首先将11100 11101 00100 01111转成十进制，对应着28、29、4、15，十进制对应的编码就是wx4g。
● GeoHash将二维的经纬度转换成字符串
● 字符串越长，表示的范围越精确
● 字符串相似的表示距离相近
KD Tree
KD Tree是 k-Dimension Tree，以k=2，2维举例。
设想一下，平面上有100万个点，给定一个特定点，如何求距离这个点最近的100个点？
传统做法：
同样暴力求解
KD Tree做法：
二维样例：{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}
首先对数据按X轴排序，取中位数划分，会有一些点落在左边分支/右边分支
然后对数据按Y轴排序，取中位数划分......
......
直到每个空间只剩1个点 / 0个点，然后建树
最邻近检索的步骤为：
- 从根节点开始，X层比较x坐标，Y层比较y坐标，类似二叉树搜索，直至叶节点
- 记录叶节点的欧式距离d，然后回溯，直至X，Y均大于d
- 回溯主要是，当前节点所在切分轴与对应的坐标的距离如果小于d，那么很有可能在另一个分支存在更近的点，搜索另一个分支，若存在，更新d
举个例子，查找（6，3.5）
- 先查到（2，3），计算d = 4.03
- 回溯到（5，4），y轴距离 = 4 - 3.5 = 0.5 < d，说明下面（包含）可能存在距离更近的，计算当前点（5，4）的距离，d = 1.18 < 4.03 更新d
- 回溯到 （7，2），x轴距离 = 7 - 6 = 1 < d，右侧可能存在更近，计算当前点（7，2）的距离，d = 1.802 > 1.18，右侧不存在，结束搜索。
五. 优化
以开源搜索引擎Lucene为例
数据压缩
PackedBlock
其采用 PackedInts 结构将一个 int[] 压缩打包成一个紧凑的 Block。它的压缩方式是取数组中最大值所占用的 bit 长度作为一个预算的长度，然后将数组每个元素按这个长度进行截取，以达到压缩的目的。
例如：一个包含128个元素的 int 数组中最大值的是 2，那么预算长度为2个 bit, PackedInts 的长度仅是 2 * 128 / 8 = 32个字节，然后就可以通过4个 long 值存储。
VIntBlock
VIntBlock 是采用 VInt 来压缩 int 值，对于绝大多数语言，int 型都占4个字节，不论这个数据是1、100、1000、还是1000,000。VInt 采用可变长的字节来表示一个整数。数值较大的数，使用较多的字节来表示，数值较少的数，使用较少的字节来表示。每个字节仅使用第1至第7位(共7 bits)存储数据，第8位作为标识，表示是否需要继续读取下一个字节。
举个例子：
整数130为 int 类型时需要4个字节，转换成 VInt 后仅用2个字节，其中第一个字节的第8位为1，标识需要继续读取第二个字节。
SkipData
为了能够快速查找docid，lucene采用了SkipList这一数据结构。SkipList有以下几个特征：
- 元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大;
- 跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是;
- SkipList的层次，这个是指整个SkipList有几层
时间复杂度log(n)
FST
使用lucene进行查询不可避免都会使用到其提供的字典功能，即根据给定的term找到该term所对应的倒排文档id列表等信息。
怎么实现一个字典呢？我们马上想到排序数组，即term字典是一个已经按字母顺序排序好的数组，数组每一项存放着term和对应的倒排文档id列表。每次载入索引的时候只要将term数组载入内存，通过二分查找即可。排序数组的缺点是消耗内存，即需要完整存储每一个term，当term数目多达上千万时，占用的内存将不可接受。
lucene从4开始大量使用的数据结构是FST（Finite State Transducer）。FST有两个优点：
1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；
2）查询速度快。O(len(str))的查询时间复杂度。
其实和Tries（字典树）我想是类似的
KDB Tree
KDB-tree(k-dimensional B-tree)是一个用于划分K维搜索空间的树形结构，KDB-tree的既提供平衡KD树的搜索效率，又有B树面向块的存储来优化外部内存的访问效率。
结构
KDB-tree包括两种类型的页:
● 区域页面: (region, child)对的集合包含边界区域的描述，加上该区域指向子页面的指针。
● 点页面:(point, location)对的集合。数据库方面，location可能指向数据库记录的索引，对于K维空间中的点，可以被看成该空间中的点坐标。
六. 进一步学习
(1) ha3还有更多索引：截断索引 ，实时索引 ，向量索引
达摩院向量检索Proxima
FaceBook Faiss
(2) indexlib--KKV 索引
KKV模型（PKey-SKey-Value）通常用来存储属性图中的关系实例（如图1中的好友关系），其中PKey(primary key)存储一条边的源节点ID(上图中节点U1)，SKey(secondary key)存储一条边的目标节点ID(比如上图中节点U2/U3/U4)，Value用来存放关系的属性(比如好友关系的time和score属性)。
(3) 更多检索技术
七. 参考文献
GeoHash
KD Tree
浅谈搜索引擎