# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Half Decomposition Strategy and Index Structure of HD-Tree
This is also an important reason for proposing D-tree and HD-tree. When performing data insertion, the D-tree first calculates the integer encoding of the space range that can contain the target in the deepest part of the tree. Then move the code forward to determine if it or the prefix codes have one in the hash table. When an integer code exists in the hash table, the insertion operation can be performed on the node represented by the code. Since the D-tree only stores leaf nodes, if a node can be found, it must have no child nodes. However, if each of these integer codes does not exist in the hash table, the D-tree needs to traverse the hash table (Scheme used by D-tree). From the code of the basic range of the tree to the target code, look down in turn. When we find an encoding that has no suffix encoding in the hash table, we can create a new node here to insert the data. This may require traversing the hash table multiple times. In Figure 2(a), suppose we want to insert a spatial object into the D-tree, and its integer encoding at the deepest point of the tree is 0 \(\times\) 132. Obviously, the three codes 0 \(\times\) 132, 0 \(\times\) 13 and 0 \(\times\) 1 do not exist in the hash table, so it is necessary to start traversing the hash table. We can find the integer encoding prefixed with 0 \(\times\) 1 in the hash table, such as 0 \(\times\) 10, but we can't find a code prefixed with 0 \(\times\) 13 in the hash table. Then we create a leaf node encoded in 0 \(\times\) 13 and insert the spatial object into the node. Here, we need to iterate through the hash table twice, and the second time we need to completely traverse the hash table. When the depth of a D-tree is relatively large, and the hash table is large, it may be necessary to traverse the hash table many times, and each traversal may take a long time, which will seriously affect the efficiency of the operation of the data. However, the HD-tree can solve the problem fundamentally. It can guarantee that the deepest integer encoding of the tree corresponding to the target or its upper layer codes must have one in the hash table. The integer encoding of the lower node is generated by the integer shift operation of the upper node. If the node corresponding to the upper integer encoding has no data, the node will be deleted, but the encoding will still be stored in the hash table. Similarly we want to insert a spatial object, and its integer encoding at the deepest point of the tree is 0 \(\times\) 132. The integer encoding is shifted upward. It can be seen that the codes 0 \(\times\) 132, 0 \(\times\) 13 do not exist in the hash table, but the code 0 \(\times\) 1 exists in the hash table. We only need to insert data into the spatial node represented by 0 \(\times\) 1, and determine whether the number of spatial objects in the spatial node exceeds the maximum number limit. If the number of spatial objects exceeds, a half  
Figure 3: Example of D-tree and half decomposition tree (HD-tree) in four-dimensional space. decomposition strategy is used for the spatial node. Therefore, the HD-tree can greatly improve the efficiency of the data insertion by improving the decomposition strategy of the D-tree. In summary, the HD-tree and D-tree adopt different decomposition strategies while maintaining the virtual tree structure. The strategy used by the HD-tree not only enables it to save nodes and thus saves storage space, but also reduces the number of I/Os for range queries. At the same time, the algorithm efficiency of data insertion is improved. In the next subsection, we will introduce some algorithms for HD-tree.