μ-tree

Abstract

As NAND flash memory becomes increasingly popular as data storage for embedded systems, many file systems and database management systems are being built on it. They require an efficient index structure to locate a particular item quickly from a huge amount of directory entries or database records. This paper proposes μ-Tree, a new ordered index structure tailored to the characteristics of NAND flash memory. μ-Tree is a balanced tree similar to B+-Tree. In μ-Tree, however, all the nodes along the path from the root to the leaf are put together into a single flash memory page in order to minimize the number of flash write operations when a leaf node is updated. Our experimental evaluation shows that μ-Tree outperforms B+-Tree by up to 28% for traces extracted from real workloads. With a small in-memory cache of 8 Kbytes, μ-Tree improves the overall performance by up to 90% compared to B+-Tree with the same cache size.