A study on the enhancement of the insertion performance of B-tree on SSD


The KIPS Transactions:PartD, Vol. 18, No. 3, pp. 157-168, Jun. 2011
10.3745/KIPSTD.2011.18.3.157,   PDF Download:

Abstract

Recently flash memory has been being utilized as a main storage device in mobile devices, and flashSSDs are getting popularity as a major storage device in laptop and desktop computers, and even in enterprise-level server machines. Unlike HDDs, on flash memory, the overwrite operation is not able to be performed unless it is preceded by the erase operation to the same block. To address this, FTL(Flash memory Translation Layer) is employed on flash memory. Even though the modified data block is overwritten to the same logical address, FTL writes the updated data block to the different physical address from the previous one, mapping the logical address to the new physical address. This enables flash memory to avoid the high block-erase cost. A flashSSD has an array of NAND flash memory packages so it can access one or more flash memory packages in parallel at once. To take advantage of the internal parallelism of flashSSDs, it is beneficial for DBMSs to request I/O operations on sequential logical addresses. 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 original b-tree is not favorable to SSD. In this paper, we propose AS(Always Sequential) B-tree that writes the updated node contiguously to the previously written node in the logical address for every update operation. In the experiments, AS B-tree enhanced 21% of B-tree`s insertion performance.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. H. Kim, H. C. Roh, D. W. Lee, S. H. Park, "A study on the enhancement of the insertion performance of B-tree on SSD," The KIPS Transactions:PartD, vol. 18, no. 3, pp. 157-168, 2011. DOI: 10.3745/KIPSTD.2011.18.3.157.

[ACM Style]
Sung Ho Kim, Hong Chan Roh, Dae Wook Lee, and Sang Hyun Park. 2011. A study on the enhancement of the insertion performance of B-tree on SSD. The KIPS Transactions:PartD, 18, 3, (2011), 157-168. DOI: 10.3745/KIPSTD.2011.18.3.157.