F-KDB: An K-D-B Tree Implementation over Flash Memory

Flash memory has been widely used in the storage system, mainly due to its superiority such as smaller size, lower power consumption, faster read performance and no mechanical delay. Though the traditional multi-dimensional applications with spatial data management, such as GIS, CAD/CAM, data mining, could directly run over flash memory under the support of FTL (Flash Translation Layer), the performance of this approach is very poor. Because of the inherent limitation of flash memory, such as the erase-before-write, endurance characteristics, the fine-grained updates in the spatial database management system will introduce a significant number of out-place updates over flash memory. As a result, the performance of multi-dimensional applications over flash memory deteriorates rapidly and the reliability is damaged. The traditional multi-dimensional access method of choice in many practical database management systems is the K-D-B tree. In this paper, a new K-D-B tree implementation over flash memory, called F-KDB, is proposed to efficiently handle the large number of fine-grained updates. F-KDB is a log-structured implementation over flash memory storage system. A logging buffer and a node translation table in main memory are proposed to reduce the frequent updates over the flash memory. A series of experiments is conducted to demonstrate the efficiency of F-KDB over flash memory and the system performance is improved significantly.