文章插图
- 确定切分维度，这里维度的选取顺序是数据在这个维度方法最大的维度优先 。一个直接的理解就是，数据分散越开的维度，我们优先切分 。
- 切分点的选这个维度最中间的点 。
- 递归进行步骤1，2，我们可以设置一个阈值，点的数目少于多少后就不再切分，直到所有的点都切分好停止 。
文章插图
BitSet 过滤二进制处理，通过BKD-Tree查找到的docID是无序的，所以要么先转成有序的docID数组，或者构造BitSet，然后再与其他结果合并 。
IndexSorting
IndexSorting是一种预排序，在ES6.0之后才有，与查询时的Sort不同，IndexSorting是一种预排序，即数据预先按照某种方式进行排序，它是Index的一个设置，不可更改 。
一个Segment中的每个文档，都会被分配一个docID，docID从0开始，顺序分配 。在没有IndexSorting时，docID是按照文档写入的顺序进行分配的，在设置了IndexSorting之后，docID的顺序就与IndexSorting的顺序一致 。
举个例子来说，假如文档中有一列为Timestamp，我们在IndexSorting中设置按照Timestamp逆序排序，那么在一个Segment内，docID越小，对应的文档的Timestamp越大，即按照Timestamp从大到小的顺序分配docID 。
IndexSorting 之所以可以优化性能，是因为可以提前中断以及提高数据压缩率，但是他并不能满足所有的场景，比如使用非预排序字段排序，还会损耗写入时的性能 。
搜索引擎正是靠优秀的理论加极致的优化，做到查询性能上的极致，后续会再结合源码分析压缩算法如何做到极致的性能优化的 。
未完待续~
附：进一步阅读
http://lucene.Apache.org/
https://wiki.apache.org/lucene-JAVA/FrontPage
https://zhuanlan.zhihu.com/p/35814539
http://www.runoob.com/java/java-bitset-class.html
https://www.cnblogs.com/skycore/p/5093257.html
https://www.cnblogs.com/LBSer/p/4119841.html
https://blog.csdn.net/zhufenglonglove/article/details/51700898
https://www.jianshu.com/p/1e498888f505
http://www.nosqlnotes.com/technotes/searchengine/lucene-invertedindex/
https://www.jianshu.com/p/69d56f9c0576
作者：yhzhtk
【深入搜索引擎原理】
推荐阅读
- 通俗易懂的Nginx工作原理
- 淘宝搜索引擎排名规则 怎么让淘宝搜索排名靠前
- 九种跨域方式的实现原理，第一个就超惊艳！
- 一篇文章彻底搞懂base64编码原理
- 深入理解热度算法：如何做好内容推荐？
- 图解HTTP原理
- JavaScript引擎运行原理
- C语言调动硬件的原理是什么？
- 5分钟理解SSH的工作原理
- 从网页建库来摸清搜索引擎排名核心规律