摘要
μ-Tree是直接建立在闪存之上的索引,它克服了传统B+树应用于闪存时引起的"游走树"现象,避免更新一页累及多页的现象.但μ-Tree也存在缺点:占用空间比传统B+树多.为克服μ-Tree存在的缺点,本文提出一套机制改进μ-Tree:k分法模型.在此模型中,我们分析了在给定扇出度F时,k值与总记录数n的关系,以及给定记录数n时,不同大小的索引记录项对k的影响;给出了确定k值的基本方法.实验结果表明,k比例划分可以有效地节省索引所占空间,空间节省最大达50%左右,平均可达39%.所提方法在空间资源受限的环境下具有良好的空间特性.
μ-Tree is the state-of-the-art index supporting efficient random updates on the flash memory.However,we found that it underutilizes the flash memory.To improve the utilization on the memory resources,we propose a novel index scheme called kμ-Tree,where we study a k-partitioning strategy for increasing utilization of the flash memory.The k-partitioning strategy determines an optimal k value for space efficiency by allocating more flash memory to the leaf nodes and guarantees sufficient space for tree growth.The experimental results show that our proposed k-partitioning strategy effectively reduces the index size up to around 50% over μ-Tree with average space conservation about 39%.Our proposed scheme is very promising under the resource-constrained conditions.
出处
《小型微型计算机系统》
CSCD
北大核心
2010年第6期1097-1101,共5页
Journal of Chinese Computer Systems
基金
国家"八六三"高技术研究发展计划项目(2007AA01Z153)资助
浙江省基金项目(Y1090096
Y1080102)资助
