Un índice LSM-Tree para datos espaciales
Autores: He, Junjun; Chen, Huahui
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un índice LSM-Tree para datos espaciales
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
árbol LSM
Almacenamiento de datos orientado a disco
Consulta espacial
índices secundarios
árbol ER
Eficiencia de consulta
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
Un LSM-tree (árbol de fusión estructurada de registros) es una estructura de almacenamiento de datos jerárquica, ordenada y orientada a disco que aprovecha al máximo las características de la escritura secuencial en disco, las cuales son mucho mejores que las de la escritura aleatoria. Sin embargo, un LSM-tree solo puede ser consultado por una clave y no puede satisfacer las necesidades de una consulta espacial. Para mejorar la eficiencia de consulta de datos espaciales almacenados en LSM-trees, el método tradicional es introducir índices secundarios independientes tipo árbol, el problema con el cual es la amplificación de lectura provocada por consultas de índices duales. Además, cuando se almacenan más datos espaciales, el árbol de índice se vuelve cada vez más grande, lo que trae problemas de menor eficiencia de consulta y un mayor costo de actualización de índices. Para abordar los problemas anteriores, este documento propone una estructura de índice ER-tree (árbol R integrado) basada en la ordenación de los datos de LSM-tree. Al construir una estructura de índice SER-tree (árbol R integrado en una tabla de dispersión ordenada) para cada componente de almacenamiento, optimizamos las consultas de índices duales en índices SER-tree individuales y organizados en un índice ER-tree con una lista enlazada binaria. Los experimentos mostraron que el rendimiento de consulta del índice ER-tree se mejoró de manera efectiva en comparación con el de los índices R-tree independientes.
Descripción
Un LSM-tree (árbol de fusión estructurada de registros) es una estructura de almacenamiento de datos jerárquica, ordenada y orientada a disco que aprovecha al máximo las características de la escritura secuencial en disco, las cuales son mucho mejores que las de la escritura aleatoria. Sin embargo, un LSM-tree solo puede ser consultado por una clave y no puede satisfacer las necesidades de una consulta espacial. Para mejorar la eficiencia de consulta de datos espaciales almacenados en LSM-trees, el método tradicional es introducir índices secundarios independientes tipo árbol, el problema con el cual es la amplificación de lectura provocada por consultas de índices duales. Además, cuando se almacenan más datos espaciales, el árbol de índice se vuelve cada vez más grande, lo que trae problemas de menor eficiencia de consulta y un mayor costo de actualización de índices. Para abordar los problemas anteriores, este documento propone una estructura de índice ER-tree (árbol R integrado) basada en la ordenación de los datos de LSM-tree. Al construir una estructura de índice SER-tree (árbol R integrado en una tabla de dispersión ordenada) para cada componente de almacenamiento, optimizamos las consultas de índices duales en índices SER-tree individuales y organizados en un índice ER-tree con una lista enlazada binaria. Los experimentos mostraron que el rendimiento de consulta del índice ER-tree se mejoró de manera efectiva en comparación con el de los índices R-tree independientes.