基于分布式内存数据库的移动对象全时态索引

Full-temporal Index of Moving Objects Based on Distributed Main Memory Database

针对现有移动索引仅对内存/磁盘两层结构进行优化,忽略了索引节点在内存中的缓存敏感性,提出一种基于分布式内存数据库的全时态索引结构DFTB^x树。该索引结构针对存储器Cache、内存和磁盘3层结构进行优化,根据Cache行、指令数量和TLB失配数等多个条件设计内存索引节点的大小。同时,根据磁盘数据页的大小设计历史数据迁移链节点的大小,使得Cache和内存能够一次读取索引节点和迁移链节点数据,避免多次读取数据带来的延迟。此外,构建历史数据迁移链,实现历史数据持久化,从而支持移动对象全时态索引。实验结果表明:与Bx树、Bdual树、TPR*树和STRIPES算法相比,DFTBx树具有较高的查询和更新效率。

Due to the traditional index of moving objects ignores the cache-conscious of index nodes,only the two-layer memory/disk hierarchy is optimized. Thus, this paper proposed a novel full-temporal index structure named DFTBX-tree based on the distributed main memory database. The optimization of new index structure includes the Cache, the main memory and the hard disk. The size of index nodes is set according to many conditions such as Cache line, the number of instructions and the number of TLB mismatches. Meanwhile, the size of historical data migration nodes is designed a ccording to the size of the disk data pages. Therefore, the cache and the main memory can read the data of interior node or leaf node at a time, to avoid the delay caused by multiple data reads. Moreover, the full-temporal index of mo- ving objects is supported by historical data which is linked through a migration chain. Compared with other algorithms, the experiment shows that DFTBX-tree has higher efficiency in query and update operations.