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


Vol. 15,  No. 6, pp. 325-334, Dec.  2008
10.3745/KIPSTA.2008.15.6.325


PDF
  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


  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.