开始

节点

是否为叶子节点?

选出叶子节点的排序维度

选出切分维度

内部节点的排序

设置splitPackedValues数组

第一次更新parentSplits数组

u143_seg0 u143_seg1
u144_seg0 u144_seg1
u145_seg0 u145_seg1
u146_seg0 u146_seg1
u147_seg0 u147_seg1
u148_seg0 u148_seg1
u149_seg0 u149_seg1

设置左子树的准备数据

设置右子树的准备数据

u152_seg0 u152_seg1
u153_seg0 u153_seg1
u154_seg0 u154_seg1 u154_seg2 u154_seg3 u154_seg4
u155_seg0 u155_seg1 u155_seg2 u155_seg3 u155_seg4

处理左子树

处理右子树

第二次更新parentSplits数组

u159_seg0 u159_seg1
u160_seg0 u160_seg1

叶子节点的排序

更新leafBlockFPs数组

写入文档号信息到索引文件.dim中

写入相同前缀信息到索引文件.dim中

写入不同后缀信息到索引文件.dim中

返回

u167_seg0 u167_seg1
u168_seg0 u168_seg1
u169_seg0 u169_seg1
u170_seg0 u170_seg1
u171_seg0 u171_seg1
u172_seg0 u172_seg1

处理叶子节点

处理内部节点

当前节点是否

为根节点?

结束

u177_seg0 u177_seg1 u177_seg2

u181_seg0 u181_seg1 u181_seg2

构建BKD树的节点值(node value)流程图

维度值大于等于2(Lucene 7.5.0)

开始

节点

节点内的点数据排序

是否还有未处理

的点数据?

写入文档号信息到索引文件.kdd中

写入相同前缀信息到索引文件.kdd中

写入不同后缀信息到索引文件.kdd中

统计leafCardinality

以及其他一些信息

结束

是否生成

一个叶子节点?

u194_seg0 u194_seg1
u195_seg0 u195_seg1
u196_seg0 u196_seg1
u197_seg0 u197_seg1
u198_seg0 u198_seg1
u199_seg0 u199_seg1 u199_seg2
u200_seg0 u200_seg1 u200_seg2 u200_seg3 u200_seg4
u201_seg0 u201_seg1 u201_seg2 u201_seg3

构建BKD树的节点值(node value)流程图

维度值等于1(Lucene 8.7.0)

更新leafBlockFPs数组

u208_seg0 u208_seg1
u209_seg0 u209_seg1
u210_seg0 u210_seg1
u211_seg0 u211_seg1 u211_seg2 u211_seg3