# An LSM-Tree Index for Spatial Data
## 4 ER-Tree Index
### ER-Tree Index Query
#### 4.4.3 Circle Range Query  
The circle range query of the spatial data is given a circle centre point CP(x, y) and radius r and queries the data within the circle with the CP point as the centre and r as the radius. According to the formula to derive the latitude and longitude of the four vertices, the smallest outlying rectangle of the circle can be found, which is then converted into a rectangular range query, as shown in Figure 9. The calculation formula is shown below. \[x_{1}=x-r;\ x_{2}=x+r; \tag{6}\]  
\[y_{1}=y-r;\ y_{2}=y+r; \tag{7}\]```
1:QR: query spatial range, ERT: LSM ER-Tree index. 2:result_c - key, value-collection, whose value in QR1. Level_ptr \(\leftarrow\) ERT. head;
3:level_ptr \(\leftarrow\) ERT. head;
4:while(level_ptr! = null) do
5: ptr \(\leftarrow\) level_ptr. head;
6:while(ptr! = null) do
7: if intersect (ptr. tMBR, QR) then // intersect: judge whether the range QR is within or intersects the MBR
8: LeafNode \(\leftarrow\) QRFindLeaf (ptr.SERT,QR); //SERT: SER-Tree index on SSTable
9: temp. append(LeafNode_db_ptr); end if
10: ptr \(\leftarrow\) ptr. next;
11: end while
12:end while
13:foreach(<key, value>in temp)
14:if(include(QR, value)) then //include:judge whether the point value is within the QR range
15: result_c. append(<key, value); end if;
16:end for
17: return result_c;
18:function QRFindLeaf (T, QR)
19: begin
20: if T is a LeafNode, then
21: if (intersect(T.mbr, QR)) then
22: return T; else return \(\emptyset\);
23:else
24: for each child u of T, do
25: if(intersect(u.mbr, QR)) then
26: QRFindLeaf (u, QR); end if;
27: end for
28:end function
```

**Algorithm 3** Rectangular range query algorithm

Algorithm 4 describes the process of the circular range query for the ER-tree index. In the first step, Algorithm 4 needs to computationally transform the circular range query into a rectangular range query (line 1). In the second step, the range_query algorithm is executed and the returned results <key, value> are stored in the result_c collection (lines 2-3). In the third step, for the results in the result_c collection, the distance from each data point to the query circle centre is the computed distance and the results whose distance is greater than the query distance r are removed (lines 4-8). Figure 9: Circle query to the rectangular range query. ## 5 Evaluation

### Experimental Environment and Data

RocksDB is an LSM-tree architecture engine developed by Facebook. In this paper, we implemented the ER-tree index on RocksDB and compared the ER-Tree with the hierarchical R-tree index and the stand-alone R-tree index implemented in RocksDB. All of the experiments were conducted on the following experimental machine: Intel(R) Core(TM) i7-9700k CPU, 32 GB memory, 2.5 TB SATA, Ubuntu 18.04.4 LTS as the operating system and RocksDB version number 5.6.1. Simulated dataset: We used randomly generated double-type coordinate values in the range of 0-1,000,000 and the key was obtained by encoding the coordinate value to generate 1 million, 10 million and 100 million test data randomly. Real dataset 1: We used the Chinese national building data downloaded through OpenStreetMap [25], with the total number of elements being 2,089,000, as shown in Figure 10. It can be found that the spatial data distribution of the research object is not uniform and there is a certain degree of randomness in the sparsity of the data, meaning it can be used as an experimental sample. Real dataset 2: We used the New York building data downloaded through OpenStreetMap, with the total number of elements being 3,780,837. Its data distribution is different from real dataset 1, meaning it can be used as an experimental sample. ### Experimental Results

#### 5.2.1 ER-Tree Index Building Performance

In this paper, the same randomly generated spatial data were inserted into the ER-tree index database, hierarchical R-tree index database and the stand-alone R-tree index database and the insertion data time was measured.