• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >In-Depth Analysis of Concurrent B-Tree Algorithms
【24h】

In-Depth Analysis of Concurrent B-Tree Algorithms

机译：并行B树算法的深入分析

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The B tree is a data structure designed to efficiently support dictionaryoperations for a variety of applications. In order to increase throughput, many algorithms have been proposed to maintain concurrent operations on B-tree. Replicating objects in memory can play a large role in concurrent B-tree performance, especially for large distributed and parallel systems. Because most replication schemes are coherent, readers generally cannot operate concurrently with a writer. This thesis presents two new concurrent B-tree algorithms. The first is a link algorithm that uses coherent replication; it is based on the Lehman-Yao algorithm which performs better than any other proposed concurrent B-tree algorithm. The second is a similar algorithm that uses multi-version memory, a new semantics for replicated memory. Multi-version memory weakens the semantics of coherent replication by allowing readers to read old versions of data. As a result, readers can perform in parallel with a writer. Also, implementations of multi-version memory require less communication and synchronization. Simulation experiments comparing a variety of concurrent B-tree algorithms show that the first algorithm has better performance than previously proposed algorithms and that the second algorithm has significantly better performance and scaling properties than any algorithms using coherent replicated memory.

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号