Headless Flash Disk Tree: Uma Estrutura Dinâmica em SSD para Dados Unidimensionais
Resumo
Com a transição do uso de discos rígidos para unidades de estado sólido, tornou-se necessário desenvolver novas estruturas de dados que considerem as suas características. Para mitigar os efeitos de restrições como o “apagar antes de escrever”, foram projetadas estruturas de dados capazes de reduzir seu impacto. Nesse contexto, este artigo apresenta a Headless Flash Disk Tree, uma estrutura dinâmica para dados unidimensionais que seguem relação de ordem total, e que melhora o desempenho de operações de inserção e consulta. A avaliação foi realizada usando um conjunto de dados real, e os resultados mostraram que a proposta é até 16% mais rápida que as concorrentes para inserir dados e até 8% mais rápida para realizar consultas.
Palavras-chave:
indexação, dados unidimensionais, HFD-Tree
Referências
Boukhobza, J., Olivier, P., Lim, W. S., Chen, L. C., Hsieh, Y. S., Wu, S. T., Ho, C. C., Huang, P. C., and Chang, Y. H. (2025). A survey on flash-memory storage systems: A host-side perspective. ACM Transactions on Storage, 21(3):1–59.
Carniel, A. C., Ciferri, R. R., and Aguiar, C. D. (2019). A generic and efficient framework for flash-aware spatial indexing. Information Systems, 82:102–120.
Comer, D. (1979). Ubiquitous b-tree. ACM Computing Surveys, 11(2):121–137.
Fevgas, A., Akritidis, L., Bozanis, P., and Manolopoulos, Y. (2019). Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. The VLDB Journal, 29(1):273–311.
Fevgas, A. and Bozanis, P. (2019). Lb-grid: An ssd efficient grid file. Data & Knowledge Engineering, 121:18–41.
Haas, G. and Leis, V. (2023). What modern nvme storage can do, and how to exploit it: High-performance i/o for high-performance storage engines. Proceedings of the VLDB Endowment, 16(9):2090–2102.
Hassani, F. S., Fetrat, A. G., Vanestan, S. B., Gholipoor, M., Zoufan, S., Lee, J. A., and Azad, H. S. (2026). A survey on ssd wear leveling techniques. Computer Science Review, 60:1–14.
Ho, V. P. and Park, D. J. (2018). Wpcb-tree: A novel flash-aware b-tree index using a write pattern converter. Symmetry, 10(1):1–18.
Jiang, Z., Wu, Y., Zhang, Y., Li, C., and Xing, C. (2014). Ab-tree: A write-optimized adaptive index structure on solid state disk. In 11th Web Information System and Application Conference, pages 188–193.
Kim, B. K., Lee, S. W., and Lee, D. H. (2015). h-hash: A hash index structure for flash-based solid state drives. Journal of Circuits, Systems and Computers, 24(09):1–32.
Levandoski, J. J., Lomet, D. B., and Sengupta, S. (2013). The bw-tree: A b-tree for new hardware platforms. In 29th Int. Conference on Data Engineering, pages 302–313.
Li, Y., He, B., Yang, R. J., Luo, Q., and Yi, K. (2010). Tree indexing on solid state drives. Proceedings of the VLDB Endowment, 3(1–2):1195–1206.
Roumelis, G., Velentzas, P., Vassilakopoulos, M., Corral, A., and Manolopoulos, Y. (2018). Spatial batch-queries processing using xBR+-trees in solid-state drives. In 22nd Int. Conference on Database and Expert Systems Applications, pages 301–317.
Sarwat, M., Mokbel, M. F., Zhou, X., and Nath, S. (2011). Fast: a generic framework for flash-aware spatial trees. In 12th International Conference on Advances in Spatial and Temporal Databases, page 149–167.
Teng, D., Guo, L., Lee, R., Chen, F., Zhang, Y., Ma, S., and Zhang, X. (2018). A low-cost disk solution enabling lsm-tree to achieve high performance for mixed read/write workloads. ACM Trans. Storage, 14(2).
Zhang, X., Bhimani, J., Pei, S., Lee, E., Lee, S., Seong, Y. J., Kim, E. J., Choi, C., Nam, E. H., Choi, J., and Kim, B. S. (2025). Storage abstractions for ssds: The past, present, and future. ACM Transactions on Storage, 21(1):1–44.
Carniel, A. C., Ciferri, R. R., and Aguiar, C. D. (2019). A generic and efficient framework for flash-aware spatial indexing. Information Systems, 82:102–120.
Comer, D. (1979). Ubiquitous b-tree. ACM Computing Surveys, 11(2):121–137.
Fevgas, A., Akritidis, L., Bozanis, P., and Manolopoulos, Y. (2019). Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. The VLDB Journal, 29(1):273–311.
Fevgas, A. and Bozanis, P. (2019). Lb-grid: An ssd efficient grid file. Data & Knowledge Engineering, 121:18–41.
Haas, G. and Leis, V. (2023). What modern nvme storage can do, and how to exploit it: High-performance i/o for high-performance storage engines. Proceedings of the VLDB Endowment, 16(9):2090–2102.
Hassani, F. S., Fetrat, A. G., Vanestan, S. B., Gholipoor, M., Zoufan, S., Lee, J. A., and Azad, H. S. (2026). A survey on ssd wear leveling techniques. Computer Science Review, 60:1–14.
Ho, V. P. and Park, D. J. (2018). Wpcb-tree: A novel flash-aware b-tree index using a write pattern converter. Symmetry, 10(1):1–18.
Jiang, Z., Wu, Y., Zhang, Y., Li, C., and Xing, C. (2014). Ab-tree: A write-optimized adaptive index structure on solid state disk. In 11th Web Information System and Application Conference, pages 188–193.
Kim, B. K., Lee, S. W., and Lee, D. H. (2015). h-hash: A hash index structure for flash-based solid state drives. Journal of Circuits, Systems and Computers, 24(09):1–32.
Levandoski, J. J., Lomet, D. B., and Sengupta, S. (2013). The bw-tree: A b-tree for new hardware platforms. In 29th Int. Conference on Data Engineering, pages 302–313.
Li, Y., He, B., Yang, R. J., Luo, Q., and Yi, K. (2010). Tree indexing on solid state drives. Proceedings of the VLDB Endowment, 3(1–2):1195–1206.
Roumelis, G., Velentzas, P., Vassilakopoulos, M., Corral, A., and Manolopoulos, Y. (2018). Spatial batch-queries processing using xBR+-trees in solid-state drives. In 22nd Int. Conference on Database and Expert Systems Applications, pages 301–317.
Sarwat, M., Mokbel, M. F., Zhou, X., and Nath, S. (2011). Fast: a generic framework for flash-aware spatial trees. In 12th International Conference on Advances in Spatial and Temporal Databases, page 149–167.
Teng, D., Guo, L., Lee, R., Chen, F., Zhang, Y., Ma, S., and Zhang, X. (2018). A low-cost disk solution enabling lsm-tree to achieve high performance for mixed read/write workloads. ACM Trans. Storage, 14(2).
Zhang, X., Bhimani, J., Pei, S., Lee, E., Lee, S., Seong, Y. J., Kim, E. J., Choi, C., Nam, E. H., Choi, J., and Kim, B. S. (2025). Storage abstractions for ssds: The past, present, and future. ACM Transactions on Storage, 21(1):1–44.
Publicado
08/09/2026
Como Citar
FORASTEIRO, Diogo Sobral; SILVA, Thiago F. M.; SEABRA, Rodrigo Duarte; SANTOS, Lúcio F. D.; SERAPHIM, Enzo; CARVALHO, Luiz Olmes.
Headless Flash Disk Tree: Uma Estrutura Dinâmica em SSD para Dados Unidimensionais. In: SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 41. , 2026, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 903-909.
ISSN 2763-8979.
DOI: https://doi.org/10.5753/sbbd.2026.249466.
