针对数值型的倒排索引,Lecene从6.X引入了BKD树结构,BKD全称:Block K-Dimension Balanced Tree。在此之前,数值型查找和String结构一样,使用FST结构)建立索引,FST结构针对精确匹配存在较大的优势,但是数值型很大部分使用场景为范围查找, BKD树就是解决这类使用场景的。若我们将多维简化为一维时,结构就是bst(二叉查找树)。
数据放入内存中
BKD树支持多维范围,数值型包括int,float,point等, 这里就以int类型写入作为示例,将age
建构为三维:
1 | Document document = new Document(); |
IntPoint内部会将多维转变为一维数组,转变过程比较简单,比如int,将转变为长度为3*4=12的byte数组。真正开始在内存中建立索引结构是在DefaultIndexingChain.indexPoint()
处:
1 | private void indexPoint(int docID, PerField fp, IndexableField field) { |
其中,使用ByteBlockPool弹性扩容的功能存储byte数组的value, docIDs记录的是第几个point对应的文档号。numPoints记录的是point的个数(一个point可以由多个域构成),因为存在一个字段,会存储多个point的情况。
将内存中的结构flush到磁盘
构建kdd文件
flush到文件中指的是形成一个segment,触发条件有两个(同fdx,dvm、词典建立一样):
1.lucene建立的索引结构占用内存或者缓存文档数超过阈值。该check会在每次索引完一个文档后(详见flushControl.doAfterDocument
)。
2.用户主动调用indexWriter.flush()触发。
刷新建立BKD树时,我们首先进入PointValuesWriter.flush()
:
1 | public void flush(SegmentWriteState state, Sorter.DocMap sortMap, PointsWriter writer) throws IOException { |
这里用MutablePointValues封装了读取每个point的方法,需要进入Lucene86PointsWriter.writeField看下。我们需要知道,Lucene86PointsWriter定义了BKD每个叶子存放的point不能超过512个(BKDWriter.DEFAULT_MAX_POINTS_IN_LEAF_NODE),大小不能超过16MB(BKDWriter.DEFAULT_MAX_MB_SORT_IN_HEAP):
1 | @Override |
BKDWriter函数就是构建BKD数的核心类, 需要继续进入BKDWriter.writeField->writeFieldNDims看如何构建的,我们以point为2+维进行介绍,一维的是其简化版:
1 | private Runnable writeFieldNDims(IndexOutput metaOut, IndexOutput indexOut, IndexOutput dataOut, String fieldName, MutablePointValues values) throws IOException { |
该函数主要做了如下事情:
1.计算了该BDK的叶子数
2.首先统计每个维度的最大值&最小值, 以便决定是从哪个维度开始切分排序
3.进入BKDWriter.build()
函数开始递归构建每个维度。原则上,对于当前所有point,首先按照512个point为1个节点,放入完全二叉树的叶子中。按照从跟节点从上向下切分所有的叶子节点,切分前查找每个维度的最大最小差值,以这个维度将切分的左右子树保持局部有序。
4.将构建好的BKD树元数据存放在kdi和kdm文件中.
BKDWriter.build
将切分过程&局部有序分成两个阶段:
1.切分到叶子节点后也保证叶子内某个维度有序。
2.当没切分到叶子节点时,保证左右子树局部有序。
当不是叶子节点时,需要split,保证某一维度有序
这里看下如何还不是叶子节点时的切分过程:
1 | final int splitDim; |
根据当前数据进行排序切分,主要做了如下事情:
1.判断是否需要重新(精确)统计from->to所有维度最大值、最小值,仅当父类节点在当前维度每切分4次(SPLITS_BEFORE_EXACT_BOUNDS)才统计,因为精确统计所有point的边界是一个非常昂贵的操作。
2.在BKDWriter.split()
根据最大值最小值边界差距最大的那个维度确定以哪个维度排序。同时为了考虑每个维度被选中切分排序的次数不能差距太大,规定了,每个维度切分排序次数不能相差2倍,若切分次数太少了,会强制选择切分次数最小的那个维度。
3.通过构建完全二叉树来计算左子树、右子树分别有多少个叶子节点。
4.确定在被切分的维度上,最大值和最小值有多少个相同的前缀,以便压缩存储。
5.使用MutablePointsReaderUtils.partition
来进行排序。保证当前维度下,左子树的值小于右子树。
6.重新恢复左子树的所有维度的最大值:maxSplitPackedValue
和右子树的所有维度的最小值:minSplitPackedValue
7.分别递归左子树和右子树,再继续查找分隔维度并在此维度上进行排序。最终形成了每个子树只在一个维度保证了左右有序。切分过程如下:
我们再看下MutablePointsReaderUtils.partition
如何在splitDim维度上保证左边的数值小于等于mid对应的值、右边的数大于等于mid对应的值。这里其实使用了堆排&快排的思想完成的排序。
1 | public static void partition(int numDataDim, int numIndexDim, int maxDoc, int splitDim, int bytesPerDim, int commonPrefixLen, |
排序逻辑我们需要注意两个地方:
1.每个point当前切分维度splitDim的逻辑位数:dataCmpBytes + (bitsPerDocId + 7) / 8。我们当使用基数排序时,会确定每个point的位数,然后可以从高位->低位的排序。同样,这里对每个point的第splitDim维度产生虚拟位数。针对from-to的point的第splitDim维度,首先使用从不相同的byte进行排序,其次基于docId进行排序。
2.byteAt中定义了逻辑位数的获取方法,k表示逻辑元素的位数,当k小于该元素该维度的不同起始位时,获取具体的byte;当k超过不同位数dimCmpBytes时,则比较文档Id大小。
我们看下RadixSelector里最核心的排序算法部分:
1 | private void radixSelect(int from, int to, int k, int d, int l) { |
该函数主要做了如下事情:
1.通过computeCommonPrefixLengthAndBuildHistogram统计第splitDim维度逻辑位数第d位相同的前缀commonPrefixLength,并且统计每个字母出现的次数histogram。
2.若commonPrefixLength大于0,代表该维度逻辑位数为d位有相同的前缀。同时检测到还有逻辑位数没有排序完,那么直接跳到逻辑位数不同的位数继续进行排序。
3.否则,该维度逻辑位数为d位没有相同的前缀,那么就统计下,第k(初始化时为mid)个数逻辑位数d的值在哪个histogram维度内,然后调用partition()
按照快排的思想将找出bucketTo-bucketFrom的值放在中间,这样,左边的值都小于中间的那组值,右边的值都大于中间的那组值。
4.继续递归,完成第k个所在那档的point所在splitDim维度逻辑为数第d+1位有序,直到这档splitDim维度逻辑完全有序。
此时,所有point在splitDim维度维度,形成了相对排序:以k为分隔, 第k个point左边的所有point均小于等于k,第k个pint右边的所有point均大于等于k。
当递归到叶子节点时,需要split
此时叶子节点内的point并没有按照某一个维度有序。每个叶子的处理顺序比较有序,是从第一个叶子、第二个、第三个、、、、最后一个叶子的顺序进行的。这部分主要是将叶子节所有point点如何高效的存储起来。
1 | // 叶子节点的起始位置 |
具体做了如下事情:
1.遍历from-to所有point,依次比较每个point同一个维度相同的前缀长度,存放在commonPrefixLengths。
2.统计每个维度不相同前缀point的cardinaliy,统计时使用长度为256的FixedBitSet,代表着256个字符。
3.遍历每个维度,找出cardinaliy值最小的那个维度sortedDim。
4.基于sortedDim维度,调用MutablePointsReaderUtils.sortByDim
使用快排原理保证叶子内所有元树在sortedDim维度有序。
5.统计from-to个Point的cardinaliy,这里每个维度都要对比。
6.存储from-to个排序后Point的docId
7.存储每个维度相同的前缀。
8.使用BKDWriter.writeLeafBlockPackedValues()
存储from-to个具体的point。
kdd文件结构如下:
构建kdm和kdi文件
当对所有point进行排序后,开始存储BKD树的每个子节点和叶子节点,会进入到:
1 | private void writeIndex(IndexOutput metaOut, IndexOutput indexOut, int countPerLeaf, BKDTreeLeafNodes leafNodes, long dataStartFP) throws IOException { |
该函数主要做了两件事:
1.在packIndex
中压缩存储BKD树子节点和叶子节点。
2.在writeIndex
中存储压缩后的数据,及BKD元数据。
压缩转存BKD树
压缩BKD转存的核心函数是recursePackIndex
,采用递归的方式转存,以中序遍历的方式对BKD树进行处理,首先先存储中间飞叶子的信息,然后再分别对左右叶子节点进行处理:
1 | // 到了叶子节点 |
按照中序遍历的方式存储,比如处理node1节点:
其中:
deltaFP:leftBlockFP - minBlockFP,minBlockFP是父节点最左边的子节点,leftBlockFP是该节点的子节点。
code: (firstDiffByteDelta * (1+bytesPerDim) + prefix) * numIndexDims + splitDim,firstDiffByteDelta是当前节点切分维度的value-该相同维度上一个父节点切分的value。这里采用了编码,使之存储三个数值。
最终,BKD树存储在了数组blocks中。
存储bkm和bki文件
在BKDWriter.writeIndex
文件中,bki文件存储了bkd树转存后的blocks的二进制数,而bkm文件存储了BKD树的元数据信息:
1 | private void writeIndex(IndexOutput metaOut, IndexOutput indexOut, int countPerLeaf, int numLeaves, byte[] packedIndex, long dataStartFP) throws IOException { |
总结
BKD树主要运用在范围多维查找,在空间上,按照完全二叉树结构,将数据分为左右两部分,找到所有point每个维度[min,max]差距最大的维度,在该维度按照照左子树完全小于中间值,右子树完全大于间的值。通过范围查找,能够快速定位出docId。