mysql索引 倒排表

索引 倒排表"/>

mysql索引 倒排表

>>>

此时，假如用户想找tagk1=tagv1这个维度条件下的seriesKey，那第一个map就满足条件。很显然，这种场景下3个Tag组成的seriesKey，最终形成的seriesByTagKeyValue就会有3重seriesKey冗余。

因此使用Int类型的SeriesID对SeriesKey进行编码，将长长的SeriesKey编码成短短的SeriesID，可以有效减少索引在内存中的存储量。另外，SeriesID集中存储在一起可以使用Int集合编码有效压缩。

Memory-Based Index实现方案好处是可以根据tag查找SeriesKey会非常高效，但是缺点也非常明显：

1. 受限于内存大小，无法支持大量的TimeSeries。尤其对于某些基数非常大的维度，会产生大量的SeriesKey，使用Memory-Based Index并不合适。

2. 一旦InfluxDB进程宕掉，需要扫描解析所有TSM文件并在内存中全量构建TSI结构，恢复时间会很长。

Disk-Based Index

正因为Memory-Based Index存在如此重大的缺陷，InfluxDB 1.3之后实现了Disk-Based Index。Disk-Based Index方案会将索引持久化到磁盘，在使用时再加载到内存。InfluxDB官网对Disk-Based Index实现方案做了如下说明：

不难看出，InfluxDB中倒排索引和时序数据使用了相同的存储机制 – LSM引擎。因此倒排索引也是先写入内存以及WAL，内存中达到一定阈值或者满足某些条件之后会执行持久化操作，将内存中的索引写入文件。当磁盘上文件数超过一定阈值会执行Compaction操作进行合并。实际实现中，时序数据点写入系统后会抽出Measurement、Tags并拼成SeriesKey，在系统中查看该SeriesKey是否已经存在，如果存在就忽略，否则写入内存中相应结构(参考log_file文件中变量InMemory Index)。接着内存中的数据会flush到文件(参考log_file文件中CompactTo方法)，接下来笔者将会重点介绍TSI文件格式，如下图所示：

TSI文件主要由4个部分组成：Index File Trailer，Measurement Block，Tag Block以及Series Block。

1. File Trailer主要记录Measurement Block、Tag Block以及Series Block在TSI文件中的偏移量以及数据大小。

2. Measurement Block存储数据库中表的信息，通常来说Measurement不会太多，一个Block也就够了。

3. Tag Block实际上是seriesByTagKeyValue这个双重map – map>>在文件中的实际存储。

4. Series Block存储了数据库中所有SeriesKey。

Measurement Block

Measurement Block存储数据库中所有时序数据表表名信息，Block主要由三部分组成：Block Trailer Section、Hash Index Section以及Measurement Entry Section。

1. Block Trailer Section记录了Hash Index Section以及Measurement Data Section在文件中的偏移量以及数据大小，是Measurement Block读取解析的入口。

2. Hash Index是一个Hash索引。实现机制很简单，就是一个Map结构 – map。使用Hash函数将给定measurement映射到数组的特定位置，将该特定数组位的值置为该measurement在文件中的实际偏移量。Hash Index主要有两个核心作用：

(1)加快Measurement的查找效率。正常情况下在Block中查找某个Measurement Entry只能依次遍历查找，或者二分查找，而使用Hash索引可以直接在o(1)复杂度找到待查Measurement。

(2)减小内存开销。如果没有Hash Index，在Measurement Block中查找一个Measurement Entry，需要将该Block全部加载到内存再查找。Measurement Block本身大小不特定，有可能很大，也可能很小，一旦Block很大的话内存开销会非常之大。而使用Hash Index的话，只需要将Hash Index加载到内存，根据Hash Index定位到Measurement Entry具体的offset，直接根据偏移量加载具体的待查找measurement。

3. Measuremen是具体的时序数据表，比如广告信息表等。Measurement是一个复合结构，由一系列字段组成，其中name表示指标名，TagBlock offset以及TagBlock size表示该Measurement所对应的TagBlock在索引文件中的偏移量以及大小。因此可以使用Measurement过滤掉大量不属于该Measurement的Tags。

Tag Block