# An LSM-Tree Index for Spatial Data
## 4 ER-Tree Index
### ER-Tree Index Query
#### 4.4.3 Circle Range Query
The experimental results are shown in \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]6 The ER-tree index has better range query performance regardless of the range of the real dataset, indicating that the index design in this paper is suitable for both short- and large-range queries. **Real dataset circle query:** Using the centre point of the real dataset to gradually expand the circle range outward, this paper conducted five circle query operations on the Chinese and New York datasets, respectively, and the last query covered all the data points of the real dataset. The experimental results are shown in \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]7 Similar to the range queries, the ER-tree indexes have better query performance for both short and large circular ranges. It is worth noting that circular range queries can be used for KNN queries that are common in spatial queries. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]8 Comparison of the index range query performance on the real dataset. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]9 Comparison of the index point query performance on the real dataset. #### 5.2.3 ER-Tree Index Space Performance

For databases with different data volumes after building the index, this paper compared the size of the ER-tree index database file with that of a stand-alone R-tree index database file to study the space performance of the two indexes. It can be found from the experimental results in Figure 18 that the space performance of the ER-tree index is slightly better than that of the stand-alone R-tree index. This is because the building of the ER-tree index is bottom-up, which is compacted in the storage of tree nodes and there is almost no space to waste. The stand-alone R-tree index is built from the root node to the bottom, inevitably wasting space on the node. Therefore, compared to the two indexes, the space performance of the ER-tree index is slightly better than that of the stand-alone R-tree index. ## 6 Conclusions

To address the problems of a low query efficiency and the dual queries of stand-alone R-tree index for spatial data on an LSM-tree, this paper designed a new ER-tree index structure based on the orderliness of an LSM-tree and optimised the dual queries into single query to improve the query efficiency of spatial data. The experiments proved that the ER-tree index was improved in the index building and the index query performance compared to the stand-alone R-tree index, and there was almost no degradation in the space performance. \[y_{1}=y-r;\ y_{2}=y+r; \tag{7}\]0 Comparison of the index circle query performance on the real dataset. \[y_{1}=y-r;\ y_{2}=y+r; \tag{7}\]1 Comparison of index space. **Author Contributions:** Data curation, [PERSON]; formal analysis, J.H. ; investigation, J.H. ; resources, H.C.; software, J.H. ; writing--original draft preparation, J.H. ; writing--review and editing, J.H. and H.C.; visualisation, J.H. All authors have read and agreed to the published version of the manuscript. **Funding:** This research received no external funding. **Institutional Review Board Statement:** Not applicable. **Informed Consent Statement:** Not applicable. **Data Availability Statement:** Not applicable. **Conflicts of Interest:** The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON]; [PERSON] The log-structured merge-tree (LSM-tree). _Acta Inform._**1996**, 33, 351-385. [CrossRef]
* (2) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Bigtable: A distributed storage system for structured data. _ACM Trans. Comput. Syst. TOCS_**2008**, _26_, 1-26. [CrossRef]
* (3) [PERSON]; [PERSON] LevelDB. Available online: [[http://code.google.com/p/leveldb](http://code.google.com/p/leveldb)]([http://code.google.com/p/leveldb](http://code.google.com/p/leveldb)) (accessed on 15 February 2022). * (4) Apache. Apache. ABase: The Hadoop Database, a Distributed, Scalable, Big Data Store. Available online: [[https://hbase.apache](https://hbase.apache)]([https://hbase.apache](https://hbase.apache)). org/ (accessed on 15 February 2022).