mysql innoDB  b+tree

单条记录查询时，b+tree 自顶层向下逐层查找节点，最终找到叶子节点，
范围查询时，b+tree找到叶子节点的起始位置，通过叶子节点链表依次查询数据，直到范围结束为止。

elasticsearch索引原理
倒排索引

term  Posting list  
文档ID
term Dictionary
term index
FST(Finite StateTransducers) 压缩
Term dictionary在磁盘上 分block 存储
block内部公共前缀压缩
posting list 压缩
增量编码压缩，将大数变小数，按字节存储


联合索引查询

skip list
bitset 二进制，直接按位与

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

FST以字节的方式存储所有的term，这种压缩方式可以有效的缩减存储空间，
使得term index足以放进内存，但这种方式也会导致查找时需要更多的CPU资源。


Lucene 索引

单词ID 
单词 
文档频率   文档集合中有多少个文档包含某个单词
倒排列表   包含单词ID及其他必要信息
DocId    单词出现的文档id
TF       单词在某个文档中出现的次数
POS      单词在文档中出现的位置