Árbol de combinación estructurado por registros
 | Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . ( Abril de 2013 ) |
| Árbol de combinación estructurado por registros | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Escribe | Híbrido (dos componentes en forma de árbol) | ||||||||||||||||
| Inventado | 1996 | ||||||||||||||||
| Inventado por | Patrick O'Neil , Edward Cheng, Dieter Gawlick y Elizabeth O'Neil | ||||||||||||||||
| Complejidad del tiempo en notación O grande | |||||||||||||||||
| |||||||||||||||||
En informática , el árbol de fusión estructurado por registros (o árbol LSM) es una estructura de datos con características de rendimiento que lo hacen atractivo para proporcionar acceso indexado a archivos con un gran volumen de inserciones, como los datos de registros transaccionales . Los árboles LSM, al igual que otros árboles de búsqueda , mantienen pares clave-valor. Los árboles LSM mantienen los datos en dos o más estructuras separadas, cada una de las cuales está optimizada para su medio de almacenamiento subyacente respectivo; los datos se sincronizan entre las dos estructuras de manera eficiente, en lotes.
Una versión simple del árbol LSM es un árbol LSM de dos niveles. [1] Como describió Patrick O'Neil , un árbol LSM de dos niveles comprende dos estructuras en forma de árbol , llamadas C 0 y C 1 . C 0 es más pequeño y está completamente residente en la memoria, mientras que C 1 es residente en el disco. Los nuevos registros se insertan en el componente C 0 residente en memoria . Si la inserción hace que el componente C 0 supere un cierto umbral de tamaño, un segmento contiguo de entradas se elimina de C 0 y se fusiona en C 1en disco. Las características de rendimiento de los árboles LSM se derivan del hecho de que cada componente está ajustado a las características de su medio de almacenamiento subyacente, y que los datos se migran de manera eficiente a través de los medios en lotes continuos, utilizando un algoritmo que recuerda al tipo de combinación .
La mayoría de los árboles LSM utilizados en la práctica emplean múltiples niveles. El nivel 0 se guarda en la memoria principal y puede representarse mediante un árbol. Los datos en disco se organizan en series de datos ordenadas . Cada ejecución contiene datos ordenados por clave de índice. Una ejecución se puede representar en el disco como un solo archivo o, alternativamente, como una colección de archivos con rangos de claves que no se superponen. Para realizar una consulta sobre una clave en particular para obtener su valor asociado, se debe buscar en el árbol de Nivel 0 y también en cada ejecución.
Una clave en particular puede aparecer en varias ejecuciones y lo que eso significa para una consulta depende de la aplicación. Algunas aplicaciones simplemente quieren el par clave-valor más reciente con una clave determinada. Algunas aplicaciones deben combinar los valores de alguna manera para obtener el valor agregado adecuado que se devolverá. Por ejemplo, en Apache Cassandra , cada valor representa una fila en una base de datos y diferentes versiones de la fila pueden tener diferentes conjuntos de columnas. [2]
Para mantener bajo el costo de las consultas, el sistema debe evitar una situación en la que haya demasiadas ejecuciones.
Se han sugerido extensiones al método 'nivelado' para incorporar estructuras de árbol B + , por ejemplo, bLSM [3] y Diff-Index. [4]
Los árboles LSM se utilizan en almacenes de datos como Apache AsterixDB , Bigtable , HBase , LevelDB , SQLite4 , [5] Tarantool , [6] RocksDB , WiredTiger , [7] Apache Cassandra , InfluxDB [8] y ScyllaDB .
Referencias
- ^ O'Neil 1996, p. 4
- ^ "Compactación nivelada en Apache Cassandra: DataStax" . 13 de febrero de 2014. Archivado desde el original el 13 de febrero de 2014.
- ^ https://web.archive.org/web/20160127170015/http://www.eecs.harvard.edu/~margo/cs165/papers/gp-lsm.pdf
- ^ http://researcher.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf
- ^ "SQLite4 con LSM Wiki" . SQLite.
- ^ "Un servidor de aplicaciones junto con un administrador de bases de datos" . Consultado el 3 de abril de 2018 .
El motor de almacenamiento basado en disco de Tarantool es una fusión de ideas de sistemas de archivos modernos, árboles de fusión estructurados por registros y árboles B clásicos.
- ^ "GitHub - wiredtiger / wiredtiger: árbol de fuentes de WiredTiger" . 4 de diciembre de 2019 - a través de GitHub.
- ^ Dix, Paul (7 de octubre de 2015). "[Nuevo] motor de almacenamiento InfluxDB | Árbol de fusión estructurado en el tiempo" .
- General
- O'Neil, Patrick E .; Cheng, Edward; Gawlick, Dieter; O'Neil, Elizabeth (junio de 1996). "El árbol de fusión estructurado por registros (árbol LSM)". Acta Informatica . 33 (4): 351–385. CiteSeerX 10.1.1.44.2782 . doi : 10.1007 / s002360050048 .
- Li, Yinan; Él, Bingsheng; Luo, Qiong; Yi, Ke (2009). "Indexación de árboles en discos flash". 2009 IEEE 25th International Conference on Data Engineering . págs. 1303–6. CiteSeerX 10.1.1.144.6961 . doi : 10.1109 / ICDE.2009.226 . ISBN 978-1-4244-3422-0.
- Luo, Chen; Carey, Michael J. (julio de 2019). "Técnicas de almacenamiento basadas en LSM: una encuesta". El diario VLDB . arXiv : 1812.07527 . doi : 10.1007 / s00778-019-00555-y .
enlaces externos
- Una descripción general de los árboles de fusión estructurados de registros
- Árboles (estructuras de datos)
- Técnicas de índice de base de datos
