μ*-Tree: An Ordered Index Structure for NAND Flash Memory with Adaptive Page Layout Scheme

被引:12
作者
Ahn, Jung-Sang [1 ]
Kang, Dongwon [2 ]
Jung, Dawoon [3 ]
Kim, Jin-Soo [4 ]
Maeng, Seungryoul [1 ]
机构
[1] Korea Adv Inst Sci & Technol, Dept Comp Sci, Taejon 305701, South Korea
[2] Google Korea LLC, Seoul, South Korea
[3] Samsung Elect Corp, Memory Div, Hwasung, South Korea
[4] Sungkyunkwan Univ, Sch Informat & Commun Engn, Suwon, South Korea
基金
新加坡国家研究基金会;
关键词
NAND flash memory; index structure; B+-Tree; B-TREE;
D O I
10.1109/TC.2012.20
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
As NAND flash memory is gaining popularity as a storage medium for mobile embedded devices, many flash-aware file systems, flash-aware DBMSes, and flash translation layers (FTLs) require an flash-efficient index structure. This paper proposes a novel index structure called mu*-Tree which natively works on NAND flash memory, aiming at improving performance over B+-Tree. mu*-Tree stores all the nodes along the path from the root to the leaf into a single flash memory page in order to minimize the number of flash write operation when a node is updated. Furthermore, mu*-Tree has an adaptive page layout scheme which dynamically adjusts the page layout according to the workload characteristics on-the-fly. mu*-Tree also allows flash pages with different page layouts to coexist in the same tree. Our evaluation results with real workload traces show that mu*-Tree outperforms B+-Tree by up to 55 percent in terms of the time needed for flash operations. With a small in-memory cache of 32 KB, mu*-Tree improves the overall performance by up to five times compared to B+-Tree with the same cache size.
引用
收藏
页码:784 / 797
页数:14
相关论文
共 17 条
  • [1] Agrawal D, 2009, P INT C VER LARG DAT
  • [2] Bayer R., 1972, Acta Informatica, V1, P173, DOI 10.1007/BF00288683
  • [3] Chiang ML, 1999, SOFTWARE PRACT EXPER, V29, P267, DOI 10.1002/(SICI)1097-024X(199903)29:3<267::AID-SPE233>3.0.CO
  • [4] 2-T
  • [5] UBIQUITOUS B-TREE
    COMER, D
    [J]. COMPUTING SURVEYS, 1979, 11 (02) : 121 - 137
  • [6] On the Lambert W function
    Corless, RM
    Gonnet, GH
    Hare, DEG
    Jeffrey, DJ
    Knuth, DE
    [J]. ADVANCES IN COMPUTATIONAL MATHEMATICS, 1996, 5 (04) : 329 - 359
  • [7] Kang D, 2007, P INT C EMB SYST SOF
  • [8] Kim G.J, 2006, P INT C VER LARG DAT
  • [9] Decreased vasomotor reactivity in Alzheimer's disease
    Lee, Soon-Tae
    Jung, Keun-Hwa
    Lee, Yong-Seok
    [J]. JOURNAL OF CLINICAL NEUROLOGY, 2007, 3 (01): : 18 - 23
  • [10] Lee Y.-G, 2008, P INT C EMB SYST SOF