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

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

为解决现有闪存数据库索引机制无法同时具备高索引更新性能和高检索性能的问题,提出一种应用于闪存数据库的高效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.