一种支持高效并发访问的移动对象索引

针对移动对象当前及未来位置索引不能有效支持多用户并发访问的问题,提出了一种支持高效并发访问的移动对象索引CS2B-tree(Concurrent Space-filling curve enabled Cache Sensitive B+-tree)。该索引结合了Bx-tree和CSB+-tree的特点,因而能够支持对移动对象进行预测查询且具有缓存敏感特性。重点研究了一种针对CS2B-tree的两层锁并发访问机制,特别是设计了一种网格锁备忘录结构,使得索引能够支持多任务并发执行。基于并发访问机制,分别提出了CS2B-tree的并发更新算法及并发预测范围查询算法。实验表明,相对于Bx-tree,CS2B-tree的并发访问的吞吐量提高了15.1%,响应时间减少了14.9%。

An Efficient Moving Object Index that Supports Concurrent Access

Current literature on indexing current and future positions of the moving objects lacks the mechanisms on concurrent access. To solve this problem, the current research proposed an efficient moving object index that supports concurrent access, also called CS²B-tree(Concurrent Space-filling curve enabled Cache Sensitive B⁺-tree). CS²B-tree combines the characteristics of the B^x-tree and CSB⁺-tree, thus it can support querying the predicted future positions of the moving objects and is cache sensitive. Focus was put on studying a concurrent access mechanism to CS²B-tree which resulted in a two-level lock mechanism and particularly a lock memo structure was designed. Based on the concurrent access mechanism, a CS²B-tree concurrent location update algorithm and a concurrent predicted range query algorithm were proposed respectively. Experimental results show that, compared with B^x-tree, the throughput of the CS²B-tree improves by 15.1%, and the response time decreases by 14.9%.