空间索引技术在58搜索中的落地实践–BKD技术原理深入剖析

见贤思齐

1序言一直以来，在涉及搜索引擎的空间数据检索、空间数值数据查询或范围查询问题领域，BKD或BKD-Tree技术作为空间索引技术的重要方面，一直是被讨论的一个绕不开的热门话题。在网络上有关BKD的技术文章或博客、贴文，虽然也有一些，然而多是言之不精，浅谈辄止，良莠不齐，让很多想学习、掌握BKD技术要点和技术内幕的人不得其法，徘徊在困惑迷茫的新手之路上。着眼于此，本文正是这样一篇全面、深入讲述BKD前世今生、技术内幕和算法本质的技术文章，力求呈现细胞级的深刻论述表达，演绎透彻流畅的算法思想理解脉络，通篇辅以详实的算法伪代码展现，力求达到"理解后即可实践",全在这一篇文章。关于BKD技术，只看这一篇就足够了。2问题描述现在有如下示例的14个二维空间的点的数据，每一行表示一个点数据，冒号前的数值为该点的id，冒号后是一个典型的二维数值的坐标值x和y（假定id和x，y的值都是int类型）。比如第一行03,8)含义为：数据id为0，数据值是一个二维数据，第一维值x=3,第二维值y=8。03,8)1-74,10)22,-33)30,-92)473,84)5-10,19)6-23,73)78,-53)80,-37)9:(4,29)10:(39,-98)11:(-16,9)12:(26,89)13:(-76,33)本文要讨论解决的问题可表述为：如何从该数值数据点的集合中快速查询出x值在(-3,8）范围内且y值在（-5,3）范围内所有点（即返回满足范围条件内的所有点的id及其二维数据值x和y本身）？这就是搜索引擎中非常基础的查询问题之一：大规模数值（类型）数据的范围查询问题，尤其经常是要在多维的数值数据集合上的范围查询（比如本例中就是一个2维数值数据的查询）。要查询的目标范围的上下边界值如果设定为同一个值，范围查询就转变为数值数据的精确值查询。因此解决了范围查询问题几乎就解决了数值数据查询的绝大部分问题，因此这个问题具有基础性。详细分析问题之前，简短描述该问题的关键要素如下：面对的数据规模大-数据个数多，字段多，维度多搜索引擎场景要查询的数据集合通常是海量的，因此数据集合全集通常不能完全存于内存中，一般还要存储在外部存储器上（比如磁盘）。磁盘IO读写数据速度较慢问题也是重要的解决方案考虑因素之一，后文会涉及描述这一点。通常不仅仅数据个数多，而且每一个数据还有多个数值字段，每个字段都有快速执行快速范围查询的需求。最后每个字段的数据数值本身可能不止1维，可能是多个维度的。（当然维度数一般不会太大，比如一般最大支持16维或32维即可）。并且，每一维的数值类型也具有多样性，可能是不同字节和精度的整型、浮点型。要求支持数据的动态更新-动态新增数据、删除和修改数据如果仅仅是要在一个静止不变的静态数据集合上执行范围查询，可能你有所耳闻以传统的KD-Tree数据结构就能满足本问题要求。但是既要支持多维数据快速查询，又要兼顾海量数据的动态更新操作，KD-Tree就不合适了。后文会展开描述KD-Tree的局限性。综合以上，本文将描述一种能高效地运行在海量的大规模数值数据集合上，既支持海量数据动态更新，又能执行非常快速的数值范围查询的解决方案，即BKD-Tree。BKD-Tree英文全程是：BlockK-DimensionBalancedTree。其中的block意指“一群”，“一簇”，表明BKD-Tree其实是多个tree的集合，即一个森林的数据结构。BKD-Tree最早是杜克大学的几位教授在论文[1]中提出的，它是基于KD-B-Tree设计的，同时结合了一种被称为“logarithmicmethod"的方法使得静态数据动态化。那么BKD-Tree执行数值查询有多快呢，时间复杂度量化分析如下（假定N是数据集合的元素个数）：BKD-Tree执行精确值查询时间复杂度是O(lgN)；BKD-Tree执行范围查询的耗时依赖于查询结果的元素集合的规模R。最慢的情况如果R的规模是O(N),则BKD-Tree执行范围查询时间复杂度是O(N)；如果R的规模是O(1)，则BKD-Tree执行范围查询时间复杂度是O(lgN)。虽然如此，BKD-Tree上执行范围查询能充分利用多维数据分布的局部相似性进行“剪枝”操作，过滤掉众多不必要的数据元素，极大地提高了查询效率。下图是上述问题的14个二维数值点集合构建的BKD-Tree在58搜索中的落地实践的结构示意图：接下来，本文将从理论上详细阐述BKD-Tree方法的原理，及其在58搜索引擎中的落地实践操作细节。3解决方案和原理分析3.1.解决方案讨论大规模数值（类型）数据的范围查询问题，有很多可尝试解决方案：FST、BST、B-Tree、B+Tree、KD-Tree、KD-B-Tree、BKD-Tree。综合来看，本文描述的BKD-Tree解决方案最终比较好地解决了该问题，并且在58搜索引擎实践中落地。下面简要分解叙述这6中候选方案的思想原理和优缺点特性。BKD-Tree是基于KD-B-Tree改进而来，而KD-B-Tree又是KD-Tree和B+Tree的结合体，KD-Tree又是我们最熟悉的二叉查找树BST(BinarySearchTree)在多维数据的自然扩展，它是BSP(BinarySpacePartitioning)的一种。B+Tree又是对B-Tree的扩展。以下对这几种树的特点简要描述。3.1.1.FSTFST（FiniteStateTransducers,有穷状态转换器）是搜索引擎倒排索引中支持海量词语高效存储和快速查询的重要数据结构。数值范围查询问题较早的一种不高效的解决方案是：将数值范围查询问题转换成枚举数值范围内全部的可能取值，组成一个候选值集合，然后对该集合执行基于每个元素term的或查询。此方案缺点显而易见：在范围较大是候选值集合容量太大导致查询效率低下，因此实际使用中限制较多。3.1.2.BST二叉查找树BST是最基础的数据结构，它基于二分查找的思想，常见的AVL树和红黑树都是其实现自平衡树的变体，能实现O(lgN)的插入和查找速度，查询非常快。主要通过特定的平衡树插入、删除操作后附带对树节点的调整以保持树的平衡性，从而实现高效的动态数据更新效果。缺点其一是不能处理多维数据，只针对1维数据场景，其二是不适宜处理海量大规模数据。简单解释如下：如果处理海量大规模数据必须要存储到磁盘上时，因为是二叉树（不是多叉树），导致数的高度相对多叉树较高，而且数据本身（或数据本身的地址值）也是存储到树的中间节点（即非叶子节点）上的，导致对数据的读写要经历较长的节点路径（即树高），考虑到每个树节点的访问都需要磁盘IO，导致磁盘IO读写次数也较高，而磁盘IO的读写速度相对内存访问速度会慢很多，因此BST不适宜处理海量大规模数据。3.1.3.B-Tree和B+Tree相对于BST，B-Tree通过增加子节点的个数，减少了树的层级，解决了平衡二叉树磁盘访问效率低的问题，因此B树适宜处理大规模海量数据。同时，B树本身也是一种自平衡树。如同BST一样，B树可以自适应地动态更新数据，通过节点裂变的方式保持自平衡。因此B树的优缺点显而易见：处理1维数据插入、查询和动态更新效率高，但不适宜处理多维数据；同时相对适宜处理海量大规模数据，因为是多叉树，相对于二叉树来说降低了树高，从而降低了节点访问次数，也就是降低了磁盘IO的次数，数据访问效率较高。然后需要注意B-Tree的一个重要特点是：其中间节点（即非叶子节点）上仍然是存储数值数据（或数据本身的地址值）的，不像下文提到的B+树中间节点不存储任何数值数据。这样带来的问题是中间节点因为同时存储了数据和子节点的索引数据，体积相对较大，如果都调入到内存中使得内存利用率不高，相对应地，全部存储数值数据的叶子节点们不能将所有的数值数据都全部包括进来存储到磁盘上，势必导致磁盘空间利用不高。于是就有了B+Tree对这一特性的改进。B+树（B+Tree）是对B树的一种改进，它与B树的不同点主要包括：B+树的所有数据本身都存储在叶子节点上，非叶子节点只存储索引；而B树是叶子节点存储数据本身，非叶子节点既存储数据，又存储索引。B+树的所有叶子节点被一个链表按照数据的从小到大的顺序串联起来。因此B+树上对1维数据的结果集的访问可以不用回溯到非叶子节点直接通过叶子节点链表就可以直接收集，效率比较高。如前文提及，B+树的中间节点不存储数据本身这一特性，使其索引数据的内存利用率更紧凑，相应地数据磁盘存储的空间利用率更高，多叉树相对二叉树极大降低了树高使得费时的磁盘访问次数尽可能地减少了，最终使得B+树较适宜处理1维的海量大规模数据。我们说B+树和B树、BST一样都不适宜处理多维数据，为什么呢？解释如下：在处理1维数据时，B+树和B树、BST的平衡树形式或变种对插入、删除和修改操作都有比较高效的节点调整或裂变等方式来保证树的平衡性，从而保证O（lgN)的高效的时间复杂度。现在假设改为存储了多维数据，那么在插入、删除和修改操作后对相关节点的调整或裂变等附带操作就会带来较大的时间开销：存储1维数据时，父子节点兄弟节点之间的大小有序关系仅存在1个维度上，节点调整或裂变很容易适应1维上的有序关系；而存储多维数据时，父子节点兄弟节点之间的大小有序关系表现在多个维度上，节点调整或裂变操作还需要修改数量较多的离得较远的叶子节点或祖先节点（极限情况可能波及整棵树），导致数据动态更新效率变低。当然有适合处理多维数据的专门的数据结构:KD-Tree。3.1.4.KD-TreeKD-Tree（K-Dimension-Tree)，K维树，顾名思义，是能处理多维数据的树结构。一个典型的KD-Tree的示例如下[2]：它是对6个二维数据点集合：（2,3），（5,4），（9,6），（4,7），（8，1），（7,2）的存储。它先按照X维度值7把空间一分为二得到x7两部分左子树和右子树，接下来对左子树按Y维度4再一分为二，依次递归类推。注意KD-Tree切分数据的维度是依次轮替的：第一层先按X维划分，第二层按Y维度划分，第三层按X维度划分，第4层再按Y维度划分…。接下来循着前几节讨论树特性的几个方面简要讨论一下KD-Tree的特性：首先KD-Tree适宜处理多维数据，查询效率较高。不难知道一个静态多维数据集合建成KD-Tree后查询时间复杂度是O（lgN)。所有节点都存储了数据本身，导致索引数据的内存利用不够紧凑，相应地数据磁盘存储的空间利用不够充分。此外KD-Tree不适宜处理海量数据的动态更新。原因和B树B+树不适宜处理多维数据的动态更新的分析差不多，因为KD-Tree的分层划分是依维度依次轮替进行的，动态更新后调整某个中间节点时，变更的当前维度也同样需要调整其全部子孙节点中的当前维度值，导致对树节点的访问和操作增多，操作耗时增大。可见，KD-Tree更适宜处理的是静态场景的多维海量数据的查询操作。3.1.5.KD-B-TreeKD-B-Tree（K-Dimension-Balanced-Tree）顾名思义，结合了KD-Tree和B+Tree。它主要解决了KD-Tree的二叉树形式树高较高，对磁盘IO不够友好的缺点，引入了B+树的多叉树形式，不仅降低了树高，而且全部数据都存储在叶子节点，增加了磁盘空间存储利用率。一个KD-B-Tree结构的示意图如下。它同样不适宜多维数据的动态更新场景，原因同KD-Tree一样。3.1.6.BKD-TreeBKD-Tree(或BK-D-Tree,全称是Block-K-Dimension-Tree)，顾名思义它是一族或一群（Block）KD-Trees。即它其实是一个森林，不再是一颗树。如前所述，他最早是杜克大学的几位教授在论文[1]中提出的，它是基于KD-B-Tree设计的，同时结合了一种被称为“logarithmicmethod"的方法使得静态数据动态化。区别于KD-B-Tree，它有如下一些特性：不同于KD-B-Tree的多叉树，BKD-Tree是完全二叉树。虽然二叉树不如多叉树的磁盘IO更友好，但是BKD-Tree仍然采用二叉树的形式主要原因可能在于：1）二叉形式实现起来更直观简便；2）采用了完全二叉树的形式，类似于堆或优先级队列，能直接通过下标访问父节点或子节点，减少了存储在中间节点中的索引的存储空间，极简紧凑的中间索引节点占用空间更小，甚至中间节点可以一次性全部调入内存存储，调用内存访问索引节点效率更高。同KD-B-Tree一样，BKD-Tree的全部数据都存储在叶子节点，海量的大规模数据都通过叶子节点存储在外部磁盘上。二叉树的层层分级依照不同子数据集综合统筹的维度空间的切分规划，最终分别落入到每个代表某个相对集中、紧凑和局部相似的局部空间的叶子节点上，全部叶子节点数据空间采用相邻连续存储的方式存储到外部磁盘上，空间利用率高。BKD-Tree最创新的特性在于它采用一种被称为“logarithmicmethod"的方法使得静态数据动态化，极大提高了动态数据更小的效率。简单来说它的思想是采用一个二叉的KD-B-Tree的森林，新增加的数据存储在一个初始支持高效查询和动态更新的小规模数据结构上M，再通过M和多个小的二叉KD-B-Tree以一定的策略和时机合并成大的二叉KD-B-Tree以替换原结构的方式更新数据。此外数据删除可以采取标记删除的方式实现。实现了多维数值数据的高效率动态更新操作。下图是论文[1]中对这种动态更新方式的一个示意图。更深入详细的BKD-Tree原理分析见后文章节。综合以上，下表总结了这几种Tree的使用特点。名称全称能处理多维是数据处理海量数据的空间利用率是否适宜数据动态更新BSTBinarySearchTree否低单维适宜B-TreeBushyTree否中单维适宜B±TreeBushyPlusTree否高单维适宜KD-TreeK-Dimension-Tree是低多维不适宜KD-B-TreeK-Dimension-Balanced-Tree是高多维不适宜BK-D-TreeBlock-K-Dimension-Tree是高多维适宜3.2.BKD-Tree原理分析本节将重点详细展开分析BKD-Tree的原理和算法过程，包含构建、查询、数据动态更新过程。3.2.1.BKD构建算法分析下面的伪代码示意图BuildBKD(A,k,leavesOffset,leavesCount)表达了一个递归构建bkd树结构的算法过程。其中：A：输入数值元素数组，k：维度,leavesOffset：当前子树包含的叶子节点集合起始序号，numLeaves:当前子树中叶子节点个数。在初始阶段，输入元素集合整体对应的叶子节点个数numLeaves值的计算，依赖于一个外部设定的配置值config.maxPointsInLeafNode,其含义为叶节点中最大允许的原始数值数据元素的个数，实际中一般设计为512或1024。numLeaves可以简化理解为由count(A)/config.maxPointsInLeafNode计算得到。其中count(A)是原始输入数据集合中元素的个数。于是BKD递归构建过程BuildBKD(A,k,leavesOffset,numLeaves)初始调用的参数为BuildBKD(A,k,0,numLeaves)。BuildBKD(A,k,leavesOffset,numLeaves)1.ifnumLeaves==1/*递归退出条件*/2.thensortDim1的情况，因为叶子节点个数不止1个，所以要继续切分空间，具体操作过程大体如下：以某种适当的策略选取合适当前递归上下文的切分维度序号：SplitDim;通过父节点为根的子树的叶子节点个数numLeaves结合完全二叉树性质确定未来二叉空间切分后左子树中叶子节点个数numLeftLeafNodes;计算空间切分后左子树中含原始数值元素个数leftCount,显然leftCount=numLeftLeafNodes*config.maxPointsInLeafNode；核心过程：Select(A,splitDim，leftCount)，经典选择问题，选择后要使得A中前leftCount个元素的splitDim维度值都不大于其后的元素。同时不难得出：切分后右子树中叶子结点起始序号rightLeavesOffset可由leavesOffset+numLeftLeafNodes计算得到；最后分别递归构建切分后的左子树BuildBKD(A,k,leavesOffset,numLeftLeafNodes)和右子树BuildBKD(A,k,rightLeavesOffset,numLeaves-numLeftLeafNodes)即可。至此BKD递归构建算法过程分析完毕。虽然过程似乎并不复杂，然而有如下几个细节问题仍需解决：当BuildBKD进入退出条件numLeaves==1分支后，在写当前叶子结点到外部输出介质之前为何还需要按某个sortDim维度对其数据进行排序呢？其中选择sortDim的策略又是什么呢？写当前叶子结点到外部输出介质，具体有什么高效和优化的落地实践方案？比如能否压缩数据以实现尽可能小的数据空间占用，这样后期读BKD数据时磁盘IO也更加友好读取效率也更高。进入进入numLeaves>1的分支后，切分维度splitDim的选择策略是什么？换句话说怎么选当前的切分维度才比较合适？经典选择过程Select(A,splitDim，leftCount)应该采用什么高效优化的选择算法策略来进行？它的时间复杂度是多少？有没有一些技巧性的优化加速过程？以上问题1,2,3,4正是下文要重点分析的内容，其解决方案也正是基于数值索引的高效查询问题在58搜索引擎实践落地的重要方面，此处留待后文详述。不过还是简单分析一下问题1：理论上叶子结点中的原始数值数据集合以任何一种顺序存储到外部介质，对未来的BKD数据读取和查询过程的影响基本是无差别的。之所以按特定策略选择出的维度sortDim值提前排序了，是为了提高问题2涉及的叶节点中数据存储的压缩效率，至于sortDim维度选择策略细节以及为什么就能提高数据存储的压缩效率，留到后文详细展开阐述。3.2.2.BKD查询过程分析假定[minBounds,maxBounds]是由两个k维数值数据构成的k维数值数据的一个范围（Range),那么在BKD结构上基于范围[minBounds,maxBounds]的范围查询问题基本就代表了BKD上的全部查询类型：要查询返回BKD结构上的全体数据集合，只需要将目标范围[minBounds,maxBounds]设置为[-∞,+∞]然后执行bkd上的范围查询即可；要查询返回BKD结构上是否精确包含某个数值x,只需要将目标范围[minBounds,maxBounds]设置为[x,x]然后执行bkd上的范围查询即可；一般来说，对BKD等Tree类数据结构全部节点的访问或查询通常要用到软件设计模式中一种常用的设计模式：Visitor（访问者）模式[3]。Visitor模式是典型的面向对象软件的24种基础设计模式之一，它的意图通常为表示一个作用于某对象结构中各元素的操作。它是你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。下图是该模式的一个典型的结构示意图。一个典型的BKD-Tree的Visitor类可以设计示意如下：classBKDVisitor{/*当前节点及其所有子树中元素集合的范围与目标范围的空间集合关系*/enumRelation{INSIDE_QUERY,/*完全在目标范围内部*/OUTSIDE_QUERY,/*在目标范围外部*/CROSSES_QUERY/*跟目标范围部分交叉*/};public:/*比较当前节点及其所有子树中元素集合的范围与目标范围的空间集合关系*/virtualRelationCompare(minBound,maxBound)=0;/*Compare()返回INSIDE_QUERY时，执行操作的接口*/virtualVisit(intdocId)=0;virtualVisit(docIdSetIteratorit)=0;/*Compare()返回CROSSES_QUERY时，执行操作的接口*/virtualVisit(intdocId,minBound,maxBound)=0;virtualVisit(docIdSetIteratorit,minBound,maxBound)=0;};不难理解，BKDVisitor类中的注释已经非常清楚地表明了这个Visitor类从BKD-Tree的根节点起访问全部子孙节点过程中要执行的操作。我们只需继承该纯虚基类，重新实现5个虚接口函数，将相关的docid和数值数据收集起来，就可以方便地完成基于BKD-Tree数据结构上数据的范围查询过程。3.2.3.BKD数据动态更新策略分析BKD一改传统Tree采用调整父子兄弟节点或节点裂变等方式来动态更新数据的方式，采用"对数法"[logarithmicmethod]策略动态更新：在内存中存储一个大小为M的完全二叉树作为Buffer;在外部存储器（磁盘）上保存的第i棵树，要么是空的，要么大小是M*2^i;每次插入新数据的时候，如果buffer没满，那就直接插入到内存中的Buffer；如果内存buffer满了，则将目前磁盘上所有的树和buffer合并。假设磁盘上最大的树的大小是M*2^i,那么合并后，新生成的一棵树的大小将是M*2^(i+1)。数据删除可以采取以位图标记逻辑删除的方式进行。而修改操作则转化为先删除在新增两个操作进行。4BKD-Tree在58搜索中的实践操作上面我们已经分析了BKD-Tree的主要算法过程的原理，下面将详细展开阐述BKD在58搜索引擎中实践落地的具体策略与细节。我们称包含数值数据的索引为PointIndex(点数值索引)。Point索引以BKD实现，包含多个字段的数值数据，每一个字段的PointIndex是一个独立的BKD-Tree。全部字段的PointIndex持久化到磁盘上以.bkd.data、.bdk.index、.bkd.meta为文件名后缀的3个文件分别存储，分别称为data原始（数值）数据文件、索引文件和meta元数据文件。4.1.BKD数据组织方式BKD-Tree结构的数据大体包含了原始（数值）数据、索引数据和meta元数据3部分：原始（数值）数据：即BKD要读取数据的数值型数据集合数据。这类数据一般规模大，数据元素本身因为维度可能也不小，每个维度数值占用字节也可能不小，因此所占空间一般很大，实际中必须存储到外部磁盘上，读取是通常通过磁盘文件内存映射（Mmap)的方式动态按需调入内存使用，按需淘汰，由操作系统策略管理。这类数据实际存储有数据压缩的必要性，一来本身所占空间就大，二来如果能显著压缩存储空间后通过内存映射方式加载进内存后也能显著降低内存使用量，将更宝贵的内存资源尽可能留给其他两类数据完全加载到内存来提供数据的高效访问辅助。索引数据：可以简单理解为自根向下遍历bkd树节点所需要的那些辅助数据，比如splitPackedValues和splitDimensionValues。这类数据本身所占空间比不是很大（规模可分析，见后文对splitPackedValues和splitDimensionValues规模的分析），但为了提高BKD树的查询速度，一般尽可能将这类数据一次性全完加载到内存用于BKD树读取查询。而内存容量有限，落地实践中一般都尽可能地压缩BKD索引数据所占空间。meta元数据：通常是一些构建和访问BKD树需要的维度相关的前置配置参数值，比如config.numDims,config.bytesPerDim，pointCount,leafCount等。meta元数据一般都是一个常量值，所占空间不大，压缩存储的必要性也不大，使用时也是一次性完全加载到内存中提高高效内存访问。实践中我们将以上3部分数据分别单独存储到独立的磁盘文件上，以文件名后缀区分，分别是：.bkd.data文件-存储原始数值数据；.bdk.index文件-存储索引数据；.bkd.meta文件-存储meta元数据;综合以上，.bkd.data文件和.bdk.index文件存储的两类数据:原始数值数据和索引数据有压缩存储必要性的。后文将详细展开论述压缩存储策略。4.2.BKD数据压缩存储策略如前文描述，BKD-Tree中存储的两类数据:原始数值数据和索引数据是有压缩存储必要性的。对于原始数值数据而言，其被存储到.bkd.data文件中，使用时通过Mmap内存映射方式动态按需加载进内存，由操作系统策略管理。如果显著压缩了这类数据的大小，将会降低Mmap加载映射到内存的空间占用，将更宝贵的内存资源尽可能留给其他两类数据完全加载到内存来提供数据的高效访问辅助。而索引数据是提供高效访问和便利BKD树的辅助数据，只有完全加载到内存才能提供高效访问。而要想完全加载到内存，就必须尽可能压缩这部分数据。当前还有个前提，索引数据本身所占存储空间大小适度，不是特别大，也不是特别小。如果特别大则即使压缩之后也可能在一些极端场景下没有完全加载到内存的可能性；而如果特别小那也没有压缩的必要，因为特别小直接加载进内存即可。（meta元数据之所以未压缩就是因为其所占空间太小，没有压缩的必要，后文还将会详细展开解释一点。）本着索引数据尽可能压缩空间存储的原则出发，接下来将分别阐述原始数值数据和索引数据的BKD压缩存储方法与策略。4.2.1.原始数值数据的压缩存储策略前文3.2.1.节伪代码BuildBKD(A,k,leavesOffset,numLeaves)中第2~4行中的WriteLeafBlockToDataOutput(A,leavesOffset，DataOutput)所做的事情，就是将当前叶子节点所包含的原始数值数据集合块数据写入DataOutput外部文件，即文件名后缀为.bkd.data文件。下面重点分析该算法细节。BKD的叶子节点要存储的原始数值数据包括docIds和pointValues两部分，pointValues是多维数值数据本身，每个pointValue会绑定存储一个对应的docId，docId一般是4字节int类型即可满足应用场景。通过docId关联来定位某个pointValue值属于那篇文档。bkd上执行查询最终返回的结果也是 数据对的集合。一般在构建BKD-Tree前会原始数值数据集合组织成如下图所示的连续数组存放（我们从现在起约定该初始数值数据输入数组为A，其元素个数为count(A)）,可见该数组A是由count(A)个输入数据元素构成，每个数据元素的初始存放格式是若干固定维度的数值之后紧跟一个该数值所述的docId。前节3.2.1中的递归算法BuildBKD本质上就是通过历次中间节点划分空间时对该原始数值数据数组A进行多次选择，以重新排列元素位置的过程（此处的选择算法策略后文将详细展开论述其细节），最终递归算法执行到叶子节点，此时叶子节点包含的原始数值数据只是初始数组A的一个子集M，WriteLeafBlockToDataOutput(M,leavesOffset，DataOutput)要做的就是把子集M中的数据压缩后存储到外部data文件（后缀为.bkd.data）中去，参数中的leavesOffset很容易理解，就是子集M在全集A中的起始偏移量。原始数值数据压缩存储显然包含两部分：docIds和pointValues，下面分别展开详述。4.2.1.1.DocIds压缩存储方案下面的伪代码WriteDocIds(docIdsArr,count,dataOut)表达了docIds的压缩存储策略。参数说明：docIdsArr是叶子节点的数值数据数组，count是其元素个数，dataOut是datafile（即文件名后缀为.bkd.data的文件）的文件句柄。该算法定义了如下5种枚举类型表明5种不同的docIds分布情形，在一开始以1个字节写入，读取时以该1字节值对应枚举值确定docIds存储样式STYLE。enumDOC_ID_STORE_STYLE_ENUM{CONTINUOUS_IDS,BITSET_IDS,DELTA_16_STYLE,MERGE_24_STYLE,SIMPLE_32_STYLE};WriteDocIds(docIdsArr,count,dataOut)1.dataOut->WriteVint(count)2.(min,max,maxMinDiff,strictAsc)WriteByte(CONTINUOUS_IDS)6.dataOut->Writeint(docIdsArr[0])7.elseifcount>=maxMinDiff/168.thendataOut->WriteByte(BITSET_IDS)9.WriteIdsAsBitSet(dataOut,docIdsArr)10.elseifmaxMinDiffWriteByte(DELTA_16_STYLE)12.dataOut->WriteInt(min)13.WriteDiffsOverMin(dataOut,docIdsArr)14.elseifmaxWriteByte(MERGE_24_STYLE)16.WriteMerge24Docids(dataOut,docIdsArr)17.elsedataOut->WriteByte(SIMPLE_32_STYLE)18.WriteSimple32Docids(dataOut,docIdsArr)下面简要分析一下WriteDocIds()算法过程：第1行：存储docId个数；第2行：只需遍历一趟数值数组docIdsArr即可统计获得最小值/最大值:min/max,最大值与最小值的差值maxMinDiff=max-min;strictAsc是个bool变量，其含义是判断数组docIdsArr元素是否严格单调递增，即任意一个元素都严格小于其前一个元素值。第3~6行：如果数组严格单调递增，且maxMinDiff==count,表明是连续无空隙的数值序列，直接写出1个字节CONTINUOUS_IDS值，同时将第1个值写出即可。第7~9行：虽然是严格单调递增数组，但是有空隙，不过数据分布还挺紧密，紧密程度表现为元素个数超过了maxMinDiff/16，则以bitset位图方式存储更省空间；第10~13行：如果maxMinDiffWriteVInt(prefixLengths[dim])3.dataOut->WriteBytes(prefixValues[dim][0...prefixLengths[dim]])2.WriteSuffixes： 顾名思义WriteSuffixes是用来存储全部维度数值的后缀数据的。WriteSuffixes(pointsArr,count,prefixLengths,leafCardinality,sortDim)1.prefixLenSum>[4]中7.4.2节对此伪代码的时间复杂度有详细的理论证明：该选择问题的期望的时间复杂度能达到线性即O(N)(虽然系数可能会大一点)。RandomizedPartition(A,p,r)1.kA[k]3.returnPartition(A,p,r)Partition(A,p,r)1.xA[j]7.exchangeA[i+1]A[r]8.returni+1RandomizedSelect(A,p,r,k)1.ifp==r2.thenreturnA[p]3.qleafBlocksArr)4.newLeafBlocksArr>[4].<>[5].https://github.com/apache/lucene【作者简介】丁斌，硕士毕业于清华大学软件工程专业，58同城TEG搜索推荐部后端架构师，专注于搜索引擎相关技术，主要负责搜索内核功能开发、搜索引擎系统性能优化等搜索相关的后端架构设计和开发工作。