Im, JunsuKim, JeonggyunOh, SeonggyunKoo, JinhyungPark, JuhyungChwa, Hoon SungNoh, Sam H.Lee, Sungjin2025-04-042025-04-042025-03-30https://hdl.handle.net/10919/125142Thanks to the advance of device scaling technologies, the capacity of SSDs is rapidly increasing. Such increase, however, comes at the cost of a huge index table requiring large DRAM. To provide reasonable performance with less DRAM, various index structures exploiting locality and regularity of I/O references have been proposed. However, they provide deteriorated performance depending on I/O patterns and storage fragmentation. This paper proposes a novel approximate index structure, called AppL, which combines memoryefficient approximate indices and an LSM-tree that has an append-only and sorted nature. AppL reduces the index size to 6∼8-bits per entry, which is considerably smaller than the typical index structures requiring 32∼64-bits, and maintains such high memory efficiency irrespective of locality and fragmentation. By alleviating memory pressure, AppL achieves 33.6∼72.4% shorter read latency and 28.4%∼83.4% higher I/O throughput than state-of-the-art techniques.application/pdfenIn CopyrightArticle - Refereed2025-04-01The author(s)https://doi.org/10.1145/3689031.3717478