这是我参与「第三届青训营 -后端场」笔记创作活动的第6篇笔记

基本架构

索引层(Index)

基本概念

一个索引能够看成是一个数据库，存储了指定字段的一切文档，并提供应引擎层增修改查的接口

索引构建

选用分段的方法构建

首要设定一个阈值，比方10000篇文档，在这10000篇文档的规模内，依照第一种方法构建索引，生成一个字典文件和一个倒排文件，这一组文件叫做一个段(segment)
每10000篇文档生成一个段(segment) ，直到一切文档构建完成，然后生成了多个段，并且在查找引擎启动今后，增量数据也按这个方法进行构建，所以段会越来越多
每一个段便是索引的一部分，他有倒排索引的全部东西(词典，倒排表)，能够进行一次正常的检索操作，每次检索的时分依次查找各个段，然后把成果兼并起来便是最终成果了
假如段的数量过多，对多个段的词典和倒排文件进行多路兼并操作，由于词典是有序的，所以能够依照term的次序进行归并操作，每次归并的时分把倒排全拉出来，然后生成一个新的词典和新的倒排文件，当兼并完了今后把老的都删掉。

中心组件

索引类


type Index struct {
   Name       string      `json:"name"`
   PathName     string      `json:"pathName"`
   Fields      map[string]uint64 `json:"fields"`
   PrimaryKey    string      `json:"primaryKey"`
   StartDocId    uint64      `json:"startDocId"`
   MaxDocId     uint64      `json:"maxDocId"`
   DelDocNum     int        `json:"delDocNum"`
   NextSegmentSuffix uint64      `json:"nextSegmentSuffix"`
   SegmentNames    []string     `json:"segmentNames"`

   segments    []*segment.Segment
   memorySegment *segment.Segment
   primary    *tree.BTreeDB
   bitmap    *utils.Bitmap

   pkMap map[int64]string // 内存中的主键信息

   segmentMutex *sync.Mutex
   Logger    *utils.Log4FE `json:"-"`
}

文件组成

{indexName}.meta 这里是索引的元信息，包括索引中字段的称号，类型，也包括索引内文档的起始和停止编号
{IndexName}.bitmap 符号索引中文档状态——删去或未删去
{indexName}.pk 记载索引中主键与生成的docID的映射

增加文档

删去文档

段层(Segment)

段结构

type Segment struct {
	StartDocId  uint64            `json:"startDocId"` // 段内docId的最小值
	MaxDocId    uint64            `json:"maxDocId"` // 段内docId的最大值
	SegmentName string            `json:"segmentName"` // 段的称号，序列化时文件名的一部分
	FieldInfos  map[string]uint64 `json:"fields"` // 记载段内字段的类型信息
	Logger      *utils.Log4FE     `json:"-"`
	fields   map[string]*Field // 段内字段的
	isMemory bool              // 标识段是否在内存中
	btdb     *tree.BTreeDB     // 段的数据库，用于存储各字段的正排索引
}

基本概念

一个索引由多个段组成，段分为内存段和磁盘段，磁盘段是由内存段序列化而来，只有内存段能够新增文档，一旦内存段进行了序列化变成了磁盘段，就不再进行修改，即只读，每次新增数据时，咱们总是新建一个段来到数据进行存储，这样能够处理多线程读写冲突的问题，并且分段存储，也能够很方便的进行多线程查找。

段兼并

由于段太多会导致要查询的段太多，故会每隔一段时刻对段进行兼并

假如要删去文档，能够用 bitmap 记载被删去的文档ID，然后在段兼并的时分判别该文档是否被删去

段文件组成

段需求存储，段内文档的倒排索引，文档数据，正排索引

一个段在文件保存在一个命名为indexname_{segementNumber}的文件夹内，文件夹内包括几个文件

seg.meta 这里是段的元信息，包括段中字段的称号，类型，也包括段的文档的起始和停止编号
seg.bt 记载段中一切正排信息
{fieldName}_invert.fst 这里是段中各字段的倒排文件
{fieldName}_index.idx这是段中字段的实践数据即profile
{fieldName}_profile.pfl存储字段数据的文件,假如字段类型是字符类型就会将数据存储在.dtl中，pfl中只存储数据在.dtl文件中的偏移量。
{fieldName}_detail.dtl主是存储字符类型字段数据的文件
{fieldName}_profileindex.pfi存储字段的正排索引

上面的indexname是这个索引的称号，相当于数据库中的表名，segmentNumber是段编号，这个编号是系统生成的。

增加文档

文档如下

{“name”:”张三”,”age”:18,”introduce”:”我喜爱跑步”}

{“name”:”李四”,”age”:28,”introduce”:”我喜爱歌唱”}

对于每个文档给它分配一个doc_id,假设第一个文档的doc_id为0，第二个的为1，分配后如下

字段：name

map{“张三”:0}{“李四”:1}

stringArray[”张三”,”李四”]

字段：age

integeArray[18,28]

字段：introduce

map{“我”:0，1}{“喜爱”:0，1}{“跑步”:0}{“歌唱”:1}

stringArray[”我喜爱跑步”,”我喜爱歌唱”]

将数据耐久化到磁盘中

咱们设置一个阈值，当文档量抵达阈值时，将文档数据耐久化到磁盘中

进行耐久化的进程中

假如是倒排索引，咱们将fst和倒排链分别存储，首要将倒排链耐久化，前8个字节记载倒排链的长度，后面写入倒排链，记载每个倒排链在文件中的偏移量，之后耐久化fst，key为term,value为倒排链的偏移量。
假如是IntegerArray，咱们遍历整个数组，然后把数据写入到pfl文件中，每个数据占用8个字节。
假如是StringArray，咱们遍历整个数据，首要把value追加写入到dtl文件中，然后把文件偏移量写入到pfl文件中

字段层 (Field)

基本概念

字段表明的是一个文档有哪些特点，比方标题，内容，作者，日期等

字段有不同的类型，这些类型决定在新增文档的时分如何处理

比方对于字符串类型，咱们会给它建立倒排索引，对于日期，数值类型咱们会对它建立正排索引以便于规模过滤

倒排索引(Invert)

基本概念

把文件ID对应到关键词的映射转换为关键词到文件ID的映射，每个关键词都对应着一系列的文件，这些文件中都出现这个关键词

完成思路

构建倒排索引意图是咱们期望能够经过它快速找到包括某些内容的文档。所以构建倒排索引首要咱们需求将文档中需求构建倒排的字段内容进行分词。比方说，“今日中午吃什么”，分词后变成今日、中午、吃、什么。map的key便是分词后的成果，叫做term。value保存的便是包括这个分词的文档id集合，能够叫做倒排链。大约的结构如下：

term(关键词)	docs_id（文档编号）posting_list
Go	1
言语	1，2，3
完成	1，3
查找引擎	1，4
PHP	2
世界	2，4
最好	2，4
汇编	3
公司	4

咱们能够运用map构建倒排查询的时刻复杂度为O(1)这是十分理想的时刻复杂度，但map占用的空间十分大，在文档量大时，内存或许无法存放下map。所以咱们挑选了运用FST作为存储倒排索引的结构，FST能够充分利用term中的前缀和后缀，节省了一部分空间，查询的时刻复杂度为O(n)——n为需求的term长度，一起将倒排链存入文件中，FST存储term对应的倒排链在文件中的偏移量(offset)，这样能够进一步缩小了倒排的大小。关于倒排链的读写，咱们先对倒排链文件，用mmap将文件映射到内存中，加速文件的读写。

FST构建进程

刺进key:carrry, value：1

每个字母构成一条边，首个字母还会包括val值

刺进key:depend,value: 10

刺进key:deep,value:20

deep和前面的depend有公共的前缀，所以前面的途径相同，deep在刺进进程中，不断减去途径上的value,在需求新的途径时，将剩下的value写入，这样查询时，只要把途径上的value相加便是成果的value值。

刺进end

5. 刺进marry

兼并倒排文件

咱们运用fst对倒排进行存储，key为term,value为倒排链在文件中的偏移量，兼并时咱们能够遍历fst，遍历成果是一个term的有序数组，所以流程有点类似于兼并k个有序链表，所以选用小顶堆来进行兼并，对于不同fst中相同的key咱们需求会集处理，将key对应的倒排链进行兼并，保存进文件，再将偏移量写入新的fst中。

倒排耐久化

由于fst在value只有存储数字类型，所以倒排索引的倒排链无法直接存储在fst中，所以我先将倒排链存入另一个文件，记载倒排链在文件中的开始方位，即偏移量(offset)，并在开始方位的前8个字节写入倒排链的长度。

文件{fieldName}_invert.idx保存着倒排链，fst的key为term,value为倒排链在文件中的偏移量

比方咱们要刺进如下数据

term(关键词)	docs_id（文档编号）posting_list
Go	1，3
言语	1，2，3

我先将倒排链写入文件，大约结构如下

之后将term和term对应倒排链在idx文件中的偏移量写入fst中

正排索引(ProfileIndex)

基本概念

正排索引是为了进行规模查找服务的，当咱们经过倒排索引查找到一些文档后，咱们想过滤出在一定日期内的文档，这时咱们就会去查找正排索引，找到契合规模的文档，然后对倒排索引查找的文档和正排索引查找的文档求交集，得到最终成果

完成思路

运用 boldDB 完成，由于 boltDB 是 B+树完成的KV数据库，能够很好的支持规模查找，由于B+树的叶子节点本来便是有序的。查询时先找到规模内的第一个数，然后往后遍历直到抵达边界条件

比方要查找价格是 2000-4000 的产品，就会从B+树的根节点开始向下查找第一个大于等于2000的结点，然后从该结点开始向后一个一个遍历，直到遍历完一切结点或许当前结点的数值大于 4000

运用举例

首要，经过标题的倒排索引，检索出一切的带手机这个关键词的产品的成果集，他们的docId是【1，2，3】
在查询倒排一起，咱们能够查询价格的正排索引，找出契合条件的文档，返回docId列表【2，3，4】
遍历完成今后，对两个成果取交集，得到最终的成果集【2，3】

兼并多颗B+树

由于段需求兼并，所以段中的正排索引也需求兼并

咱们运用ｂ+树对正排进行存储，B+树天然带排序，那么兼并正排的时分实践上便是兼并多个B+树，咱们只要运用多路归并排序的方法就能兼并多个B+树了。每个B+树的Key便是待归并的元素，一边扫描B+树一边构建一个新的B+树，然后把正排文件就兼并完了

文档仓(Profile)

基本概念

每个字段都有一个profile，记载字段的数据，文档仓中记载了一切字段的内容，用 Mmap 方法进行读取

详细完成

在profile在内存中时，运用数组保存数据，序列化时再将数组中数据写入磁盘，假如是int或许float类型的数据，字节大小固定只需求保存进.pfl文件就行。由于咱们记载了段中文档的startId，并且docID是连续的，所以读取时，只需求将要查询的docid-startId再乘以数据的占用位数，就能够得到数据在文件中的偏移量，然后读取到数据。假如是string类型，由于长度不固定，则pfl文件中保存的是的偏移量，数据实践保存在dtl文件中，经过读取pfl能够得到数据偏移量，找到实践数据在dtl中的方位，其中前8个字节记载的是文本的长度，这样就能够经过文本长度和偏移量比及文本内容了。

搜索引擎模块设计与实现——索引模块 | 青训营笔记

基本架构

索引层(Index)

基本概念

索引构建

中心组件

文件组成

增加文档

删去文档

段层(Segment)

段结构

基本概念