一种应用于闪存数据库的高效B+树索引机制  

An Efficient B+ Tree Index Mechanism for Flash-based Database

作　　者：周斯忠[1] 陈耀武[1] 

机构地区：[1]浙江大学数字技术及仪器研究所,杭州310027

出　　处：《计算机工程》2013年第9期1-5,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(40927001);浙江省级重点科技创新团队基金资助项目(2011R09021-02)

摘　　要：为解决现有闪存数据库索引机制无法同时具备高索引更新性能和高检索性能的问题,提出一种应用于闪存数据库的高效B+树索引机制。该机制采用日志方式更新索引,利用日志缓存区保证日志快速写入闪存。针对日志方式检索效率低的缺陷,设计节点日志映射表,通过哈希映射直接索引节点更新记录,避免全局搜索节点日志。将更新日志整合为B+树逻辑节点,使索引检索转化为B+树深度搜索,在此基础上设计节点缓存区,提高节点检索效率。实验结果表明,该机制相比日志型索引机制BFTL,更新效率提高了51%、检索效率提高了2.3倍,相比基于Nand闪存转换层的B+树索引机制,在保证与其相当的高检索效率的同时,更新效率提高了2.4倍。To solve the problem that current flash-based database index mechanisms do not have both high update and query performance, this paper proposes an Efficient B＋ Tree Indexing Mechanism（EBTIM） for flash-based database. EBTIM updates the index through log method, and a buffer is designed to ensure that loges are efficiently written to flash. Due to low index query efficiency of log update method, a node-log map table is designed to avoid global search log for index. Meanwhile at the right time loges are integrated into the B＋ tree logic node to optimize the index query. Furthermore, a node cache is designed to improve the index query efficiency. A Experi- mental result show that EBTIM improves the update efficiency by 51% and query efficiency by 2.3 times compared tO BFTL, and it has the same query efficiency of B＋ tree index mechanism based on Nand Flash Translation Layer（NFTL）, but it improves the update efficiency by 2.4 times compared to NFTL.

关 键 词：闪存数据库 B+树 日志结构索引 节点日志映射表 日志整合 节点缓存区 

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