Effect of Node Size on the Performance of the B(+)-tree on Flash Memory


The KIPS Transactions:PartA, Vol. 15, No. 6, pp. 325-334, Dec. 2008
10.3745/KIPSTA.2008.15.6.325,   PDF Download:

Abstract

Flash memory is widely used as a storage medium for mobile devices such as cell phones, MP3 players, PDA’s due to its tiny size, low power consumption and shock resistant characteristics. Additionally, some computer manufacturers try to replace hard-disk drives used in Laptops or personal computers with flash memory. More recently, there are some literatures on developing a flash memory-aware B -tree index for an efficient key-based search in the flash memory storage system. They focus on minimizing the number of “overwrites” resulting from inserting or deleting a sequence of key values to/from the B -tree. However, in addition to this factor, the size of a physical page allocated to a node can affect the maintenance cost of the B -tree. In this paper, with diverse experiments, we compare and analyze the costs of construction and search of the B -tree and the space requirement on flash memory as the node size increases. We also provide sorting-based or non-sorting-based algorithms to be used when inserting a key value into the node and suggest an header structure of the index node for searching a given key inside it efficiently.


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]
D. J. Park and H. G. Choi, "Effect of Node Size on the Performance of the B(+)-tree on Flash Memory," The KIPS Transactions:PartA, vol. 15, no. 6, pp. 325-334, 2008. DOI: 10.3745/KIPSTA.2008.15.6.325.

[ACM Style]
Dong Joo Park and Hae Gi Choi. 2008. Effect of Node Size on the Performance of the B(+)-tree on Flash Memory. The KIPS Transactions:PartA, 15, 6, (2008), 325-334. DOI: 10.3745/KIPSTA.2008.15.6.325.