目录

概述

存储数据到 Elasticsearch 的行为叫做 索引.

一个 Elasticsearch 集群可以 包含多个 索引 ,相应的每个索引可以包含多个 类型 。 这些不同的类型存储着多个 文档 ,每个文档又有 多个 属性 。

索引 这个词在 Elasticsearch 语境中包含多重意思, 所以有必要做一点儿说明:

  • 索引(名词)

如前所述,一个 索引 类似于传统关系数据库中的一个 数据库 ,是一个存储关系型文档的地方。 索引 (index) 的复数词为 indices 或 indexes 。

  • 索引(动词)

索引一个文档 就是存储一个文档到一个 索引 (名词)中以便它可以被检索和查询到。这非常类似于 SQL 语句中的 INSERT 关键词,除了文档已存在时新文档会替换旧文档情况之外。

  • 倒排索引

关系型数据库通过增加一个 索引 比如一个 B树(B-tree)索引 到指定的列上,以便提升数据检索速度。Elasticsearch 和 Lucene 使用了一个叫做 倒排索引 的结构来达到相同的目的。

默认的,一个文档中的每一个属性都是 被索引 的(有一个倒排索引)和可搜索的。一个没有倒排索引的属性是不能被搜索到的。

倒排索引

倒排索引是搜索引擎中最为核心的一项技术之一,可以说是搜索引擎的基石。可以说正是有了倒排索引技术,搜索引擎才能有效率的进行数据库查找、删除等操作。

倒排索引的思想

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。

  在搜索引擎中,查询词可以切分成若干个单词,所以对于搜索引擎中的倒排索引对应的属性就是单词,而对应的记录就是网页(也可以广泛地称为是文档)。所以,搜索引擎中的倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词(属性)快速获取包含这个单词的文档列表(记录)。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

单词-文档矩阵

搜索引擎通常检索的场景是:给定几个关键词,找出包含关键词的文档。 怎么快速找到包含某个关键词的文档就成为搜索的关键。这里我们借助单词——文档矩阵模型, 通过这个模型我们可以很方便知道某篇文档包含哪些关键词,某个关键词被哪些文档所包含。

单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,下图展示了其含义。图中的每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系:

单词-文档矩阵

从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其它单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过单词1,而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。

搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式。

倒排索引的基本框架

  • 单词和单词字典
    搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

  • 倒排列表
    倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。

  • 倒排文件
    所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

搜索引擎中倒排索引大概流程框架:用户在搜索引擎搜索框输入查询词进行搜索时,搜索引擎会对查询词进行切词以及近义词匹配等操作,根据原始查询词得到一系列的单词列表。然后根据搜索引擎内部的字典来查询每个单词对应的倒排列表,从而定位到包含这个单词的网页或者说是文档。最后搜索引擎根据特定的网页排序算法将查询到的网页进行排序,通过前端将搜索结果展示给用户。下图为倒排索引的主要流程:

倒排索引流程框架

单词字典

倒排索引的关键技术在于建立单词字典。

单词词典用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。

对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构(哈希存储的拉链法)和树形词典结构。

哈希拉链法

哈希拉链法词典结构

词典结构主要由两个部分构成:

  主体部分是哈希表,每个哈希表项保存一个指针,指针指向冲突链表,在冲突链表里,相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词获得相同的哈希值,如果是这样,在哈希方法里被称做是一次冲突,可以将相同哈希值的单词存储在链表里,以供后续查找。

在建立索引的过程中,词典结构也会相应地被构建出来。比如在解析一个新文档的时候,对于某个在文档中出现的单词T,首先利用哈希函数获得其哈希值,之后根据哈希值对应的哈希表项读取其中保存的指针,就找到了对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词,说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,相应的词典结构也就建立起来了。

在响应用户查询请求时,其过程与建立词典类似,不同点在于即使词典里没出现过某个单词,也不会添加到词典内。以上图为例,假设用户输入的查询请求为单词X,对这个单词进行哈希,定位到哈希表内的4号槽,从其保留的指针可以获得冲突链表,依次将单词X和冲突链表内的单词比较,发现单词X在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的倒排列表来进行后续的工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

树形结构

B树(或者B+树)是另外一种高效查找结构。B树与哈希方式查找不同,需要字典项能够按照大小排序(数字或者字符序),而哈希方式则无须数据满足此项要求。

  B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用,最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。

实例说明

一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的文档列表。

例如,假设我们有两个文档,每个文档的 content 域包含如下内容:

The quick brown fox jumped over the lazy dog
Quick brown foxes leap over lazy dogs in summer 

为了创建倒排索引,我们首先将每个文档的 content 域拆分成单独的 词(我们称它为 词条 或 tokens ),创建一个包含所有不重复词条的排序列表,然后列出每个词条出现在哪个文档。结果如下所示:

Term Doc_1 Doc_2
Quick X
The X
brown X X
dog X
dogs X
fox X
foxes X
in X
jumped X
lazy X X
leap X
over X X
quick X
summer X
the X

现在,如果我们想搜索 quick brown ,我们只需要查找包含每个词条的文档:

Term Doc_1 Doc_2
brown X X
quick X
——- —– —–
Total 2 1

两个文档都匹配,但是第一个文档比第二个匹配度更高。如果我们使用仅计算匹配词条数量的简单 相似性算法 ,那么,我们可以说,对于我们查询的相关性来讲,第一个文档比第二个文档更佳。

但是,我们目前的倒排索引有一些问题:

  • Quick 和 quick 以独立的词条出现,然而用户可能认为它们是相同的词。
  • fox 和 foxes 非常相似, 就像 dog 和 dogs ;他们有相同的词根。
  • jumped 和 leap, 尽管没有相同的词根,但他们的意思很相近。他们是同义词。

使用前面的索引搜索 +Quick +fox 不会得到任何匹配文档。(记住,+ 前缀表明这个词必须存在。)只有同时出现 Quick 和 fox 的文档才满足这个查询条件,但是第一个文档包含 quick fox ,第二个文档包含 Quick foxes 。

我们的用户可以合理的期望两个文档与查询匹配。我们可以做的更好。

如果我们将词条规范为标准模式,那么我们可以找到与用户搜索的词条不完全一致,但具有足够相关性的文档。例如:

  • Quick 可以小写化为 quick 。
  • foxes 可以 词干提取 –变为词根的格式– 为 fox 。类似的, dogs 可以为提取为 dog 。
  • jumped 和 leap 是同义词,可以索引为相同的单词 jump 。

现在索引看上去像这样:

Term Doc_1 Doc_2
brown X X
dog X X
fox X X
in X
jump X X
lazy X X
over X X
quick X X
summer X
the X X

这还远远不够。我们搜索 +Quick +fox 仍然 会失败,因为在我们的索引中,已经没有 Quick 了。但是,如果我们对搜索的字符串使用与 content 域相同的标准化规则,会变成查询 +quick +fox ,这样两个文档都会匹配!

分析与分析器

分析 包含下面的过程:

  • 首先,将一块文本分成适合于倒排索引的独立的 词条 ,
  • 之后,将这些词条统一化为标准格式以提高它们的“可搜索性”,或者 recall

分析器执行上面的工作。 分析器 实际上是将三个功能封装到了一个包里:

字符过滤器
首先,字符串按顺序通过每个 字符过滤器 。他们的任务是在分词前整理字符串。一个字符过滤器可以用来去掉HTML,或者将 & 转化成 and分词器
其次,字符串被 分词器 分为单个的词条。一个简单的分词器遇到空格和标点的时候,可能会将文本拆分成词条。 Token 过滤器
最后,词条按顺序通过每个 token 过滤器 。这个过程可能会改变词条(例如,小写化 Quick ),删除词条(例如, 像 aandthe 等无用词),或者增加词条(例如,像 jump 和 leap 这种同义词)。

Elasticsearch提供了开箱即用的字符过滤器、分词器和token 过滤器。 这些可以组合起来形成自定义的分析器以用于不同的目的。

内置分析器

Elasticsearch还附带了可以直接使用的预包装的分析器。 接下来我们会列出最重要的分析器。为了证明它们的差异,我们看看每个分析器会从下面的字符串得到哪些词条:

Set the shape to semi-transparent by calling set_trans(5)

标准分析器

标准分析器是Elasticsearch默认使用的分析器。它是分析各种语言文本最常用的选择。它根据 Unicode 联盟 定义的 单词边界 划分文本。删除绝大部分标点。最后,将词条小写。它会产生

set, the, shape, to, semi, transparent, by, calling, set_trans, 5

简单分析器

简单分析器在任何不是字母的地方分隔文本,将词条小写。它会产生

set, the, shape, to, semi, transparent, by, calling, set, trans

空格分析器

空格分析器在空格的地方划分文本。它会产生

Set, the, shape, to, semi-transparent, by, calling, set_trans(5)

语言分析器

特定语言分析器可用于 很多语言。它们可以考虑指定语言的特点。例如, 英语 分析器附带了一组英语无用词(常用单词,例如 and 或者 the ,它们对相关性没有多少影响),它们会被删除。 由于理解英语语法的规则,这个分词器可以提取英语单词的 词干 。

英语 分词器会产生下面的词条:

set, shape, semi, transpar, call, set_tran, 5

注意看 transparentcallingset_trans 已经变为词根格式。

什么时候使用分析器

当我们 索引 一个文档,它的全文域被分析成词条以用来创建倒排索引。 但是,当我们在全文域 搜索 的时候,我们需要将查询字符串通过 相同的分析过程 ,以保证我们搜索的词条格式与索引中的词条格式一致。

全文查询,理解每个域是如何定义的,因此它们可以做 正确的事:

  • 当你查询一个 全文 域时, 会对查询字符串应用相同的分析器,以产生正确的搜索词条列表。
  • 当你查询一个 精确值 域时,不会分析查询字符串, 而是搜索你指定的精确值。

现在你可以理解在下面的查询为什么返回那样的结果:

  • date 域包含一个精确值:单独的词条 2014-09-15
  • _all 域是一个全文域,所以分词进程将日期转化为三个词条: 201409, 和 15

当我们在 _all 域查询 2014,它匹配所有的12条推文,因为它们都含有 2014

GET /_search?q=2014              # 12 results

当我们在 _all 域查询 2014-09-15,它首先分析查询字符串,产生匹配 201409, 或 15 中 任意 词条的查询。这也会匹配所有12条推文,因为它们都含有 2014

GET /_search?q=2014-09-15        # 12 results !

当我们在 date 域查询 2014-09-15,它寻找 精确 日期,只找到一个推文:

GET /_search?q=date:2014-09-15   # 1  result

当我们在 date 域查询 2014,它找不到任何文档,因为没有文档含有这个精确日志:

GET /_search?q=date:2014         # 0  results !

参考目录

  1. 倒排索引
  2. 搜索引擎技术之倒排索引
  3. 倒排索引原理和实现
  4. 正排索引(forward index)与倒排索引(inverted index)