近年來隨著嵌入式系統的應用越來越廣泛，高容量快閃記憶體的需求也隨之上升。許多儲存媒介因為製造成本低廉、體積小及省電等優點[1]，逐漸使用快閃記憶體取代原本的硬碟，使得快閃記憶體的索引架構(index structure)成為當前一項重要的研究議題。然而快閃記憶體所擁有之硬體特性，如寫入前刪除(erase-before-write)、區塊存取(Block Access)、平均磨損(wear-leveling)等[2]，皆令當前運作於快閃記憶體上之嵌入式系統的索引結構，出現許多需要解決的問題。
本論文將介紹現行使用於快閃記憶體儲存系統上之索引架構[3]如： BFTL[4]、IBSF[5]、RBFTL[6]、IPL Approach[7]，以及μ-tree[8]。本論文將針對資料存取的效能[9][10]、不同資料量多寡對於系統的負擔，以及系統出現錯誤當機時的可靠度[11][12][13][14]等方面進行探討比較，透過詳盡的比較分析也可為未來的系統設計提供他們的想法與分析各種因素，而當面臨多個程序需同時存取同一索引結構時，所產生的一些有關鎖定協定 (locking protocol)[15][16]和暫存區的並行控制(concurrency buffer control)[17]等具有挑戰性的問題，也將會在本篇論文中被討論。

With the applications of embedded systems in recent years, more and more demand for reliable and huge-capacity flash-memory storage systems is rising. Many flash-memory storage systems have gradually replaced hard-disk drives in many applications because of its advantages such as low cost, small size and low-power consumption[1] [2]. Therefore, index structures on flash-memory have become an important research topic[3]. However, flash-memory has distinct characteristics such as out-place update, erase-before-write, garbage collection, and wear-leveling such that current implementation of index structures on flash-memory requires a delicate design.
In the thesis, we will introduce some famous index structures on flash-memory storage systems such as BFTL[4], IBSF[5], RBFTL[6], IPL Approach[7], as well as the μ-tree[8]. This thesis will compare these index structures in terms of their performance on data access[9][10], system workload on different amount of data written [11][12][13][14] and crash recovery from a failure. The detailed comparison can provide their design insight and analyze the various factors for future design. Some challenging issues about a locking protocol[15][16] and concurrency buffer control[13][17] will be discussed when two or more processes will access a same index structure.

[1] Bez, R., Camerlenghi, E., Modelli, A. and Visconti, A. Introduction to flash memory. Proceedings of the IEEE, 91, (4 2003), 489-502.
[2] Kawaguchi, A., Nishioka, S. and Motoda, H. A flash-memory based file system. In Proceedings of the Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings (New Orleans, Louisiana, 1995). USENIX Association.
[3] Wu, M. and Zwaenepoel, W. eNVy: a non-volatile, main memory storage system. In Proceedings of the Proceedings of the sixth international conference on Architectural support for programming languages and operating systems (San Jose, California, United States, 1994). ACM.
[4] Wu, C.-H., Kuo, T.-W. and Chang, L. P. An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans. Embed. Comput. Syst., 6, (3 2007), 19.
[5] Lee, H.-S., Park, S., Song, H.-J. and Lee, D.-H. An Efficient Buffer Management Scheme for Implementing a B-Tree on NAND Flash Memory. In Proceedings of the Proceedings of the 3rd international conference on Embedded Software and Systems (Daegu, Korea, 2007). Springer-Verlag.
[6] Xiang, X., Yue, L., Liu, Z. and Wei, P. A reliable B-tree implementation over flash memory. In Proceedings of the Proceedings of the 2008 ACM symposium on Applied computing (Fortaleza, Ceara, Brazil, 2008). ACM.
[7] Lee, S.-W. and Moon, B. Design of flash-based DBMS: an in-page logging approach. In Proceedings of the Proceedings of the 2007 ACM SIGMOD international conference on Management of data (Beijing, China, 2007). ACM.
[8] Kang, D., Jung, D., Kang, J.-U. and Kim, J.-S. Mu-tree: an ordered index structure for NAND flash memory. In Proceedings of the Proceedings of the 7th ACM \& IEEE international conference on Embedded software (Salzburg, Austria, 2007). ACM.
[9] Park, C., Seo, J., Seo, D., Kim, S. and Kim, B. Cost-Efficient Memory Architecture Design of NAND Flash Memory Embedded Systems. In Proceedings of the Proceedings of the 21st International Conference on Computer Design (2003). IEEE Computer Society.
[10] Yin, S., Pucheral, P. and Meng, X. A sequential indexing scheme for flash-based embedded systems. In Proceedings of the Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (Saint Petersburg, Russia, 2009). ACM.
[11] Jaluta, I., Sippu, S. and Soisalon-Soininen, E. Concurrency control and recovery for balanced B-link trees. The VLDB Journal, 14, 2 (2005), 257-277.
[12] Wu, C.-H., Kuo, T.-W. and Chang, L.-P. The Design of efficient initialization and crash recovery for log-based file systems over flash memory. Trans. Storage, 2, (4 2006), 449-467.
[13] Wu, C.-H., Kuo, T.-W. and Chang, L.-P. Efficient initialization and crash recovery for log-based file systems over flash memory. In Proceedings of the Proceedings of the 2006 ACM symposium on Applied computing (Dijon, France, 2006). ACM.
[14] Wu, C.-H. and Kuo, T.-W. An adaptive two-level management for the flash translation layer in embedded systems. In Proceedings of the Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design (San Jose, California, 2006). ACM.
[15] S. Byun, M. H. a. H. H. Flash memory lock management for portable information systems. International Journal of Cooperative Information Systems, vol.15, no.3 (15 2006), 79.
[16] Bayer, R. and Schkolnick, M. Concurrency of operations on B-trees. Morgan Kaufmann Publishers Inc., City, (1988).