ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Dynamic In-Page Logging for B-Tree Index
Cited 15 time in scopus Download 3 time Share share facebook twitter linkedin kakaostory
Authors
Gap-Joo Na, Sang-Won Lee, Bongki Moon
Issue Date
2012-07
Citation
IEEE Transactions on Knowledge and Data Engineering, v.24, no.7, pp.1231-1243
ISSN
1041-4347
Publisher
IEEE
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1109/TKDE.2011.32
Project Code
11VS1500, STB open platform development which provides various integrated broadcasting/tele-communication services and contents, Kyung Hee Lee
Abstract
Unlike database tables, B +-tree indexes are hierarchical and their structures change over time by node splitting operations, which may propagate changes from one node to another. The node splitting operation is difficult for the basic In-Page Logging (IPL) scheme to deal with, because it involves more than one node that may be stored separately in different flash blocks. In this paper, we propose Dynamic IPL B +-tree (d-IPL B +-tree in short) as a variant of the IPL scheme tailored for flash-based B +-tree indexes. The d-IPL B +-tree addresses the problem of frequent log overflow by allocating a log area in a flash block dynamically. It also avoids a page evaporation problem, imposed by the contemporary NAND flash chips, by introducing ghost nodes to d-IPL B +-tree. This simple but elegant design of the d-IPL B +-tree provides significant performance improvement over existing approaches. For a random insertion workload, the d-IPL B +-tree outperformed a B +-tree with the plain IPL scheme by more than a factor of two in terms of page write and block erase operations. © 2012 IEEE.
KSP Keywords
B+-tree, Existing Approaches, Flash-based, NAND Flash, Over time, database tables, performance improvement, tree index