# An LSM-Tree Index for Spatial Data
## 3 SER-Tree Index
### SER-Tree Index Build  
The following describes how to build an SER-tree index on an SSTable. First, we assume that the key and value are of a fixed size, the key is the Hilbert value of the coordinates in the spatial data and the value is the spatial data information. If the size is not specified, one can refer to the method of WiscKey [24] and can use the technique of value log to store the key and value separately, while the key is the Hilbert value and the value is the pointer to the location of that data in the value log.  
The corresponding SER-tree index for each SSTable is then built and each data block in that SSTable, corresponding to a leaf node in the SER-tree index, is defined as follows:  
\[\mathrm{T}_{\mathrm{leaf}}=(\,\mathrm{MBR},\mathrm{db}\_\mathrm{ptr}) \tag{1}\]  
where \(\mathrm{MBR}=(\mathrm{x}_{\mathrm{min}},\mathrm{y}_{\mathrm{min}},\mathrm{x}_{ \mathrm{max}},\mathrm{y}_{\mathrm{max}})\) is the minimum bounding rectangle of the spatial data in the data block and \(\mathrm{db}\_\mathrm{ptr}\) is a pointer to the corresponding data block, as shown in Figure 5 (R1-R16).  
After building the leaf nodes, the middle nodes of the SER-tree are built from the bottom up, as shown in Figure 5 (R17-R22). The middle nodes of the SER-tree are defined as:  
\[\mathrm{T}_{\mathrm{middle}}=(\,\mathrm{cMBR},\mathrm{child\_ptr}) \tag{2}\]  
where cMBR is the minimum bounding rectangle covering all child nodes in the middle node and \(\mathrm{child\_ptr}\) is the set of pointers to the next level of child nodes.  
The SER-tree is built from the bottom up according to the pre-set node size of the SER-tree, up to the root node of the SER-tree. The root node is defined as:  
\[\mathrm{T}=(\mathrm{tMBR},\mathrm{child\_ptr},\mathrm{next}) \tag{3}\]  
where tMBR is the minimum bounding rectangle covering all child nodes in the root node T, child_ptr is the set of pointers of the node to the next level of child nodes and the next  
Figure 4: Hilbert R-tree and R-tree comparison: (**a**) Hilbert curve in spatial coordinates; (**b**) MBR of the Hilbert R-tree; (**c**) MBR of the R-tree.  
pointer is the SER-tree index pointing to the adjacent SSTable. At this point, the SER-tree index on the SSTable is built, as shown in Figure 5.  
The SER-tree index construction algorithm is proposed based on the above structure, as shown in Algorithm 1.  
```
Input: S: SSTable; k: the capacity of SER-Tree node. Output: T: an SER-Tree on SSTable.
1: Q \(\leftarrow\)?; // Q: auxiliary queue
2: for each data block in S, do
3: Build a leaf node N to store the data points in a data block;
4: Q.enqueue (<N,1>);
5: end for
6: while Q.size (>1 do
7: Dequeue the first k nodes of the same level t from Q. //t: the level of SER-Tree
8: Build a node N to store MBRs of the nodes and pointers of the nodes;
9: Q.enqueue (<N,t+1>);
10: end while
11: T \(\leftarrow\) Q.LastNode;
12: return T;
```  
**Algorithm 1** SER-tree build algorithm  
Algorithm 1 describes the process of building an SER-tree index. The auxiliary queue Q is represented as a <N,t> binary, where N represents the leaf nodes and t represents the level of the node in the SER-tree. In the first step, Algorithm 1 builds leaf nodes N for each data block in turn and then pushes them into the queue Q (lines 2-5). In the second step, for the nodes on the same level t in the queue Q, a middle node is built for every k node and the middle node stores the MBRs and pointers of the child nodes; the above operation is repeated until the size of the queue becomes one (lines 6-10). Finally, the last node of the queue Q is deposited into and stored in T, completing the algorithm (lines 11-12).