{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:31Z","timestamp":1763466511842},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Flash memories are in ubiquitous use for storage on sensor nodes, mobile devices, and enterprise servers. However, they present significant challenges in designing tree indexes due to their fundamentally different read and write characteristics in comparison to magnetic disks.<\/jats:p>\n          <jats:p>\n            In this paper, we present the Lazy-Adaptive Tree (LA-Tree), a novel index structure that is designed to improve performance by minimizing accesses to flash. The LA-tree has three key features: 1) it amortizes the cost of node reads and writes by performing update operations in a lazy manner using cascaded buffers, 2) it dynamically adapts buffer sizes to workload using an online algorithm, which we prove to be optimal under the cost model for raw NAND flashes, and 3) it optimizes index parameters, memory management, and storage reclamation to address flash constraints. Our performance results on raw NAND flashes show that the LA-Tree achieves 2x to 12x gains over the\n            <jats:italic>best<\/jats:italic>\n            of alternate schemes across a range of workloads and memory constraints. Initial results on SSDs are also promising, with 3x to 6x gains in most cases.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687669","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"361-372","source":"Crossref","is-referenced-by-count":98,"title":["Lazy-Adaptive Tree"],"prefix":"10.14778","volume":"2","author":[{"given":"Devesh","family":"Agrawal","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deepak","family":"Ganesan","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Sitaraman","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanlei","family":"Diao","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shashi","family":"Singh","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","first-page":"1","article-title":"The buffer tree","volume":"37","author":"Arge L.","year":"2003","journal-title":"A Technique for Designing Batched External Data Structures. In Algorithmica"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0107-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243418.1243429"},{"key":"e_1_2_1_4_1","volume-title":"Design Tradeoffs for SSD Performance. In USENIX","author":"Agrawal N.","year":"2008"},{"key":"e_1_2_1_5_1","volume-title":"CIDR","author":"Diao Y.","year":"2007"},{"key":"e_1_2_1_6_1","unstructured":"MSP-SATA7525. http:\/\/mtron.net\/Upload_Data\/Spec\/ASIC\/PRO\/SATA\/MSP-SATA7525_rev0.4.pdf  MSP-SATA7525. http:\/\/mtron.net\/Upload_Data\/Spec\/ASIC\/PRO\/SATA\/MSP-SATA7525_rev0.4.pdf"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1413254.1413261"},{"key":"e_1_2_1_8_1","unstructured":"Enea polyhedra flashlite. http:\/\/www.enea.com.  Enea polyhedra flashlite. http:\/\/www.enea.com."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127833"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363189.1363198"},{"key":"e_1_2_1_11_1","volume-title":"Generalized Search Trees for Database Systems. In VLDB","author":"Hellerstein J. M.","year":"1995"},{"key":"e_1_2_1_12_1","first-page":"17","article-title":"A new data structure for representing sorted lists","author":"Huddleston S.","year":"1982","journal-title":"Acta Informatica"},{"key":"e_1_2_1_13_1","unstructured":"H-Store: A Next Generation OLTP DBMS. http:\/\/db.cs.yale.edu\/hstore\/.  H-Store: A Next Generation OLTP DBMS. http:\/\/db.cs.yale.edu\/hstore\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176911"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289927.1289953"},{"key":"e_1_2_1_16_1","unstructured":"A. Borodin and E. Y. Ran. Online computation and competitive analysis. Published by Cambridge University Press 1998   A. Borodin and E. Y. Ran. Online computation and competitive analysis. Published by Cambridge University Press 1998"},{"key":"e_1_2_1_17_1","volume-title":"Flashing Up the Storage Layer. In VLDB","author":"Koltsidas I.","year":"2008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247488"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376723"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.226"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236412"},{"key":"e_1_2_1_22_1","unstructured":"Toshiba TC58DVG02A1FT00 NAND flash chip datasheet. http:\/\/toshiba.com\/taec 2003.  Toshiba TC58DVG02A1FT00 NAND flash chip datasheet. http:\/\/toshiba.com\/taec 2003."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275986.1275991"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315487"},{"key":"e_1_2_1_25_1","volume-title":"Flash-Optimized Index Structures for Embedded Systems. TR 2008-08","author":"Agrawal D.","year":"2008"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:32Z","timestamp":1672226852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687669"}},"subtitle":["an optimized index structure for flash devices"],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687669"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687669","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}