{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:00Z","timestamp":1773481860549,"version":"3.50.1"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>An LSM-tree (log-structured merge-tree) is a hierarchical, orderly and disk-oriented data storage structure which makes full use of the characteristics of disk sequential writing, which are much better than those of random writing. However, an LSM-tree can only be queried by a key and cannot meet the needs of a spatial query. To improve the query efficiency of spatial data stored in LSM-trees, the traditional method is to introduce stand-alone tree-like secondary indexes, the problem with which is the read amplification brought about by dual index queries. Moreover, when more spatial data are stored, the index tree becomes increasingly large, bringing the problems of a lower query efficiency and a higher index update cost. To address the above problems, this paper proposes an ER-tree(embedded R-tree) index structure based on the orderliness of LSM-tree data. By building an SER-tree(embedded R-tree on an SSTable) index structure for each storage component, we optimised dual index queries into single and organised SER-tree indexes into an ER-tree index with a binary linked list. The experiments showed that the query performance of the ER-tree index was effectively improved compared to that of stand-alone R-tree indexes.<\/jats:p>","DOI":"10.3390\/a15040113","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T15:31:21Z","timestamp":1648222281000},"page":"113","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An LSM-Tree Index for Spatial Data"],"prefix":"10.3390","volume":"15","author":[{"given":"Junjun","family":"He","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China"}]},{"given":"Huahui","family":"Chen","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s002360050048","article-title":"The log-structured merge-tree (LSM-tree)","volume":"33","author":"Cheng","year":"1996","journal-title":"Acta Inform."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1365815.1365816","article-title":"Bigtable: A distributed storage system for structured data","volume":"26","author":"Chang","year":"2008","journal-title":"ACM Trans. Comput. Syst. TOCS"},{"key":"ref_3","unstructured":"Ghemawat, S., and Dean, J. (2022, February 15). LevelDB. Available online: http:\/\/code.google.com\/p\/leveldb."},{"key":"ref_4","unstructured":"(2022, February 15). Apache. Apache HBase: The Hadoop Database, a Distributed, Scalable, Big Data Store. Available online: https:\/\/hbase.apache.org\/."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.14778\/2733085.2733096","article-title":"AsterixDB: A scalable, open-source BDMS","volume":"7","author":"Alsubaiee","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"ref_6","unstructured":"Team Facebook RocksDB (2022, February 15). A Persistent Key-Value Store for Fast Storage Environments. Available online: https:\/\/rocksdb.org."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/1773912.1773922","article-title":"Cassandra: A decentralised structured storage system","volume":"44","author":"Lakshman","year":"2010","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"ref_8","unstructured":"Lawder, J.K. (2000). The Application of Space-Filling Curves to the Storage and Retrieval of Multi-Dimensional Data. [Ph.D. Dissertation, University of London]."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Mao, Q., Qader, M.A., and Hristidis, V. (2020, January 10\u201313). Comprehensive comparison of LSM architectures for spatial data. Proceedings of the 2020 IEEE International Conference on Big Data (Big Data), Atlanta, GA, USA.","DOI":"10.1109\/BigData50022.2020.9377919"},{"key":"ref_10","first-page":"159","article-title":"Implementation of LevelDB-based secondary index on two-dimensional data. Journal of East China Normal University","volume":"5","author":"Xu","year":"2019","journal-title":"Nat. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Xu, R., Liu, Z., Hu, H., Qian, W., and Zhou, A. (2020, January 24\u201327). An efficient secondary index for spatial data based on LevelDB. Proceedings of the International Conference on Database Systems for Advanced Applications, DASFAA 2020, Jeju, Korea.","DOI":"10.1007\/978-3-030-59419-0_50"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"841","DOI":"10.14778\/2732951.2732958","article-title":"Storage management in AsterixDB","volume":"7","author":"Alsubaiee","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"ref_13","unstructured":"Bozhi, Q. (2020). Research on Linked Spatial Index Based on LSM-Tree. [Master\u2019s Thesis, Zhejiang University]."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wu, S., and Mao, R. (2020, January 13\u201316). Towards read-intensive key-value stores with tidal structure based on LSM-tree. Proceedings of the 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), Beijing, China.","DOI":"10.1109\/ASP-DAC47756.2020.9045617"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1952","DOI":"10.1002\/spe.2875","article-title":"Improving LSM-trie performance by parallel search","volume":"50","author":"Cheng","year":"2020","journal-title":"Softw. Pract. Exp."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"531","DOI":"10.14778\/3303753.3303759","article-title":"Efficient data ingestion and query processing for LSM-based storage systems","volume":"12","author":"Luo","year":"2019","journal-title":"Proc. VLDB Endow."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s00778-019-00555-y","article-title":"LSM-based storage techniques: A survey","volume":"29","author":"Luo","year":"2020","journal-title":"VLDB J."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sears, R., and Ramakrishnan, R. (2012, January 20\u201324). BLSM: A general purpose log-structured merge tree. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201812), New York, NY, USA.","DOI":"10.1145\/2213836.2213862"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201984), Boston, MA, USA.","DOI":"10.1145\/602264.602266"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kim, Y., Kim, T., Carey, M.J., and Li, C. (2017, January 19\u201322). A Comparative Study of Log-Structured Merge-Tree-Based Spatial Indexes for Big Data. Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, USA.","DOI":"10.1109\/ICDE.2017.61"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00778-008-0120-3","article-title":"The RUM-tree: Supporting frequent updates in R-trees using memos","volume":"18","author":"Silva","year":"2009","journal-title":"VLDB J."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Shin, J., Wang, J., and Aref, W.G. (2021, January 19\u201322). The LSM RUM Tree: A Log-Structured Merge R-Tree for Update-intensive Spatial Workloads. Proceedings of the 2021 IEEE 37th International Conference on Data Engineering (ICDE), Chania, Greece.","DOI":"10.1109\/ICDE51399.2021.00238"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Li, F., Lu, Y., Yang, Z., and Shu, J. (December, January 29). SineKV: Decoupled Secondary Indexing for LSM-based Key-Value Stores. Proceedings of the 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), Singapore.","DOI":"10.1109\/ICDCS47774.2020.00071"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3033273","article-title":"WiscKey: Separating Keys from Values in SSD-Conscious Storage","volume":"13","author":"Lu","year":"2017","journal-title":"ACM Trans. Storage"},{"key":"ref_25","unstructured":"(2022, February 15). OpenStreetMap Contributors. OpenStreetMap Data. Available online: https:\/\/www.openstreetmap.org."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/113\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:43:30Z","timestamp":1760136210000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,25]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["a15040113"],"URL":"https:\/\/doi.org\/10.3390\/a15040113","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,25]]}}}