Frequent access B+-Tree based on chip multi-processor

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (25): 160-164.

• 数据库、信号与信息处理 • Previous Articles Next Articles

Frequent access B+-Tree based on chip multi-processor

HE Wei1，2，ZHANG Fang1，3，ZHONG Yanwen2，LUO Xiaozhu2，YANG Xiaomin4

1.National University of Defence Technology，Changsha 410000，China
2.Hunan Provincial Meteorological Station，Changsha 410007，China
3.Hunan Province Meteorological Science and Technology Service Center，Changsha 410007，China
4.Hunan Province Meteorological Training Center，Changsha 410125，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-09-01 Published:2011-09-01

多核处理器中支持频繁访问的B+-Tree

贺炜1，2，张芳1，3，钟艳雯2，罗小珠2 ，杨小民4

1.国防科技大学，长沙 410000
2.湖南省气象台，长沙 410007
3.湖南省气象科技服务中心，长沙 410007
4.湖南省气象培训中心，长沙 410125

Abstract

Abstract: Aiming at traditional top-down access model of B+-Tree，this paper presents FAB+-Tree（Frequent Access B+-Tree），which is based on B+-Tree and supplemented by a Hash indexing，and the Hash indexing can let FAB+-Tree access leaf nodes directly.Memory-based direct-access table and bit vector are used to improve the update performance.At the same time，based on shared Cache CMP，it presents multithreaded FAB+-Tree access module using pipelined execution model.In the experiments，FAB+-Tree and multithreaded FAB+-Tree access module are implemented in INGRES.The performance analysis and experimental results show that performance of B+-Tree is improved remarkably.

Key words: B+-Tree, Frequent Access B+-Tree（FAB+-Tree）, chip multi-processor, bottom-up access

摘要： 针对传统B+-Tree自顶向下访问模式的缺点，提出了支持频繁访问的FAB+-Tree（Frequent Access B+-Tree）。在B+-Tree的基础上增加了Hash辅助索引，使得访问B+-Tree时直接定位到叶结点，并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器，提出了基于流水线的FAB+-Tree多线程访问模块，并优化了该模块的共享Cache访问性能。在实验中，基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块，实验结果表明B+-Tree的访问性能得到显著提高。

关键词: B+-Tree, 频繁访问的B+-Tree（FAB+-Tree）, 多核处理器, 自底向上访问

HE Wei1，2，ZHANG Fang1，3，ZHONG Yanwen2，LUO Xiaozhu2，YANG Xiaomin4. Frequent access B+-Tree based on chip multi-processor[J]. Computer Engineering and Applications, 2011, 47(25): 160-164.

贺炜1，2，张芳1，3，钟艳雯2，罗小珠2 ，杨小民4. 多核处理器中支持频繁访问的B+-Tree[J]. 计算机工程与应用, 2011, 47(25): 160-164.

[1]	CAO Fei. Ring connected CMP simulator：Godson-Ring [J]. Computer Engineering and Applications, 2013, 49(9): 13-18.
[2]	GUO Xiaofang1, LI Feng2, YE Hua1. Similarity search for multivariate time series based on B+-tree index [J]. Computer Engineering and Applications, 2013, 49(22): 139-142.

Frequent access B+-Tree based on chip multi-processor

多核处理器中支持频繁访问的B+-Tree

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics