kμ-Tree: 一种空间有效的嵌入式闪存数据库索引

摘要：

μ-Tree是直接建立在闪存之上的索引,它克服了传统B+树应用于闪存时引起的"游走树"现象,避免更新一页累及多页的现象.但μ-Tree也存在缺点:占用空间比传统B+树多.为克服μ-Tree存在的缺点,本文提出一套机制改进μ-Tree:k分法模型.在此模型中,我们分析了在给定扇出度F时,k值与总记录数n的关系,以及给定记录数n时,不同大小的索引记录项对k的影响;给出了确定k值的基本方法.实验结果表明,k比例划分可以有效地节省索引所占空间,空间节省最大达50%左右,平均可达39%.所提方法在空间资源受限的环境下具有良好的空间特性.

关键词：数据库索引、闪存数据库、μ-tree、嵌入式数据库

所属期刊栏目：31

分类号：TP303(计算技术、计算机技术)

资助基金：国家"八六三"高技术研究发展计划项目2007AA01Z153;浙江省基金项目Y1090096、Y1080102

在线出版日期：2010-07-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1097-1101