# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## 2 Background  
### Concepts  
Some concepts are important for this paper. In this subsection, we illustrate the main features of concepts. * I/O I/Os include network I/O and disk I/O. The I/O mentioned in this article refers to disk I/O. To reduce the number of disk I/Os is the main goal of index optimization. * Rectangle The rectangle [19] in this article represents a range of space, not just 2 dimensions, but possibly many, with a minimum and a maximum on each dimension. For example, a 4-dimensional rectangle has an X-axis range of [0,10], Y-axis range of [10,30], z-axis range of [20,30] and v-axis range of [10,11,12,13,14,15,16,17  
relationships of D-tree are implicated by the integer code of each leaf node, so we can easily calculate the range via an integer code and compute a code, which corresponds to a range. As shown in Figure 1, this is an example of partitioning and encoding of a three-dimensional space. Assume that the integer code of the basic rectangle is 1, the space can be divided into eight subspaces of the same size after dichotomy along the three dimensions of x, y and z, and then the corresponding octal codes are from 010 to 017. Similarly, subspaces can continue to be decomposed. For example, the space represented by 010 can be decomposed into eight subspaces encoded starting from 0100. The D-tree is essentially a gird-based index structure. The unbalanced grid index may result in a large depth of the tree, which usually demands more I/O consumption when indexing, while the D-tree can reduce I/O times by integer shift operations without accessing those inner nodes and leaf nodes without data. Furthermore, it can save the storage space by omitting those nodes mentioned above. Figure 2 shows an example of a four-dimensional D-tree in the paper of D-tree. As a result of the virtual tree, the non-leaf nodes 0 \(\times\) 1, 0 \(\times\) 10, 0 \(\times\) 18, 0 \(\times\) 18b and 0 \(\times\) 18c are not stored, and those nodes without data are not displayed in the figure and need not be stored. The number of nodes of a full balanced hex tree whose depth is four is equal to 4396. In the example of D-tree, it only needs to store 9 leaf nodes with data after space division and encoding. The commonly used balanced tree structure requires n (n is the depth of the tree) disk visits to access a leaf node, but with D-tree, we can access the leaf node by computing integer encoding, with no need to go through the middle node, as we only need one disk visit (assuming the hash table is in memory, disk access to the hash table is not required). Although the performance of the D-tree is excellent, it still has some deficiencies. The full decomposition strategy of the D-tree results in more leaf nodes, and the number of I/Os is larger when executing a range query. Suppose, in a four-dimensional space, when the number of spatial objects of a node reaches the limit, 16 leaf nodes may be required after a D-tree's decomposition, because 16 subspaces may all contain objects. If a node is mapped to a disk page, the D-tree may require at least 16 I/Os to query the range represented by the original node, which is is hard to accept. Moreover, the D-tree may need enormous lookups to the hash table when performing insertion  
Figure 1: Space partition and coding. Figure 2: Example of four-dimensional decomposition tree (D-tree). operation, which will seriously affect efficiency. The hash table in the D-tree is used to determine whether the integer encoding of a certain position exists. Theoretically, the query time complexity can reach O(1). However, when the code and its upper codes do not exist in the hash table, a large number of lookups will need to be performed on the hash table until the same level code or the same level code of prefix code can be found. This means that D-tree needs to determine the level of the leaf node, and establish a node in the same layer to insert data. The query time complexity will seriously degrade to O(n) at this time.