A New Flash-based B+-Tree with Very Cheap Update Operations on Leaf Nodes
2016
Recently, as the price per bit is decreasing at a fast rate, flash memory has been considered to be an alternative storage of large-scale data-centric systems.Although flash shows off its high speeds of page reads, it also have performance concerns about pool performance of random writes.Therefore, it is crucial to get a way to efficiently update a B+-tree in flash storage.In this light, we propose a new flash B+-tree that stores updated versions of leaf nodes in sibling-leaf blocks (SLBs) so that garbage collection is efficiently performed in the unit of SLB.Since the versions of leaf nodes can be directly accessed from their virtual parent nodes, the search speeds does not deteriorate, differently from other earlier B+-trees.To verify the performance advantages, we use a cost model fitted to usual operations performed in the B+-tree.