elasticsearch索引模型
一个shard就对应了一个lucene的library
Elasticsearch索引使用的存储内容主要取决于lucene中的数据存储
(1) elasticsearch存储简介
Elasticsearch中的数据是如何存储
Elasticsearch对外提供的是index的概念，可以类比为DB，
用户查询是在index上完成的，每个index由若干个shard组成，以此来达到分布式可扩展的能力。
shard是Elasticsearch数据存储的最小单位，index的存储容量为所有shard的存储容量之和。
Elasticsearch集群的存储容量则为所有index存储容量之和。
一个shard就对应了一个lucene的library。对于一个shard，Elasticsearch增加了translog的功能，类似于MySQL的WAL(Write Ahead Log)日志，是数据写入过程中的中间数据，其余的数据都在lucene库中管理的。
| elasticsearch | MySQL | Excel |
|---|---|---|
| Node/Cluster (分片) | Cluster | 文件夹/Excel集合 |
| index(索引) | Database(数据库) | 一个Excel |
| Type | Table(一个表) | Excel里的一个Sheet |
| Document (文档) | Row(表里一行数据) | Sheet里的一行 |
| field (字段) | field(一个字段) | Sheet里的一个单元格 |
(2) lucene简介
lucene基本概念
segment : lucene内部的数据是由一个个segment组成的，写入lucene的数据并不直接落盘，而是先写在内存中，经过了refresh间隔，lucene才将该时间段写入的全部数据refresh成一个segment，segment多了之后会进行merge成更大的segment。lucene查询时会遍历每个segment完成。由于lucene* 写入的数据是在内存中完成，所以写入效率非常高。但是也存在丢失数据的风险，所以Elasticsearch基于此现象实现了translog，只有在segment数据落盘后，Elasticsearch才会删除对应的translog。
doc : doc表示lucene中的一条记录
field ：field表示记录中的字段概念，一个doc由若干个field组成。
term ：term是lucene中索引的最小单位，某个field对应的内容如果是全文检索类型，会将内容进行分词，分词的结果就是由term组成的。如果是不分词的字段，那么该字段的内容就是一个term。
倒排索引（inverted index）: lucene索引的通用叫法，即实现了term到doc list的映射。
正排数据：搜索引擎的通用叫法，即原始数据，可以理解为一个doc list。
docvalues :Elasticsearch中的列式存储的名称，Elasticsearch除了存储原始存储、倒排索引，还存储了一份docvalues，用作分析和排序。
(3) 索引原理
(3.1) 新增数据
(3.2) 修改数据
(3.3) 删除数据
(3.4) 查询数据
根据主键id查询
根据关键字查询
(3.5) 倒排索引合并
MySQL里经常会有 SELECT * FROM table_user WHERE city='北京' and user_name = 'lisi'
elasticsearch里也会有类似的查询
单个词匹配可以得到这个term的倒排链(docId列表)
lucene的优势在哪呢？
问题其实就变成了求有序集合求并集的问题
多个有序集合求并集
elasticsearch 利用 Skip List 合并
把多个 posting list 用 AND 的关系合并，得出 posting list 的交集
每个 list 需要指出 Advance 这个操作，快速移动指向的位置。什么样的 list 可以这样 Advance 往前做蛙跳？skip list
利用 bitset 合并
(1) 多层for循环
最简单的办法是多层for循环，这样的时间复杂度是 O(n^x)，这个明显是不能接受的。
两层是 O(n^2)，三层是O(n^3)
(2) 拉链法
有序集合1 {1,3,5,7,8,9} 和 有序集合2 {2,3,4,5,6,7}，两个指针指向首元素，比较元素的大小（如果相同，放入结果集，随意移动一个指针，否则，移动值较小的一个指针，直到队尾），
优势（集合中的元素最多被比较一次，时间复杂度为O(n)，多个有序集合可以同时进行，这适用于多个分词的item求url_id交集）
这个方法就像一条拉链的两边齿轮，一一比对就像拉链，故称为拉链法
(3) 水平分桶
水平分桶，多线程并行
有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90} 和 有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}，先进行分桶拆分【桶1的范围为[1, 9]、桶2的范围为[10, 100]、桶3的范围为[101, max_int]】，
于是拆分成集合1【a={1,3,5,7,8,9}、b={10,30,50,70,80,90}、c={}】和 集合2【d={2,3,4,5,6,7}、e={20,30,40,50,60,70}、e={}】，
利用多线程对桶1（a和d）、桶2（b和e）、桶3（c和e）分别求交集，最后求并集。
每个区间利用多线程并行求交集，各个线程结果集的并集，作为最终的结果集，能够大大的减少执行时间
(4) bitmap
bitmap，大大提高运算并行度，时间复杂度O(n)
假设list1{1,3,5,7,8,9} 和 list2{2,3,4,5,6,7} 的所有元素都在桶值[1, 16]的范围之内，可以用16个bit来描述这两个集合，原集合中的元素x，在这个16bitmap中的第x个bit为1，此时两个bitmap求交集，只需要将两个bitmap进行”与”操作，结果集bitmap的3，5，7位是1，表明原集合的交集为{3,5,7}
水平分桶（每个桶内的数据一定处于一个范围之内），使用bitmap来表示集合，能极大提高求交集的效率，但时间复杂度仍旧是O(n)，但bitmap需要大量连续空间，占用内存较大。
从Lucene 5 开始采用了一种改进的位图方式，即roaring bitmaps ( 官网http://roaringbitmap.org/ )，它是一个压缩性能比bitmap更好的位图实现。
(5) 跳表
跳表，时间复杂度为O(log(n))
集合1 {1,2,3,4,20,21,22,23,50,60,70} 和 集合2{50,70} 求交集，如果用拉链法，会发现1,2,3,4,20,21,22,23都要被无效遍历一次，每个元素都要被比对，时间复杂度为O(n)，能不能每次比对“跳过一些元素”呢？集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表时，一级只有{1,20,50}三个元素，二级与普通链表相同，集合2{50,70}由于元素较少，只建立了一级普通链表。这样在进行拉链法时，复杂度由O(n)降至O(log(n))
(4) lucene索引实现
Lucene简介、索引原理、Lucene索引实现
Lucene现使用的倒排表结构叫Frame of reference,它主要有两个特点：
1. 数据压缩，可以看下图怎么将6个数字从原先的24bytes压缩到7bytes。
2. 跳跃表加速合并，因为布尔查询时，and 和or 操作都需要合并倒排表，这时就需要快速定位相同文档号，所以利用跳跃表来进行相同文档号查找。
ElasticSearch倒排表 https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
参考资料
[1] Lucene底层实现原理，它的索引结构
[2] Elasticsearch 存储原理-lucene底层数据结构
[3] 简析ES/Lucene索引的基本设计原理
[4] Elasticsearch 如何做到快速检索 - 倒排索引的秘密
[5]
[] 时间序列数据库的秘密 (2)——索引
[] Frame of Reference and Roaring Bitmaps
[]
[]
[10] Lucene 查询原理及解析
[11] lucene字典实现原理——FST
[12] Lucene查询分析
[13] Lucene 查询原理
[14] Lucene系列七：倒排数组合并
[15] Elasticsearch 存储原理-lucene底层数据结构