ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Dynamic In-Page Logging for B-Tree Index
Cited 12 time in scopus Download 1 time Share share facebook twitter linkedin kakaostory
저자
나갑주, 이상원, 문봉기
발행일
201207
출처
IEEE Transactions on Knowledge and Data Engineering, v.24 no.7, pp.1231-1243
ISSN
1041-4347
출판사
IEEE
DOI
https://dx.doi.org/10.1109/TKDE.2011.32
협약과제
11VS1500, 다양한 방송 통신 서비스와 콘텐츠를 통합 제공하는 셋톱박스 오픈 플랫폼 개발, 이경희
초록
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.
키워드
B+-tree, Dynamic in-page logging, flash memory indexing
KSP 제안 키워드
B+-tree, Existing Approaches, Flash Memory, Flash-based, Memory indexing, NAND Flash, Over time, database tables, performance improvement, tree index