# An LSM-Tree Index for Spatial Data
## 4 ER-Tree Index
### ER-Tree Index Query
#### 4.4.3 Circle Range Query
The experiments were divided into three groups with 1 million, 10 million and 100 million data items and the insertion latency is defined below:

\[\text{Latency}=\frac{\text{Insert time}}{\text{Insert data number}} \tag{8}\]

Figure 10: Experimental data display. The experimental results in Figure 11 show that the insertion process of the ER-tree index has lower insertion latency than the other two. This is because the data of the stand-alone R-tree index and the hierarchical R-tree index are time-consuming to insert due to the huge index tree, resulting in lower build performance than ER-tree indexes. ER-tree indexes reduce the size of the index tree by building on the SSTable, thus decreasing the index building time. #### 5.2.2 ER-Tree Index Query Performance

**Simulated dataset point query:** For each database with different amounts of data after building the index, this paper performed 1000 random point queries and calculated the average query time to compare the query performance of the index. The experimental results are shown in Figure 12. Note that the vertical coordinate is the logarithmic axis. The results show that the ER-tree index has better point query performance than the other two. This is because ER-tree indexes are queried only once, while the other two indexes are queried twice. **Simulated dataset range query:** For each database with different amounts of data after building the index, this paper performed 1000 random range queries with various range lengths and calculated the average query time to compare the query performance of the index. The experimental results are shown in Figure 13. The vertical coordinate is the logarithmic axis. The results show that the ER-tree index has better range query performance than the other two, for the same reason as the point query. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]0 Comparison of the index insertion latency on the simulated datasets. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]1 Comparison of the index point query performance on the simulated datasets. **Simulated dataset circle query:** For each database with different amounts of data after building the index, this paper performed 1000 random circle queries with various query radii and calculated the average query time to compare the query performance of the index. The experimental results are shown in \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]2 The vertical coordinate is the logarithmic axis. The result shows that the ER-tree index has better circle query performance than the other two, for the same reason as the point query. **Real dataset point query:** In this paper, we randomly selected a query point on the real dataset for querying and repeated the above operation 1000 times to calculate the average query time. The experimental results are shown in \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]3 The ER-tree index shows better point query performance on both real datasets, indicating that the index design in this paper is effective. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]4 Comparison of the index circle query performance on the simulated dataset. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]5 Comparison of the index range query performance on the simulated dataset. **Real dataset range query:** Using the centre point of the real dataset to gradually expand the query range outward, this paper conducted five range query operations on the Chinese and New York datasets, respectively and the last query covered all the data points of the real dataset. For example, the approximate centre point of New York is 75\({}^{\circ}\) W, 42.5\({}^{\circ}\) N, so the first range is from 74\({}^{\circ}\) W, 42\({}^{\circ}\) N to 76\({}^{\circ}\) W, 43\({}^{\circ}\) N and the last range is from 70\({}^{\circ}\) W, 40\({}^{\circ}\) N to 80\({}^{\circ}\) W, 45\({}^{\circ}\) N, which is roughly the entire range of New York.