Page 226 - 《软件学报》2020年第10期

3202 Journal of Software 软件学报 Vol.31, No.10, October 2020

为 r.自顶向下地对空间位置进行四等分直至层数 r.在任意层次 h(h≤r)下,将 SW、SE、NW、NE 这 4 个方向的
等分区域分别标记为 0、1、2、3,如图 6(a)所示.在空间上建立四分树(如图 6(b)所示).四分树上一个 h 层的空间
位置可用一个 h 位的四进制串表示,称为位置 Morton 码.如在图 6(b)所示的第 3 层,任意一个空间位置都是一个
3 位的四进制串.四进制串中从左向右的任意一位表示的是该位置在相应层次的方向.具体地,第 3 层的 Morton
码左侧第 1 位数字表示该节点在四分树深度为 1 时区域位于的方向.如图 6(b)所示的中间 4 个区域的编码为
120、121、122、123,其中左侧第 1 位的“1”表示这 4 个区域均处于四分树第 1 层的 SE 方向.左侧第 2 位数字
表示深度为 2 时该节点所属区域的方向.继续上面的例子,左侧第 2 位的“2”表示这 4 个区域均处于四分树第 2
层划分的 NW 方向.第 3 位的 0、1、2、3 表示第 3 层上 4 个方向的划分.在线性四分树中索引的均是底层(最深
层)的 Morton 码.因此,采用 Morton 码对图 1 所示的空间进行编码,图 3 和图 6(b)所示的最底层叶子节点编码是
一致的.

(a) (b)
Fig.6 Encoded Morton
图 6 Morton 编码
线性四分树是将上述非空叶子节点的四进制 Morton 码值以数字的形式索引起来.综上所述,聚集线性四分
树 AIL 的创建算法如算法 1 所示.
算法 1. 构建倒排聚集线性四分树 AIL.
Input:空间文本对象集合 O,关键字域值 D;
Output:倒排聚集线性四分树 AIL.
1. 为所有的查询关键字创建倒排表 AIL;
2. for 每一个对象 o∈O
3. cm=计算对象 o 的 Morton 码;
4. for 关键字 w∈o.T //对于对象 o 中的每一个关键字
5. if cm 不在关键字 w 对应的 B+−树中
6. 将 cm 插入到 w 对应的 B+−树;
7. else
8. 在 cm 对应的叶子节点中添加对象 o;
9. 为 AIL 中所有的节点添加聚集值;