６期丁治明等：面向物联网海量传感器采样数据管理的数据库集群系统框架
１１８５
５．２．１ 分布式全局关键字索引及全局关键字查询
为了在Ｉ需ｏＴ－ＣｌｕｓｔｅｒＤＢ中支持关键字查询，要建立一个全局关键字Ｂ＋树索引（ＧｌｏｂａｌＦｕｌｌ －
，），图６给ＴｅｘｔＫｅｗｏｒｄＢ＋－ＴｒｅｅＧＦＴＫＢ＋－Ｔｒｅｅ ｙ出了ＧＦＴＫＢ＋－Ｔｒｅｅ的结构
．
（是所有包含该关键字的所有元组的标识ｓｅｔｔｕＩＤ）ｐ集合．
让我们结合第４．２．４小节中的查询Ｑ１和Ｑ２来在Ｉ讨论对全局关键字查询的处理．ｏＴ－ＣｌｕｓｔｅｒＤＢ中，所有的查询均发送给根结点进行处理．当根结点接收到一个关键字查询时，将首先查询ＧＫＲ－
，从而判断应该进一步查询哪个叶结点的Ｔａｂｌｅ；然后，根据对应叶结点的ＫＫＳＭＢ＋－ＴｒｅｅＳＭＢ＋－，可以得到一组叶结点的ｓ这些叶结点均ＴｒｅｅｉｔｅＩＤ，包含被查询的关键字；最后，根结点将查询广播给这些叶结点并行执行，执行结果由根结点汇总并返回给查询用户．各叶结点在执行来自于根结点的关键字查询时，将调用本地的ＬＦＴＫＢ＋－Ｔｒｅｅ快速地得到查询结果．
算法１给出了全局关键字查询的处理过程．算法１． 全局关键字查询处理算法．
输入：全局关键字索引 ＧＦＴＫＢ＋－Ｔｒｅｅ
关键字查询
输出：查询结果
图６ ＧＦＴＫＢ＋－Ｔｒｅｅ的结构
如图６所示，ＧＦＴＫＢ－Ｔｒｅｅ是一个分布式的
索引，采用３层结构，其中：
＋
ＱＲ
第１层是存放在ＩｏＴ－ＣｌｕｓｔｅｒＤＢ根结点中的全，局关键字分区表（ＧｌｏｂａｌＫｅｗｏｒｄＲａｎｅＴａｂｌｅ ｙｇ）ＧＫＲ－Ｔａｂｌｅ．ＧＫＲ－Ｔａｂｌｅ的记录格式为（ｋｅＲ－ｙ
，其中ｋａｎｅ，ｓｉｔｅＩＤ）ｅＲａｎｅ是关键字值域中的一ｇｙｇ个区域范围，ｓｉｔｅＩＤ是与该范围相对应的叶结点的该叶结点中的Ｋ标识，ＳＭＢ＋－Ｔｒｅｅ索引该范围内的关键字．
第２层是一组存放在ＩｏＴ－ＣｌｕｓｔｅｒＤＢ各叶结点中的ｋｅｗｏｒｄ到ＳｉｔｅＩＤ的映射Ｂ＋树（ｋｅｗｏｒｄｔｏ－－ｙｙ
，）ＳｉｔｅＩＤ ＭａｉｎＢ＋－ＴｒｅｅＫＳＭＢ＋－Ｔｒｅｅ．ＫＳＭＢ＋－ｐｐｇ （），Ｔｒｅｅ的叶结点记录格式为（ｋｅｗｏｒｄ，ｓｅｔｓｉｔｅＩＤ）ｙ（其中ｋ是所有包含该ｅｗｏｒｄ是关键字，ｓｅｔｓｉｔｅＩＤ）ｙ关键字的叶结点的标识的集合．在创建ＫＳＭＢ＋－
每个叶结点从自己的本地元组中提取关键Ｔｒｅｅ时，字，并对每个关键字生成一个（偶ｋｅｗｏｒｄ，ｓｉｔｅＩＤ）ｙ；对（其中ｓ随后，ｉｔｅＩＤ即为该叶结点自己的标识）该叶结点根据ＧＫＲ－Ｔａｂｌｅ将各个偶对发送给相应的叶结点，这样每个叶结点可以收到一组来自于整个系统中其它各个叶结点的（集ｋｅｗｏｒｄ，ｓｉｔｅＩＤ）ｙ合，并在此基础上构建ＫＳＭＢ＋－Ｔｒｅｅ．
第３层是一组存放在ＩｏＴ－ＣｌｕｓｔｅｒＤＢ叶结点中的本地全文关键字Ｂ＋树索引（ＬｏｃａｌＦｕｌｌｅｘｔ －Ｔ＋＋
，）ＫｅｗｏｒｄＢｒｅｅＩｎｄｅｘＬＦＴＫＢｒｅｅ．ＬＦＴＫＢ＋－ －Ｔ －ＴｙＴｒｅｅ是ＩｏＴ－ＮｏｄｅＤＢ针对本地数据建立的全文关
键字索引，其叶结点的记录格式为（ｋｅｗｏｒｄ，ｙ（），其中ｋｓｅｔｔｕＩＤ）ｅｗｏｒｄ是一个关键字，ｐｙ
；１．ｋｅＱ）ｅｔｋｅｙ＝ｇｙ（
＋
＿（）；２．ｋｓｍｂｓｉｔｅ＝ｒｅｔｒｉｅｖｅｋｅＧＦＴＫＢｒｅｅ．ＧＫＲａｂｌｅ－Ｔ－Ｔｙ，＿＿（＿）；ｅｔ３．ｋｓｍｂｔｒｅｅ＝ｇｔｒｅｅｋｓｍｂｓｉｔｅ，ＫＳＭＢ＋－Ｔｒｅｅ＿（＿）；４．ｌｔｋｂｓｉｔｅｓ＝ｒｅｔｒｉｅｖｅｋｅｋｓｍｂｔｒｅｅｆｙ，＿）５．ＦＯＲＥＡＣＨｓｉｔｅｌｔｋｂｓｉｔｅｓＤＯ（ＩＮＰＡＲＡＬＬＥＬ ∈ ｆ＿＿（）；６． ｌｔｋｂｔｒｅｅ＝ｇｔｒｅｅｓｉｔｅ，ＬＦＴＫＢ＋－Ｔｒｅｅｅｔｆ（＿）；７． ｔｕｌｅｉｄｓ＝ｒｅｔｒｉｖｅｋｅｌｔｋｂｔｒｅｅｐｙ，ｆ
（）；８． ｒｅｓ＝ｅｖａｌｕａｔｅＱ，ｔｕｌｅｉｄｓｐ（）；９． ｓｅｎｄＭａｓｔｅｒｒｅｓ
１０．ＥＮＤＦＯＲ；
根结点收集各叶结点发来的查询结果并存入Ｒ；１１．
（１２．ＲｅｔｕｒｎＲ）．
在算法１中，函数返回查询Ｑ要检ｅｔｋｅＱ）ｇｙ（
（（）函数根据关键字ｋ索的关键字；ｒｅｔｒｉｅｖｅｋｅｄｓｅｙ，ｙ在数据结构ｄ并返回相应的结果；ｓ中进行检索，＿（函数返回指定叶结点ｓｅｔｔｒｅｅｓｉｔｅ，ｔｒｅｅＮａｍｅ）ｉｔｅｇ
中的ｔ函ｒｅｅＮａｍｅ索引子树，ｅｖａｌｕａｔｅ（Ｑ，ｔｕｌｅｉｄｓ）ｐ数在ｔｕｌｅｉｄｓ元组集合的基础上执行查询并返回结ｐ
）果，将结果ｒｓｅｎｄＭａｓｔｅｒ（ｒｅｓｅｓ发送给根结点．５．２．２ 分布式全局时空索引及全局时空查询处理
物联网系统中的另一类重除了关键字查询之外，要的查询类型是带有时空约束条件的查询，如第４．２．４小节中的查询Ｑ为了支持这类查询，我们需４和Ｑ５．要建立全局时空Ｒ树索引（ＧｌｏｂａｌＳａｔｉａｌｅｍｏｒａｌ －Ｔｐｐ，）由于在ＩｒｅｅＧＳＴＲ－Ｔｒｅｅ．ｏＴ－ＣｌｕｓｔｅｒＤＢ中数Ｒ－Ｔ
据是根据其空间属性进行分布的，因此ＧＳＴＲ－Ｔｒｅｅ的构建可以得到简化，图７给出了其总体结构．
１１８６
计 算 机 学 报２０１２年
从图８可以看出，移动监控对象时空轨迹的变化十分频繁，因为每一次新采样值的到来均会导致向轨迹中插入新的轨迹单元（轨迹单元是轨迹时空如果直曲线中相邻两个采样点构成的一条直线段）．接以轨迹单元作为索引记录的基本单位，则索引的更新频率将等同于采样数据插入数据库的频率，从而导致索引更新代价升高．
为了解决上述问题，我们首先将Ｘ×Ｙ×Ｔ空间划分成粒度较粗的等距格栅．然后，将每个移动监概略化”轨迹，概略化控对象的轨迹映射成对应的“
图７ ＧＳＴＲ－Ｔｒｅｅ的结构
轨迹单元是原始轨迹所穿过的格栅单元的中心点连线，因此其粒度比原始轨迹要大得多．最后对概略化轨迹单元进行索引并建立ＧＳＳＴＲ－Ｔｒｅｅ．
