An LSM-Tree Index for Spatial Data
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 th...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/4/113 |
| _version_ | 1797437241602080768 |
|---|---|
| author | Junjun He Huahui Chen |
| author_facet | Junjun He Huahui Chen |
| author_sort | Junjun He |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T11:17:18Z |
| format | Article |
| id | doaj.art-884584db2beb4c32bc3366073b19e265 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T11:17:18Z |
| publishDate | 2022-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-884584db2beb4c32bc3366073b19e2652023-12-01T00:28:45ZengMDPI AGAlgorithms1999-48932022-03-0115411310.3390/a15040113An LSM-Tree Index for Spatial DataJunjun He0Huahui Chen1Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, ChinaFaculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, ChinaAn 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.https://www.mdpi.com/1999-4893/15/4/113LSM-treespatial dataR-tree indexER-tree indexquery performance |
| spellingShingle | Junjun He Huahui Chen An LSM-Tree Index for Spatial Data Algorithms LSM-tree spatial data R-tree index ER-tree index query performance |
| title | An LSM-Tree Index for Spatial Data |
| title_full | An LSM-Tree Index for Spatial Data |
| title_fullStr | An LSM-Tree Index for Spatial Data |
| title_full_unstemmed | An LSM-Tree Index for Spatial Data |
| title_short | An LSM-Tree Index for Spatial Data |
| title_sort | lsm tree index for spatial data |
| topic | LSM-tree spatial data R-tree index ER-tree index query performance |
| url | https://www.mdpi.com/1999-4893/15/4/113 |
| work_keys_str_mv | AT junjunhe anlsmtreeindexforspatialdata AT huahuichen anlsmtreeindexforspatialdata AT junjunhe lsmtreeindexforspatialdata AT huahuichen lsmtreeindexforspatialdata |