# An LSM-Tree Index for Spatial Data
## 4 ER-Tree Index
### ER-Tree Index Improve  
The above describes the general structure of an ER-tree index, but it is not suitable for practical applications for the following reasons:  
1. For read-only workloads, ER-tree indexes can provide higher query performance. However, for mixed read-write workloads, the indexes are constantly updated with frequent data writing, resulting in increased overheads, which does not seem to work well with the high writing performance of the LSM-tree structure. However, although writing changes the structure of the LSM-tree, most of its structure remains unchanged, especially for the SSTable in the high levels and a large amount of writing does not cause compaction operations to occur in the high-level SSTable. Therefore, indexes built on these high-level SSTables are effective and improve the data query performance. However, for a low-level SSTable, the data change process is faster and whether to build SER-tree indexes on them needs further analysis.
2. In the LSM-tree, many SSTable files have a short lifetime, especially for a low-level SSTable and when a large amount of writing occurs, they are quickly compacted to the next-level SSTable and their lifetime is less than the index build time. Therefore, it is necessary to set a threshold value. If the lifetime of an SSTable file is less than this threshold, there is no need to build an SER-tree index. In this paper, we experimentally measured that for a 4 MB SSTable file and the time to build its index was approximately 45 ms. Therefore, we set a time threshold of \(\mathrm{Tw}=50\) ms. If the lifetime of the SSTable is greater than \(\mathrm{Tw}\), then the index is built for the SSTable; otherwise, it is not built.
3. In addition to the above issues, it is also necessary to consider that even if an SSTable file has a long lifetime, it is not urgent to build indexes on it if there are almost no query tasks. To build an SER-tree index for an SSTable, we need to consider the query gain and the building loss from the index, which are denoted by \(\mathrm{G}_{\mathrm{index}}\) and \(\mathrm{L}_{\mathrm{index}}\), respectively, in this paper. If \(\mathrm{G}_{\mathrm{index  
The data in the above equation cannot be obtained directly from the SSTable file, but rather need to be obtained from the rest of the SSTable files in the same layer that have undergone the entire lifetime, which is defined as SST\({}_{\text{el}}\) in this paper. T\({}_{\text{baseline}}\) is approximately equal to the average baseline method query time on the SST\({}_{\text{el}}\) file before indexing. T\({}_{\text{index}}\) is roughly equivalent to the average index query time on the SST\({}_{\text{el}}\) file, while Q is the number of queries on the SST\({}_{\text{el}}\) file.  
To sum up, an index build decider (IBD) is needed to judge the timing of the index building. The IBD first selects the SSTable whose lifetime is greater than T\({}_{\text{w}}\), then calculates its G\({}_{\text{index}}\) and L\({}_{\text{index}}\). If G\({}_{\text{index}}\) > L\({}_{\text{index}}\), an SER-tree index is established for the SSTable; otherwise. the index waits to be built. Suppose many SSTables meet the index build conditions simultaneously; in this case, the IBD builds the index according to the value of G\({}_{\text{index}}-\text{L}_{\text{index}}\) and the larger the value is, the quicker it will be built to ensure the index achieves the maximum gain.