# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Multidimensional Indexing Techniques
#### 5.1.2 Tree-Based Technique
\begin{table}
\begin{tabular}{l l l l l} \hline \hline
**Proposition** & **Refs** & **Advantages** & **Disadvantages** & \\ \hline \multirow{3}{*}{B-tree} & \multirow{3}{*}{[125]} & • Simple structure & • Consumes a lot of computing resources & • Support only one-dimensional \\  & & • Balanced in insertion and deletion & • Reguires large storage space & • Costly maintenance & data \\  & & • Efficient for k-nn and range search & • & \\ \hline \multirow{3}{*}{B+tree} & \multirow{3}{*}{[126]} & • Storage at leaf nodes & • High complexity & • Requires a considerable \\  & & • Storage cost reduced compared to B-tree & • Nasted storage space & • Ason-optimal node splitting & • Requires a considerable \\ \hline \multirow{3}{*}{B+tree} & \multirow{3}{*}{[127]} & • Reduction of node splitting & • Less storage space compared to B-tree and b+tree & • High complexity & • Limited performance \\ \hline \multirow{3}{*}{T-tree} & \multirow{3}{*}{[127]} & • Balanced structure & • Requires a considerable amount of space & • Logradation on large scale \\  & & • More efficient memory management, search and update performance than B+tree & • The problem of balance is still unresolved & • Degradation on large scale \\ \hline \multirow{3}{*}{UB-tree} & \multirow{3}{*}{[128]} & • Efficient processing of multidimensional requests & • Unsatisfactory for queries covering dead & \\  & & • Effective and efficient update and query performance & • Noted suitable for large data & \\  & & • Structure supports parallel insertions and queries & • Noted suitable for large data & \\ \hline \multirow{3}{*}{MLB+tree} & \multirow{3}{*}{[154]} & • Higher performance on multi-dimensional range queries & • High complexity & • Sub-optimal partitioning \\  & & • More efficient structure & • Irregular and unpredictable structure & \\ \hline \multirow{3}{*}{SR-tree} & \multirow{3}{*}{[132]} & • Simple construction & • Complexity of shapes & \\  & & • Refinement : (intersection S \({}^{\circ}\)R) & • Costly insertion and search algorithm & \\  & & • Reduced overlap rate & • Costly insertion and search algorithm & \\ \hline \multirow{3}{*}{E-tree} & \multirow{3}{*}{[146]} & • Reduce time from linear to sublinear complexity & • High storage space & \\  & & • Reduce computation time & • Costly maintenance & \\  & & • High quality of search results & • K-nn research is not evaluated & \\  & & • More efficient structure & • Degradation on large scale \\ \hline \multirow{3}{*}{R-tree} & \multirow{3}{*}{[130]} & • Creation of filter cells REM & • Overlap of REMs & • Not effective for point queries \\  & & • Balanced hierarchical breakdown & • Require high space and time as well as computational complexities & \\  & & • Constraint of minimum coverage & • Potential complexities & \\ \hline \multirow{3}{*}{R+tree} & \multirow{3}{*}{[137]} & • Reduced overlap rate & • Redundancy of objects in nodes & \\  & & • Reduced overlap rate & • Clipping technique not optimized & \\  & & • More complex construction and maintenance & • Degradation of the performance on large scale \\ \hline \multirow{3}{*}{R+tree} & \multirow{3}{*}{[138]} & • More efficient variant than the R-tree & • Complexity of the re-insertion algorithm & • Degradation of the performance on large scale \\  & & • Reduced overlap rate & • Complexity of the re-insertion algorithm & \\  & & • Efficient use of space & and the split of nodes & \\ \hline Hilbert R-tree & \multirow{3}{*}{[139]} & • Good performance results for both searches and updates & Performance deteriorates for larger data & \\ \hline \multirow{3}{*}{SS-tree} & \multirow{3}{*}{[140]} & • Outperforming the R-tree & • Approximate \\  & & • Calculate the nearest and approximately nearest neighbors efficiently & • High overlap in high-dimension space & \\ \hline \multirow{3}{*}{BFM \& R-tree} & \multirow{3}{*}{[143]} & • Solve the problem of decreasing index performance for high-dimensional data & • High space consumption \\ \cline{3-5}  & & • Enhance R-tree’s search efficiency & • Require high space and computational complexities & \\ \hline \multirow{3}{*}{X-tree} & \multirow{3}{*}{[131]} & • Overlap control (overlap-free) & • Complexity of the max limit & \\  & & • No degeneration of the index & • Consumes a lot of memory space & \\  & & • Reduced overlap rate & • Performance is limited with the data dimension & \\ \hline \multirow{3}{*}{aX-tree} & \multirow{3}{*}{[155]} & • Reduce the amount of empty space & • Supports only static data & \\  & & • Reduced overlap rate & • Require more calculation & \\ \hline \multirow{3}{*}{X+tree} & \multirow{3}{*}{[156]} & • Reduces the complexity of linear scanning of super nodes compared to X-tree & • Stiffers from data redundancy and replication problems & • Cannot function properly in higher-dimensional data \\ \cline{3-5}  & & • Improve space utilization & • High complexity & \\ \cline{3-5}  & & • Reduce node overlap and the number of splits & • Not suitable for the situation of frequent updates & \\ \hline \multirow{3}{*}{BB-tree} & \multirow{3}{*}{[157]} & • Quasi-balanced structure & • Not support the k-nn search & \\ \cline{3-5}  & & • Better performance compared to R\({}^{*}\)-tree, Kd-tree, PH-tree, and VA-file & • Not support the k-nn search & \\ \hline \hline \end{tabular}
\end{table}