Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14]


Journal of Information Science and Engineering, Vol. 30 No. 1, pp. 85-106 (January 2014)

AS B-tree: A Study of an Efficient B+-tree for SSDs*

1Department of Computer Science
Yonsei University
Seoul, 120-749 Korea
2Department of Computer Science and Engineering
Sogang University
Seoul, 121-742 Korea

Recently, flash memory has been utilized as the primary storage device in mobile devices. SSDs have been gaining popularity as the primary storage device in laptop and desktop computers and even in enterprise-level server machines. SSDs have an array of NAND flash memory packages and are therefore able to achieve concurrent parallel access to one or more flash memory packages. In order to take advantage of the internal parallelism of an SSD, it is beneficial for DBMSs to request input/output (I/O) operations on sequential logical block addresses (LBAs). However, the B+-tree structure, which is a representative index scheme of current relational DBMSs, produces excessive I/O operations in random order when its node structures are updated. Therefore, the conventional B+-tree structure is unfavorable for use in SSDs. In this paper, we propose the Always Sequential (AS) B-tree which consists of the Legacy B+-tree structure, a Sequential Writer, a Write Buffer, an Address Mapping Table, and a Node Validation Manager. All of the modified nodes in the Legacy B+-tree are stored in the Write Buffer. If the Write Buffer is full, the Sequential Writer contiguously writes each node of the Write Buffer at the end of the file. To support this algorithm, the Address Mapping Table links NodeIDs of the Legacy B+-tree to the LBA of the corresponding node. Because AS B-tree writes the modified nodes on sequential LBAs in this same manner, it is able to take advantage of the internal parallelism of SSDs. In the experiments presented as part of this paper, AS B-tree enhanced the insertion performance of the conventional B+-Tree by 21%. We also confirmed AS B-tree demonstrates better performance than other flash-aware indexes in search-oriented workloads.

Keywords: flash memory, B+-tree, FTL, SSD, parallelism

Full Text () Retrieve PDF document (201401_05.pdf)

Received October 30, 2011; revised December 27, 2011 & February 22 & March 28, 2012; accepted April 2, 2012.
Communicated by Sangyeun Cho.
* This research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2012R1A2A1A01010775).
+ The first two authors contributed equally to this work.
++ Correspondence author.