ElasticSearch系列 - 倒排索引

Love The Way You Lie 2024-04-18 19:43 84阅读 0赞

### 文章目录 ###

*   *   *   *  ElasticSearch系列 - 倒排索引
             *   *  倒排索引
                 *  ElasticSearch 索引结构概述
                 *  ElasticSearch 索引原理

#### ElasticSearch系列 - 倒排索引 ####

##### 倒排索引 #####

MySQL是存储结构化数据的数据库，所以MySQL中的索引是正向索引，key->value,需要注意的是，MySQL中的scheme定义了表的结构，我们定义B-tree索引也只能定义在表字段上，从某种意义上来说，索引是确定值的类型以及可能出现的范围。

但是，编程中，不可能只有结构化数据，更多的数据是非结构化，即无法定义一种存储格式存储，数据格式多变。例如一本书，我需要找到Java出现在那页，这是MySQL中的B-tree索引做不到的。value，key，value代表本身Java就是内容一部分，Key代表页码，如果是正向索引：知道页码找Java很好找，但是知道Java找页码确不行。小时候用过字典的人知道，一本书最前面有目录，记录了单词出现的页码。这就是倒排索引。

##### ElasticSearch 索引结构概述 #####

curl -X PUT "localhost:9200/user/_doc/1" -H 'Content-Type: application/json' -d'
    {
        
        "username" : "Java",
        "age" : 20,
        "context":"java is nice"
    }

使用上述这条命令之后，在插入这些数据到索引的同时，Elasticsearch还为这些字段建立索引——倒排索引，因为Elasticsearch最核心功能是搜索。

ElasticSearch索引分为如下几个部分组成

![\[外链图片转存失败(img-9kSbH73W-1568169067289)(/Users/aaron/Library/Application Support/typora-user-images/image-20190910110020631.png)\]][img-9kSbH73W-1568169067289_Users_aaron_Library_Application Support_typora-user-images_image-20190910110020631.png]

**Term Index** ：单词索引

**Term Dictionary** ：字典（单词集合）

**Posting List** ：倒排列表

假设目前ElasticSearch中有如下数据，为了形象表示，使用Mysql来显示

<table> 
 <thead> 
  <tr> 
   <th>username</th> 
   <th>age</th> 
   <th>context</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>java</td> 
   <td>40</td> 
   <td>java is nice</td> 
  </tr> 
  <tr> 
   <td>c++</td> 
   <td>50</td> 
   <td>c++ is good</td> 
  </tr> 
  <tr> 
   <td>python</td> 
   <td>10</td> 
   <td>python is niubi</td> 
  </tr> 
 </tbody> 
</table>

我们知道，在往ElasticSearch中插入数据时，会自动为每个字段建立索引（除非手动设置忽略这个字段）。

例如context，context中是一个字符串，ElasticSearch会先进行分词。

java，is，nice，c++，good，niubi，python。这些统称为**Term**（单词）

然后为其建立**Term Dictionary**

再然后构建**Posting List**，其大概结构如下所示

<table> 
 <thead> 
  <tr> 
   <th>term id</th> 
   <th>term</th> 
   <th>文档频率</th> 
   <th>Posting List（doc,TF,Position,offset）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>java</td> 
   <td>1</td> 
   <td>(1,1,0,&lt;0,4&gt;)</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>is</td> 
   <td>3</td> 
   <td>(1,1,1,&lt;6,7&gt;),(2,1,1,&lt;5,6&gt;),(3,1,1,&lt;8,9&gt;)</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>nice</td> 
   <td>1</td> 
   <td>(1,1,2,&lt;9,12&gt;)</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>c++</td> 
   <td>1</td> 
   <td>(2,1,0,&lt;0,3&gt;)</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>good</td> 
   <td>1</td> 
   <td>(2,1,2,&lt;8,11&gt;)</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>niubi</td> 
   <td>1</td> 
   <td>(3,1,3,&lt;11,15&gt;)</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>python</td> 
   <td>1</td> 
   <td>(3,1,0,&lt;0,5&gt;)</td> 
  </tr> 
 </tbody> 
</table>

**PS:posting List只有一列，前面两个只是为了方便阅读，后续会给出物理结构图**

doc = 文档id

TF = 词频，该单词在该文档中出现次数，用于相关性打分

文档频率 = 全部文档中的频率

postion = 单词在文档中的位置，用于语句搜索

offset = 记录单词的开始结束位置，实现高亮显示

##### ElasticSearch 索引原理 #####

通过上面了解，我们知道倒排索引存储了，单词->文档id，这种类型结构，知道文档id我们就能快速检索出所需文档，那么我们怎么快速找到单词Term呢？

遍历？

我们都知道ElasticSearch使用在海量数据的检索，那么势必存储大量的文档，而这些文档经过分词器分词，又将产生大量的Term，这些单词是存储在Term Dictionary中的，那么如果遍历的话，这种消耗是无法接受的。

还有什么办法呢？

可以先对 Term 进行排序，然后使用二分检索呢，LogN的复杂度，最多LogN次磁盘随机读取。但是磁盘的随机读操作仍然是非常昂贵的（一次 random access 大概需要 10ms 的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个 term dictionary 本身又太大了，无法完整地放到内存里。于是就有了**term index**。

什么是Term Index？

Term index 是一棵 trie 树

ElasticSearch的做法是首先为Term Dictionary建立索引。

![\[外链图片转存失败(img-qu7Ndcpt-1568169067290)(/Users/aaron/Library/Application Support/typora-user-images/image-20190911101654113.png)\]][img-qu7Ndcpt-1568169067290_Users_aaron_Library_Application Support_typora-user-images_image-20190911101654113.png]

例子是一个包含 “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, 和 “inn” 的 trie 树。这棵树不会包含所有的 term，它包含的是 term 的一些前缀（相同前缀的term会在磁盘同一个block中，磁盘读取是读取一整块）。通过 term index 可以快速地定位到 term dictionary 的某个 block，然后从这个位置再往后顺序查找。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。

![\[外链图片转存失败(img-Zh0VK80u-1568169067291)(/Users/aaron/Library/Application Support/typora-user-images/image-20190911101805647.png)\]][img-Zh0VK80u-1568169067291_Users_aaron_Library_Application Support_typora-user-images_image-20190911101805647.png]

Term Index是在内存中，通过Term Index 去磁盘中找到一个单词，通过这个单词在磁盘中找到对应的posting List

如此就完成了一次检索

[img-9kSbH73W-1568169067289_Users_aaron_Library_Application Support_typora-user-images_image-20190910110020631.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ce495c3c5f4f42ecb5d612bf368a5996.png
[img-qu7Ndcpt-1568169067290_Users_aaron_Library_Application Support_typora-user-images_image-20190911101654113.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5bd038cdfaf84d29a08504a0d334f045.png
[img-Zh0VK80u-1568169067291_Users_aaron_Library_Application Support_typora-user-images_image-20190911101805647.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/624f78328be3411dad3969aee76c3d06.png