{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T02:57:46Z","timestamp":1783393066544,"version":"3.54.6"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,6,1]],"date-time":"2005-06-01T00:00:00Z","timestamp":1117584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>Flash memory is a type of electrically-erasable programmable read-only memory (EEPROM). Because flash memories are nonvolatile and relatively dense, they are now used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other computer systems in which magnetic disks are inappropriate. Flash, like earlier EEPROM devices, suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erasures, after which it can no longer reliably store data. Due to these limitations, sophisticated data structures and algorithms are required to effectively use flash memories. These algorithms and data structures support efficient not-in-place updates of data, reduce the number of erasures, and level the wear of the blocks in the device. This survey presents these algorithms and data structures, many of which have only been described in patents until now.<\/jats:p>","DOI":"10.1145\/1089733.1089735","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"138-163","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":438,"title":["Algorithms and data structures for flash memories"],"prefix":"10.1145","volume":"37","author":[{"given":"Eran","family":"Gal","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"YAFFS: Yet another flash filing system","author":"Aleph One","year":"2002","unstructured":"Aleph One . 2002 . YAFFS: Yet another flash filing system . Cambridge , UK. Available at http:\/\/www.aleph1.co.uk\/yaffs\/index.html.]] Aleph One. 2002. YAFFS: Yet another flash filing system. Cambridge, UK. Available at http:\/\/www.aleph1.co.uk\/yaffs\/index.html.]]"},{"key":"e_1_2_1_2_1","volume-title":"Filed","author":"Assar M.","unstructured":"Assar , M. , Nemazie , S. , and Estakhri , P . 1995a. Flash memory mass storage architecture. US patent 5,388,083 . Filed March 26, 1993; Issued February 7, 1995; Assigned to Cirrus Logic.]] Assar, M., Nemazie, S., and Estakhri, P. 1995a. Flash memory mass storage architecture. US patent 5,388,083. Filed March 26, 1993; Issued February 7, 1995; Assigned to Cirrus Logic.]]"},{"key":"e_1_2_1_3_1","volume-title":"Filed","author":"Assar M.","unstructured":"Assar , M. , Nemazie , S. , and Estakhri , P . 1995b. Flash memory mass storage architecture incorporation wear leveling technique. US patent 5,479,638 . Filed March 26, 1993; Issued December 26, 1995; Assigned to Cirrus Logic.]] Assar, M., Nemazie, S., and Estakhri, P. 1995b. Flash memory mass storage architecture incorporation wear leveling technique. US patent 5,479,638. Filed March 26, 1993; Issued December 26, 1995; Assigned to Cirrus Logic.]]"},{"key":"e_1_2_1_4_1","unstructured":"Assar M. Nemazie S. and Estakhri P. 1996. Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells. US patent 5 485 595. Filed October 4 1993; Issued January 16 1996; Assigned to Cirrus Logic.]]  Assar M. Nemazie S. and Estakhri P. 1996. Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells. US patent 5 485 595. Filed October 4 1993; Issued January 16 1996; Assigned to Cirrus Logic.]]"},{"key":"e_1_2_1_5_1","unstructured":"Axis Communications. 2004. JFFS home page. Lund Sweden. Available at http:\/\/developer.axis.com\/software\/jffs\/.]]  Axis Communications. 2004. JFFS home page. Lund Sweden. Available at http:\/\/developer.axis.com\/software\/jffs\/.]]"},{"key":"e_1_2_1_6_1","volume-title":"Flash file system. US patent 5,404,485. Filed","author":"Ban A.","year":"1993","unstructured":"Ban , A. 1995. Flash file system. US patent 5,404,485. Filed March 8, 1993 ; Issued April 4, 1995; Assigned to M-Systems .]] Ban, A. 1995. Flash file system. US patent 5,404,485. Filed March 8, 1993; Issued April 4, 1995; Assigned to M-Systems.]]"},{"key":"e_1_2_1_7_1","volume-title":"Filed","author":"Ban A.","year":"1999","unstructured":"Ban , A. 1999 . Flash file system optimized for page-mode flash technologies. US patent 5,937,425 . Filed October 16, 1997; Issued August 10, 1999; Assigned to M-Systems.]] Ban, A. 1999. Flash file system optimized for page-mode flash technologies. US patent 5,937,425. Filed October 16, 1997; Issued August 10, 1999; Assigned to M-Systems.]]"},{"key":"e_1_2_1_8_1","volume-title":"Wear leveling of static areas in flash memory. US patent 6,732,221. Filed","author":"Ban A.","year":"2001","unstructured":"Ban , A. 2004. Wear leveling of static areas in flash memory. US patent 6,732,221. Filed June 1, 2001 ; Issued May 4, 2004; Assigned to M-Systems .]] Ban, A. 2004. Wear leveling of static areas in flash memory. US patent 6,732,221. Filed June 1, 2001; Issued May 4, 2004; Assigned to M-Systems.]]"},{"key":"e_1_2_1_9_1","volume-title":"Filed","author":"Barrett P. L.","unstructured":"Barrett , P. L. , Quinn , S. D. , and Lipe , R. A . 1995. System for updating data stored on a flash-erasable, programmable, read-only memory (FEPROM) based upon predetermined bit value of indicating pointers. US patent 5,392,427 . Filed May 18, 1993; Issued February 21, 1995; Assigned to Microsoft.]] Barrett, P. L., Quinn, S. D., and Lipe, R. A. 1995. System for updating data stored on a flash-erasable, programmable, read-only memory (FEPROM) based upon predetermined bit value of indicating pointers. US patent 5,392,427. Filed May 18, 1993; Issued February 21, 1995; Assigned to Microsoft.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027794.1027801"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0164-1212(99)00059-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199903)29:3%3C267::AID-SPE233%3E3.0.CO;2-T"},{"key":"e_1_2_1_13_1","volume-title":"Operating system including improved file management for use in devices utilizing flash memory as main memory. US patent 5,787,445. Filed","author":"Daberko N.","year":"1996","unstructured":"Daberko , N. 1998. Operating system including improved file management for use in devices utilizing flash memory as main memory. US patent 5,787,445. Filed March 7, 1996 ; Issued July 28, 1998; Assigned to Norris Communications .]] Daberko, N. 1998. Operating system including improved file management for use in devices utilizing flash memory as main memory. US patent 5,787,445. Filed March 7, 1996; Issued July 28, 1998; Assigned to Norris Communications.]]"},{"key":"e_1_2_1_14_1","unstructured":"Dan R. and Williams J. 1997. A TrueFFS and FLite technical overview of M-Systems' flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30 M-Systems.]]  Dan R. and Williams J. 1997. A TrueFFS and FLite technical overview of M-Systems' flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30 M-Systems.]]"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Douglis F.","unstructured":"Douglis , F. , Caceres , R. , Kaashoek , M. F. , Li , K. , Marsh , B. , and Tauber , J. A . 1994. Storage alternatives for mobile computers . In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI) . Monterey, CA. 25--37.]] Douglis, F., Caceres, R., Kaashoek, M. F., Li, K., Marsh, B., and Tauber, J. A. 1994. Storage alternatives for mobile computers. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI). Monterey, CA. 25--37.]]"},{"key":"e_1_2_1_16_1","volume-title":"Flash memory wear leveling system and method. US patent 6,016,275. Filed","author":"Han S.-W.","year":"1998","unstructured":"Han , S.-W. 2000. Flash memory wear leveling system and method. US patent 6,016,275. Filed November 4, 1998 ; Issued January 18, 2000; Assigned to LG Semiconductors .]] Han, S.-W. 2000. Flash memory wear leveling system and method. US patent 6,016,275. Filed November 4, 1998; Issued January 18, 2000; Assigned to LG Semiconductors.]]"},{"key":"e_1_2_1_17_1","volume-title":"Flash file system selection guide. Application Note 686","author":"Intel Corporation","unstructured":"Intel Corporation . 1998a. Flash file system selection guide. Application Note 686 , Intel Corporation .]] Intel Corporation. 1998a. Flash file system selection guide. Application Note 686, Intel Corporation.]]"},{"key":"e_1_2_1_18_1","volume-title":"Understanding the flash translation layer (FTL) specification. Application Note 648","author":"Intel Corporation","unstructured":"Intel Corporation . 1998b. Understanding the flash translation layer (FTL) specification. Application Note 648 , Intel Corporation .]] Intel Corporation. 1998b. Understanding the flash translation layer (FTL) specification. Application Note 648, Intel Corporation.]]"},{"key":"e_1_2_1_19_1","volume-title":"J. H","author":"Jou E.","year":"1996","unstructured":"Jou , E. and Jeppesen III , J. H . 1996 . Flash memory wear leveling system providing immediate direct access to microprocessor. US patent 5,568,423. Filed April 14, 1995; Issued October 22, 1996; Assigned to Unisys .]] Jou, E. and Jeppesen III, J. H. 1996. Flash memory wear leveling system providing immediate direct access to microprocessor. US patent 5,568,423. Filed April 14, 1995; Issued October 22, 1996; Assigned to Unisys.]]"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the USENIX Technical Conference","author":"Kawaguchi A.","unstructured":"Kawaguchi , A. , Nishioka , S. , and Motoda , H . 1995. A flash-memory based file system . In Proceedings of the USENIX Technical Conference . New Orleans, LA. 155--164.]] Kawaguchi, A., Nishioka, S., and Motoda, H. 1995. A flash-memory based file system. In Proceedings of the USENIX Technical Conference. New Orleans, LA. 155--164.]]"},{"key":"e_1_2_1_21_1","first-page":"950","article-title":"An effective flash memory manager for reliable flash memory space management. IEICE","volume":"6","author":"Kim H.-J.","year":"2002","unstructured":"Kim , H.-J. and Lee , S.-G. 2002 . An effective flash memory manager for reliable flash memory space management. IEICE Trans. Inform. Syst. E85-D , 6 , 950 -- 964 .]] Kim, H.-J. and Lee, S.-G. 2002. An effective flash memory manager for reliable flash memory space management. IEICE Trans. Inform. Syst. E85-D, 6, 950--964.]]","journal-title":"Trans. Inform. Syst. E85-D"},{"key":"e_1_2_1_22_1","unstructured":"Krueger W. J. and Rajagopalan S. 1999a. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 5 634 050. Filed June 7 1995; Issued May 27 1999; Assigned to Microsoft.]]  Krueger W. J. and Rajagopalan S. 1999a. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 5 634 050. Filed June 7 1995; Issued May 27 1999; Assigned to Microsoft.]]"},{"key":"e_1_2_1_23_1","unstructured":"Krueger W. J. and Rajagopalan S. 1999b. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 5 898 868. Filed 7 June 1995; Issued April 27 1999; Assigned to Microsoft.]]  Krueger W. J. and Rajagopalan S. 1999b. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 5 898 868. Filed 7 June 1995; Issued April 27 1999; Assigned to Microsoft.]]"},{"key":"e_1_2_1_24_1","unstructured":"Krueger W. J. and Rajagopalan S. 2001. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 6 256 642. Filed 29 January 1992; Issued July 3 2001; Assigned to Microsoft.]]  Krueger W. J. and Rajagopalan S. 2001. Method and system for file system management using a flash-erasable programmable read-only memory. US patent 6 256 642. Filed 29 January 1992; Issued July 3 2001; Assigned to Microsoft.]]"},{"key":"e_1_2_1_25_1","volume-title":"Filed","author":"Lofgren K. M.","unstructured":"Lofgren , K. M. , Norman , R. D. , Thelin , Gregory, B., and Gupta , A . 2003. Wear leveling techniques for flash EEPROM systems. US patent 6,594,183 . Filed June 30, 1998; Issued July, 15, 2003; Assigned to Sandisk and Western Digital.]] Lofgren, K. M., Norman, R. D., Thelin, Gregory, B., and Gupta, A. 2003. Wear leveling techniques for flash EEPROM systems. US patent 6,594,183. Filed June 30, 1998; Issued July, 15, 2003; Assigned to Sandisk and Western Digital.]]"},{"key":"e_1_2_1_26_1","volume-title":"Filed","author":"Lofgren K. M. J.","unstructured":"Lofgren , K. M. J. , Norman , R. D. , Thelin , G. B. , and Gupta , A . 2000. Wear leveling techniques for flash EEPROM systems. US patent 6,081,447 . Filed March 25, 1999; Issued June 27, 2000; Assigned to Western Digital and Sandisk.]] Lofgren, K. M. J., Norman, R. D., Thelin, G. B., and Gupta, A. 2000. Wear leveling techniques for flash EEPROM systems. US patent 6,081,447. Filed March 25, 1999; Issued June 27, 2000; Assigned to Western Digital and Sandisk.]]"},{"key":"e_1_2_1_27_1","volume-title":"Filed","author":"Marshall J. M.","unstructured":"Marshall , J. M. and Manning , C. D. H. 1998. Flash file management system. US patent 5,832,493 . Filed April 24, 1997; Issued November 3, 1998; Assigned to Trimble Navigation.]] Marshall, J. M. and Manning, C. D. H. 1998. Flash file management system. US patent 5,832,493. Filed April 24, 1997; Issued November 3, 1998; Assigned to Trimble Navigation.]]"},{"key":"e_1_2_1_28_1","volume-title":"Filed","author":"Parker K. W.","year":"2003","unstructured":"Parker , K. W. 2003 . Portable electronic device having a log-structured file system in flash memory. US patent 6,535,949 . Filed April 19, 1999; Issued March 18, 2003; Assigned to Research In Motion.]] Parker, K. W. 2003. Portable electronic device having a log-structured file system in flash memory. US patent 6,535,949. Filed April 19, 1999; Issued March 18, 2003; Assigned to Research In Motion.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/146941.146943"},{"key":"e_1_2_1_30_1","volume-title":"USENIX Winter Conference Proceedings","author":"Seltzer M. I.","unstructured":"Seltzer , M. I. , Bostic , K. , McKusick , M. K. , and Staelin , C . 1993. An implementation of a log-structured file system for UNIX . In USENIX Winter Conference Proceedings . San Diego, CA. 307--326.]] Seltzer, M. I., Bostic, K., McKusick, M. K., and Staelin, C. 1993. An implementation of a log-structured file system for UNIX. In USENIX Winter Conference Proceedings. San Diego, CA. 307--326.]]"},{"key":"e_1_2_1_31_1","volume-title":"Filed","author":"Smith K. B.","unstructured":"Smith , K. B. and Garvin , P. K . 1999. Method and apparatus for allocating storage in flash memory. US patent 5,860,082 . Filed March 28, 1996; Issued January 12, 1999; Assigned to Datalight.]] Smith, K. B. and Garvin, P. K. 1999. Method and apparatus for allocating storage in flash memory. US patent 5,860,082. Filed March 28, 1996; Issued January 12, 1999; Assigned to Datalight.]]"},{"key":"e_1_2_1_32_1","first-page":"62","article-title":"The Microsoft flash file system","volume":"20","author":"Torelli P.","year":"1995","unstructured":"Torelli , P. 1995 . The Microsoft flash file system . Dr. Dobb's Journal 20 , 62 -- 72 .]] Torelli, P. 1995. The Microsoft flash file system. Dr. Dobb's Journal 20, 62--72.]]","journal-title":"Dr. Dobb's Journal"},{"key":"e_1_2_1_33_1","volume-title":"Filed","author":"Wells S.","unstructured":"Wells , S. , Hasbun , R. N. , and Robinson , K . 1998. Sector-based storage device emulator having variable-sized sector. US patent 5,822,781 . Filed October 30, 1992; Issued October 13, 1998; Assigned to Intel.]] Wells, S., Hasbun, R. N., and Robinson, K. 1998. Sector-based storage device emulator having variable-sized sector. US patent 5,822,781. Filed October 30, 1992; Issued October 13, 1998; Assigned to Intel.]]"},{"key":"e_1_2_1_34_1","volume-title":"Method for wear leveling in a flash EEPROM memory. US patent 5,341,339. Filed","author":"Wells S. E.","year":"1993","unstructured":"Wells , S. E. 1994. Method for wear leveling in a flash EEPROM memory. US patent 5,341,339. Filed November 1, 1993 ; Issued August 23, 1994; Assigned to Intel .]] Wells, S. E. 1994. Method for wear leveling in a flash EEPROM memory. US patent 5,341,339. Filed November 1, 1993; Issued August 23, 1994; Assigned to Intel.]]"},{"key":"e_1_2_1_35_1","volume-title":"Ottawa Linux Symposium (July).","author":"Woodhouse D.","year":"2001","unstructured":"Woodhouse , D. 2001 . JFFS: The journaling flash file system . Ottawa Linux Symposium (July). Available at http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf.]] Woodhouse, D. 2001. JFFS: The journaling flash file system. Ottawa Linux Symposium (July). Available at http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf.]]"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA)","volume":"2968","author":"Wu C.-H.","unstructured":"Wu , C.-H. , Chang , L.-P. , and Kuo , T . -W. 2003a. An efficient B-tree layer for flash-memory storage systems . In Proceedings of the 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA) . Tainan City,Taiwan. Lecture Notes in Computer Science , vol. 2968 . Springer, 409-- 430.]] Wu, C.-H., Chang, L.-P., and Kuo, T.-W. 2003a. An efficient B-tree layer for flash-memory storage systems. In Proceedings of the 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA). Tainan City,Taiwan. Lecture Notes in Computer Science, vol. 2968. Springer, 409-- 430.]]"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems","author":"Wu C.-H.","unstructured":"Wu , C.-H. , Chang , L.-P. , and Kuo , T . -W. 2003b. An efficient R-tree implementation over flash-memory storage systems . In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems . New Orleans, LA. 17--24.]] 10.1145\/956676.956679 Wu, C.-H., Chang, L.-P., and Kuo, T.-W. 2003b. An efficient R-tree implementation over flash-memory storage systems. In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems. New Orleans, LA. 17--24.]] 10.1145\/956676.956679"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Wu M.","year":"1954","unstructured":"Wu , M. and Zwaenepoel , W . 1994. eNVy: A non-volatile, main memory storage system . In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems . San Jose, CA. 86--97.]] 10.1145\/ 1954 73.195506 Wu, M. and Zwaenepoel, W. 1994. eNVy: A non-volatile, main memory storage system. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. San Jose, CA. 86--97.]] 10.1145\/195473.195506"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089733.1089735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089733.1089735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:29Z","timestamp":1750262909000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089733.1089735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1089733.1089735"],"URL":"https:\/\/doi.org\/10.1145\/1089733.1089735","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}