Open TianEx opened 5 years ago
ES是通过Lucene的倒排索引实现比RDBMS更快的过滤，特别是它对多条件的过滤支持的非常好。
相对于b-tree索引是为了优化写入，但当我们不需要支持快速更新的时候，可以使用预先排序的方式换取更小的存储空间、更快的检索速度等好处。
Lucene的倒排索引构成： [Term Index] -> [Term Dictionary] -> [Posting List] 倒排索引为每个docoment中的所有字段都建立一个索引列表，每个字段值成为term，其对应的docid就是posting list，其存储了所有符合某个term的docid。 但是由于term没有排序，所以需要进行全部过滤排序，这样就可以使用二分查找更快找到目标term（即term dictionary），由于term dictionary可以使用logN次磁盘查找得到目标，但是磁盘随机读仍然非常昂贵，所以尽可能把一些数据缓存到内存中。 同时由于term dictionary本身又忒大了，无法完整的放到内存中，所以就需要使用term index（实际上就是一棵trie树，每个节点包含词的前缀和在term dic中的offset），通过term index可以快速定位到term dictionary某个offset，然后从此offset往后顺序查找，同时使用压缩是的内存可以缓存整个term index。
[Term Index] -> [Term Dictionary] -> [Posting List]
基于上述，由于MySQL只有term dictionary这一层，以b-tree排序的方式存储在磁盘上，检索一个term需要若干次random access的磁盘操作，而Lucene在term dictionary基础上添加了term index来加速检索，term index以树的形式缓存在内存中，从term index查找到相应的term dictionary的block位置后，再去磁盘查找term大大减少random access次数。同时由于term index在内存中是以压缩方式存储，term dic以block形式在磁盘存储，一个block内部利用公共前缀压缩，相比b-tree更节约磁盘空间。
实际上给定查询过滤条件的过程就是先从term index找到在term dictionary的大概位置，然后再从term dictionary里精确地找到对应的term，得到一个posting list或者一个指向posting list位置的指针。然后再查询其他条件的过程也是类似的。最后得出多条件过滤就是把多个posting list做一个与合并。 但是这个与合并操作实际并不容易，对于MySQL来说如果你给字段都建立索引，查询的时候只会选择其中最selective的来用，然后其他条件是在遍历row的过程中在内存中计算之后过滤掉。 为了能联合使用多个索引呢，办法主要有二：
在ES中使用来以上两种联合索引方式，如果查询的filter缓存到了内存中（以 bitset 的形式），那么合并就是两个bitset的AND，而如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk 的posting list了。
ES是通过Lucene的倒排索引实现比RDBMS更快的过滤，特别是它对多条件的过滤支持的非常好。
相对于b-tree索引是为了优化写入，但当我们不需要支持快速更新的时候，可以使用预先排序的方式换取更小的存储空间、更快的检索速度等好处。
Lucene的倒排索引构成：
[Term Index] -> [Term Dictionary] -> [Posting List]倒排索引为每个docoment中的所有字段都建立一个索引列表，每个字段值成为term，其对应的docid就是posting list，其存储了所有符合某个term的docid。 但是由于term没有排序，所以需要进行全部过滤排序，这样就可以使用二分查找更快找到目标term（即term dictionary），由于term dictionary可以使用logN次磁盘查找得到目标，但是磁盘随机读仍然非常昂贵，所以尽可能把一些数据缓存到内存中。 同时由于term dictionary本身又忒大了，无法完整的放到内存中，所以就需要使用term index（实际上就是一棵trie树，每个节点包含词的前缀和在term dic中的offset），通过term index可以快速定位到term dictionary某个offset，然后从此offset往后顺序查找，同时使用压缩是的内存可以缓存整个term index。基于上述，由于MySQL只有term dictionary这一层，以b-tree排序的方式存储在磁盘上，检索一个term需要若干次random access的磁盘操作，而Lucene在term dictionary基础上添加了term index来加速检索，term index以树的形式缓存在内存中，从term index查找到相应的term dictionary的block位置后，再去磁盘查找term大大减少random access次数。同时由于term index在内存中是以压缩方式存储，term dic以block形式在磁盘存储，一个block内部利用公共前缀压缩，相比b-tree更节约磁盘空间。
实际上给定查询过滤条件的过程就是先从term index找到在term dictionary的大概位置，然后再从term dictionary里精确地找到对应的term，得到一个posting list或者一个指向posting list位置的指针。然后再查询其他条件的过程也是类似的。最后得出多条件过滤就是把多个posting list做一个与合并。 但是这个与合并操作实际并不容易，对于MySQL来说如果你给字段都建立索引，查询的时候只会选择其中最selective的来用，然后其他条件是在遍历row的过程中在内存中计算之后过滤掉。 为了能联合使用多个索引呢，办法主要有二：
在ES中使用来以上两种联合索引方式，如果查询的filter缓存到了内存中（以 bitset 的形式），那么合并就是两个bitset的AND，而如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk 的posting list了。