源码分析文章比较难以组织,推荐大家直接看大量注释的源码: 传送门
上一篇文章讲了bkd树的基本原理,这次看一下Lucene对BKD树的实现.
bkd树在lucene中的实现,都在org.apache.lucene.util.bkd
中,其中又包含了下面几个类.
为了看懂这块代码,让我们先来介绍下三个接口.
这个接口,用来描述一个多维的点
. 并且提供了数据的获取方式:
这个接口,是点的写入
的抽象接口,可以通过他的实现类,向(内存/磁盘)等存储介质写入多个点.
public interface PointReader extends Closeable {
/** Returns false once iteration is done, else true. */
// 是否还有下一个值呢???
boolean next() throws IOException;
/** Sets the packed value in the provided ByteRef */
// 把打包好的值,放进到给定的容器里, 反正就是迭代器呗,能知道下一个还有没有,拿到当前的值
PointValue pointValue();
}
这个接口,提供了点的读取
抽象接口,他的实现类可以从(内存/磁盘)上读取一系列的点.
BKD树的写入过程,是在BKDWriter
中实现的. 为了文章的简洁,这里就不一一介绍成员变量,构造方法等等给了。直接按照写入流程开始学习。
首先,我们都知道使用BKD树的目的是什么,那就是对给定的数据,首先构建一棵树,来支持快速的查询,之后再说支持树的更新的事情。
既然是添加数据,构建一棵树,那么就从add
方法开始看起把。
流程图:
代码:
public void add(byte[] packedValue, int docID) throws IOException {
// 数据check
if (packedValue.length != config.packedBytesLength) {
throw new IllegalArgumentException("packedValue should be length=" + config.packedBytesLength + " (got: " + packedValue.length + ")");
}
if (pointCount >= totalPointCount) {
throw new IllegalStateException("totalPointCount=" + totalPointCount + " was passed when we were created, but we just hit " + (pointCount + 1) + " values");
}
// 初始化
if (pointCount == 0) {
initPointWriter();
System.arraycopy(packedValue, 0, minPackedValue, 0, config.packedIndexBytesLength);
System.arraycopy(packedValue, 0, maxPackedValue, 0, config.packedIndexBytesLength);
} else {
// 每个维度进行写入
for (int dim = 0; dim < config.numIndexDims; dim++) {
int offset = dim * config.bytesPerDim;
// 进行最大最小值的写入
if (FutureArrays.compareUnsigned(packedValue, offset, offset + config.bytesPerDim, minPackedValue, offset, offset + config.bytesPerDim) < 0) {
System.arraycopy(packedValue, offset, minPackedValue, offset, config.bytesPerDim);
} else if (FutureArrays.compareUnsigned(packedValue, offset, offset + config.bytesPerDim, maxPackedValue, offset, offset + config.bytesPerDim) > 0) {
System.arraycopy(packedValue, offset, maxPackedValue, offset, config.bytesPerDim);
}
}
}
// 追加当前点
pointWriter.append(packedValue, docID);
pointCount++;
// 记录docId
docsSeen.set(docID);
}
可以看出来,add方法其实比较简单,甚至可以单纯的理解为只是对PointWriter
进行了append操作而已。
这里的PointWriter
,也就是之前介绍的点的写入接口,有两种实现方式,基于内存的和基于磁盘的. 当要写入的point数量大于内存中允许的最大点数量
时,采用磁盘写入,否则采用内存写入.
内存中允许的最大点数量
这里采用了内存大小的限制方式,给定最大的16M内存,之后除以每个点的大小,就可以得到内存中最大存储的点的数量了.
在不断的添加之后, 终于完成了所有的add,此时就需要进行finish来进行实际的写入了. (add方法只是缓冲,没有实际的构造树)
流程图:
代码比较长,就不贴了.
核心是做了两件事,对应两个方法
build
方法.writeIndex
方法.既然涉及到树,那么想必大家都是知道,构建的过程肯定是个递归的方法了. 流程如下:
核心的路径为:
点的值/docId
写入到磁盘.这个方法其实和bkd树实现无关,它将这棵树的一些元数据, 文件偏移位置等索引内容, 写入到了meta文件和index文件两个文件中.
这部分内容会在kdd/kdi/kdm等文件格式中详细介绍.
在bkd代码中,称上面的先add,然后finish的方法为慢的方法,它主要用来合并已有的分片.
代码中还提供了当我们从IndexWriter
的缓冲区,直接创建一个新的分片时,应该使用的方法,即org.apache.lucene.util.bkd.BKDWriter#writeField
. 它和上面的方法的区别是, 由于是完全新的切片, 我们可以在写入磁盘之前进行重排序,因此会比上面的性能好一些.
由于基本上是性能差异, 而这片文章主要想讲lucene如何实现一个BKD树,暂时就不深究性能了.
简单总结一下对一堆多维数据点
,构建BKD树的过程.
说实话, 对于BKD树的实现,我目前没有做到100%完全了然于心, 但是经过一番努力,仍旧差点意思,因此只能放到之后了.
希望随着看的越来越多,对于BKD的理解能够更加透彻,回头来润色这篇文章.
完。