可持久化CSB+-树索引技术研究  

Research on Durable CSB+-Tree Indexing Technology

作　　者：王胜[1] 秦小麟[1] 沈尧[1] 李博涵[1] 史文浩[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学与探索》2015年第2期182-192,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;高等学校博士学科点专项科研基金;江苏高校优势学科建设工程资助项目;中央高校基本科研业务费专项资金;江苏省研究生培养创新工程;江苏省自然科学基金青年基金;云计算-南航-大数据处理引擎技术研究项目~~

摘　　要：现有主存索引方案为实现重用功能仅将更新操作存储到硬盘中,根据操作序列进行索引恢复,实时性和重用性均较差。为进一步提升重用性和实时性,提出了一种可持久化的CSB+-树(cache sensitive B+-tree)索引方案。该方案基于内存映射技术,完整而高效地将索引结构保存到外存中,导入时无需重复创建索引,可节省大量计算资源。针对索引更新过程中出现大量内存碎片问题,采用一种分类内存管理机制进行管理和监视,当内存碎片过多而无法利用时,基于有序键值对进行索引重构以完全消除内存碎片。实验结果表明,所提方案与现有方案相比具有更好的实时性和重用性,同时具有高效的查询处理能力。To achieve the function of reusing, existing main-memory indexing schemes only store the update opera- tion to the disk and recover the index according to the operating sequence, and are less reusable and real-time. To improve the reusability and efficiency further, this paper proposes a durable CSB＋-tree （cache sensitive B＋-tree） indexing scheme based on memory mapping technology, which stores the index structure into the disk completely and efficiently, and doesn＇ t need to build the index when loaded. For the problem of memory fragmentation during updating the index, this paper uses a classified memory managing scheme to monitor, and employs a rebuilding mechanism based on the sorted key-value pairs to wipe out the fragmentation when it is too much to reuse. The experimental results show that compared with the existing schemes, the proposed scheme is more real-time and reusable, with efficient querying performance.

关 键 词：主存索引 持久化 CSB+-树 内存映射 索引头 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]