Índice de árbol fractal

En informática , un índice de árbol fractal es una estructura de datos de árbol que mantiene los datos ordenados y permite búsquedas y acceso secuencial en el mismo tiempo que un árbol B , pero con inserciones y eliminaciones asintóticamente más rápidas. Al igual que un árbol B, un índice de árbol fractal es una generalización de un árbol de búsqueda binaria, ya que un nodo puede tener más de dos hijos. Además, a diferencia de un árbol B, un índice de árbol fractal tiene búferes en cada nodo, que permiten almacenar inserciones, eliminaciones y otros cambios en ubicaciones intermedias. El objetivo de los búferes es programar las escrituras en disco de manera que cada escritura realice una gran cantidad de trabajo útil, evitando así el peor caso de rendimiento de los árboles B, en el que cada escritura en disco puede cambiar una pequeña cantidad de datos en el disco. Al igual que un árbol B, los índices de árbol fractal están optimizados para sistemas que leen y escriben grandes bloques de datos. El índice de árbol fractal ha sido comercializado en bases de datos por Tokutek . Originalmente, se implementó como una matriz de anticipación ajena a la caché, ^{[ 1 ]} pero la implementación actual es una extensión del árbol B ^{ε .}^{[ 2 ]} El B ^ε está relacionado con el árbol de repositorio en búfer. ^{[ 3 ]} El árbol de repositorio en búfer tiene grado 2, mientras que el árbol B ^ε tiene grado B ^ε . El índice de árbol fractal también se ha utilizado en un prototipo de sistema de archivos . ^{[ 4 ]}^{[ 5 ]} Hay disponible una implementación de código abierto del índice de árbol fractal, ^{[ 6 ]} que demuestra los detalles de implementación descritos a continuación.

Descripción general

En los índices de árboles fractales, los nodos internos ( no hojas ) pueden tener un número variable de nodos hijos dentro de un rango predefinido. Cuando se insertan o eliminan datos de un nodo, cambia el número de nodos hijos. Para mantener el rango predefinido, los nodos internos pueden unirse o dividirse. Cada nodo interno de un árbol B contiene un número de claves que es uno menos que su factor de ramificación . Las claves actúan como valores de separación que dividen sus subárboles . Las claves en los subárboles se almacenan en el orden del árbol de búsqueda , es decir, todas las claves en un subárbol están entre los dos valores entre corchetes. En este sentido, son iguales a los árboles B.

Los índices de árboles fractales y los árboles B explotan el hecho de que cuando se recupera un nodo del almacenamiento, un bloque de memoria, cuyo tamaño se denota por $B$ , se obtiene. Por lo tanto, los nodos se ajustan para tener un tamaño aproximado $B$ Dado que el acceso al almacenamiento puede dominar el tiempo de ejecución de una estructura de datos, la complejidad temporal de los algoritmos de memoria externa está determinada principalmente por la cantidad de lecturas/escrituras que genera dicha estructura. (Véase, por ejemplo, ^{[ 7 ]} para los análisis posteriores).

En un árbol B, esto significa que el número de claves en un nodo está diseñado para ser suficiente para llenar el nodo, con cierta variabilidad para las divisiones y fusiones de nodos. Para fines de análisis teórico, si $O(B)$ Las claves encajan en un nodo, entonces el árbol tiene profundidad. $O(\log _{B}N)$ y esta es la complejidad de E/S tanto de las búsquedas como de las inserciones.

Los nodos de los árboles fractales utilizan un factor de ramificación más pequeño, por ejemplo, de ${\sqrt {B}}$ La profundidad del árbol es entonces $O(\log _{\sqrt {B}}N)=O(\log _{B}N)$ , coincidiendo así asintóticamente con el árbol B. El espacio restante en cada nodo se utiliza para almacenar en búfer las inserciones, eliminaciones y actualizaciones, a las que nos referimos en conjunto como mensajes. Cuando un búfer está lleno, se vacía en bloque en los hijos. Hay varias opciones para vaciar los búferes, todas ellas conllevan una complejidad de E/S similar. Cada mensaje en el búfer de un nodo se vaciará en un hijo en particular, según lo determine su clave. Supongamos, para mayor concreción, que se vacían los mensajes que se dirigen al mismo hijo, y que entre los ${\sqrt {B}}+1$ niños, elegimos el que tiene más mensajes. Entonces hay al menos ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ mensajes que se pueden enviar al niño. Cada descarga requiere $O(1)$ vaciados, y por lo tanto el costo por mensaje de un vaciado es $O\left({\frac {1}{\sqrt {B}}}\right)$ .

Consideremos el costo de una inserción. Cada mensaje se envía por el desagüe. $O(\log _{B}N)$ veces, y el costo de una descarga es $O\left({\frac {1}{\sqrt {B}}}\right)$ Por lo tanto, el costo de una inserción es $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ . Finalmente, tenga en cuenta que el factor de ramificación puede variar, pero para cualquier factor de ramificación $B^{\varepsilon }$ , el costo de una descarga es $O\left({\frac {1}{B^{1-\varepsilon }}}\right)$ De este modo, se logra un equilibrio adecuado entre el coste de búsqueda, que depende de la profundidad del árbol de búsqueda y, por lo tanto, del factor de ramificación, y el tiempo de inserción, que depende de la profundidad del árbol, pero de forma más sensible al tamaño de los vaciados del búfer.

Comparaciones con otros índices de memoria externa

Esta sección compara los índices de árboles fractales con otras estructuras de datos de indexación de memoria externa. La literatura teórica sobre este tema es muy extensa, por lo que esta discusión se limita a una comparación con estructuras de datos populares que se utilizan en bases de datos y sistemas de archivos.

Árboles B

El tiempo de búsqueda de un árbol B es asintóticamente el mismo que el de un índice de árbol fractal. Sin embargo, un índice de árbol fractal tiene árboles más profundos que un árbol B, y si cada nodo requiriera una operación de entrada/salida (por ejemplo, si la caché está inactiva), un índice de árbol fractal generaría más operaciones de entrada/salida. No obstante, para muchas cargas de trabajo, la mayoría o la totalidad de los nodos internos, tanto de los árboles B como de los índices de árbol fractal, ya están almacenados en la memoria RAM. En este caso, el costo de la búsqueda está dominado por el costo de recuperar la hoja, que es el mismo en ambos casos. Por lo tanto, para muchas cargas de trabajo, los índices de árbol fractal pueden igualar a los árboles B en términos de tiempo de búsqueda.

La diferencia radica en las inserciones, eliminaciones y actualizaciones. Una inserción en un índice de árbol fractal requiere $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ mientras que los árboles B requieren $O(\log _{B}N)$ Por lo tanto, los índices de árboles fractales son más rápidos que los árboles B por un factor de $O({\sqrt {B}})$ . Desde $B$ puede ser bastante grande, esto produce una mejora potencial de dos órdenes de magnitud en los tiempos de inserción en el peor de los casos, lo cual se observa en la práctica. Tanto los árboles B como los índices de árboles fractales pueden realizar inserciones más rápido en el mejor de los casos. Por ejemplo, si las claves se insertan en orden secuencial, ambas estructuras de datos logran una $O\left({\frac {1}{B}}\right)$ Operaciones de entrada/salida por inserción. Por lo tanto, debido a que los casos óptimos y pesimistas de los árboles B difieren ampliamente, mientras que los índices de árboles fractales siempre se encuentran cerca de su mejor caso, la aceleración real que logran los índices de árboles fractales con respecto a los árboles B depende de los detalles de la carga de trabajo.

árboles de fusión estructurados en registros

Los árboles de fusión con estructura de registro (LSM) son una clase de estructuras de datos que consisten en dos o más estructuras de índice con capacidades que crecen exponencialmente. Cuando un árbol alcanza su capacidad máxima, se fusiona con el siguiente nivel, que tiene mayor capacidad. La complejidad de entrada/salida de un LSM depende de parámetros como el factor de crecimiento entre niveles y la estructura de datos elegida en cada nivel. Por lo tanto, para analizar la complejidad de los LSM, es necesario seleccionar una versión específica. Para fines comparativos, elegimos la versión de LSM que iguala el rendimiento de inserción de los índices de árbol fractal.

Supongamos que se implementa un LSM mediante $O(\log _{B}N)$ Árboles B, cada uno de los cuales tiene una capacidad que es ${\sqrt {B}}$ más grande que su predecesor. El tiempo de fusión depende de tres hechos: El orden ordenado de las claves en un $N$ -El elemento B-tree se puede producir en $O\left({\frac {N}{B}}\right)$ E/S; Dos listas ordenadas de $N$ y $M$ Los elementos se pueden fusionar en una lista ordenada en $O\left({\frac {N+M}{B}}\right)$ E/S; y un árbol B de una lista ordenada de $N$ Los elementos se pueden construir en $O\left({\frac {N}{B}}\right)$ E/S. Cuando un árbol se desborda, se fusiona en un árbol cuyo tamaño es $O({\sqrt {B}})$ más grande, por lo tanto, un nivel que contiene $k$ artículos requieren $O\left({\frac {k}{\sqrt {B}}}\right)$ IO para fusionar. Un elemento puede fusionarse una vez por nivel, lo que da un tiempo total de $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ , que coincide con el índice del árbol fractal.

El tiempo de consulta es simplemente el tiempo de consulta del árbol B en cada nivel. El tiempo de consulta en el $i$ ^El nivel es $O(\log _{B}B^{\frac {i}{2}})=O(i)$ , ya que el $i$ ^El nivel tiene capacidad $B^{\frac {i}{2}}$ Por lo tanto, el tiempo total es $O(\log _{B}^{2}N)$ Esto supera en un factor logarítmico tanto a los índices de árboles B como a los de árboles fractales. De hecho, si bien los índices de árboles B y fractales se encuentran en la curva de equilibrio óptimo entre inserciones y consultas, los LSM no. Son incomparables con los árboles B y están dominados por los índices de árboles fractales.

Algunas notas sobre los LSM: existen maneras de acelerar las consultas. Por ejemplo, si solo se requieren consultas de pertenencia y no de sucesores, predecesores o rangos, se pueden usar filtros de Bloom para agilizarlas. Además, se puede establecer el factor de crecimiento entre niveles en otro valor, lo que permite diferentes compensaciones entre la inserción y la consulta. Sin embargo, para cada tasa de inserción elegida, el índice de árbol fractal correspondiente ofrece consultas más rápidas.

Árboles B ^ε

El índice de árbol fractal es un refinamiento del árbol Bε ^. Al igual que un árbol Bε ^, consta de nodos con claves y búferes, y logra el equilibrio óptimo entre inserción y consulta. El índice de árbol fractal se diferencia por incluir optimización del rendimiento y por extender su funcionalidad. Ejemplos de funcionalidad mejorada incluyen la semántica ACID . Las implementaciones de la semántica ACID en árboles B suelen implicar el bloqueo de las filas involucradas en transacciones activas. Este esquema funciona bien en un árbol B porque tanto las inserciones como las consultas implican la recuperación de la misma hoja en memoria. Por lo tanto, bloquear una fila insertada no conlleva una penalización de E/S. Sin embargo, en los índices de árbol fractal, las inserciones son mensajes, y una fila puede residir en más de un nodo simultáneamente. Por consiguiente, los índices de árbol fractal requieren una estructura de bloqueo independiente que sea eficiente en E/S o que resida en memoria para implementar el bloqueo necesario para la semántica ACID.

Los índices de árbol fractal también cuentan con varias optimizaciones de rendimiento. En primer lugar, los búferes se indexan para acelerar las búsquedas. En segundo lugar, las hojas son mucho más grandes que en los árboles B, lo que permite una mayor compresión. De hecho, las hojas se eligen con un tamaño suficiente para que su tiempo de acceso esté dominado por el tiempo de ancho de banda, amortizando así la latencia de búsqueda y rotación. Las hojas grandes son ventajosas para las consultas de rango amplio, pero ralentizan las consultas puntuales, que requieren acceder a una pequeña porción de la hoja. La solución implementada en los índices de árbol fractal consiste en tener hojas grandes que se pueden recuperar en su totalidad para consultas de rango rápidas, pero que se dividen en partes más pequeñas llamadas nodos base, que se pueden recuperar individualmente. Acceder a un nodo base es más rápido que acceder a una hoja, debido al menor tiempo de ancho de banda. Por lo tanto, la subestructura de las hojas en los índices de árbol fractal, en comparación con los árboles Bε, ^permite que tanto las consultas de rango como las puntuales sean rápidas.

Índices de mensajería y árboles fractales

Las inserciones, eliminaciones y actualizaciones se insertan como mensajes en búferes que se dirigen hacia los nodos hoja. La infraestructura de mensajería puede utilizarse para implementar diversas operaciones, algunas de las cuales se describen a continuación.

Actualizaciones e inserciones

Una operación upsert es una instrucción que inserta una fila si no existe y la actualiza si ya existe. En un árbol B, una operación upsert se implementa buscando primero la fila y luego insertándola o actualizándola, según el resultado de la búsqueda. Esto requiere cargar la fila en memoria si no está almacenada en caché. Un índice de árbol fractal puede implementar una operación upsert insertando un mensaje especial. Dicho mensaje puede, en teoría, implementar fragmentos de código arbitrarios durante la actualización. En la práctica, se admiten cuatro operaciones de actualización:

$x:={\text{constante}}$
$x:=x+{\text{constante}}$ (un incremento generalizado)
$x:=x-{\text{constante}}$ (un decremento generalizado)
$x:={\begin{cases}0&{\text{si }}x=0\\x-1&{\text{si }}x\neq 0\end{cases}}$ (un decremento con un mínimo en 0)

Estas corresponden a las operaciones de actualización utilizadas en LinkBench, ^{[ 8 ]} un benchmark propuesto por Facebook. Al evitar la búsqueda inicial, los mensajes upsert pueden mejorar la velocidad de las operaciones upsert en varios órdenes de magnitud.

Cambios en el esquema

Hasta ahora, todos los tipos de mensajes han modificado filas individuales. Sin embargo, los mensajes de difusión, que se copian a todos los búferes de salida, pueden modificar todas las filas de una base de datos. Por ejemplo, los mensajes de difusión se pueden usar para cambiar el formato de todas las filas. Si bien el trabajo total necesario para cambiar todas las filas no varía con respecto al método de fuerza bruta de recorrer la tabla, la latencia mejora, ya que, una vez que el mensaje se inyecta en el búfer raíz, todas las consultas posteriores podrán aplicar la modificación del esquema a cualquier fila que encuentren. El cambio de esquema es inmediato y el trabajo se pospone hasta que los búferes se desborden y las hojas se actualicen de todos modos.

Implementaciones

El índice de árbol fractal ha sido implementado y comercializado por Tokutek . Está disponible como TokuDB , un motor de almacenamiento para MySQL y MariaDB , y como TokuMX, una integración más completa con MongoDB . Los índices de árbol fractal también se han utilizado en sistemas de archivos prototipo, TokuFS ^{[ 4 ]} y BetrFS ^{[ 5 ] .}

Referencias

↑ Bender, MA; Farach-Colton, M.; Fineman, J.; Fogel, Y.; Kuszmaul, B.; Nelson, J. (junio de 2007). "Árboles B de transmisión independientes de la caché" . Actas del 19.º Simposio Anual de la ACM sobre Paralelismo en Algoritmos y Arquitecturas . CA : ACM Press: 81–92 . Archivado del original el 11 de noviembre de 2020. Consultado el 15 de marzo de 2014 .
↑ Brodal, G.; Fagerberg, R. (enero de 2003). "Límites inferiores para diccionarios de memoria externa" . Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos . Nueva York : ACM Press: 546–554 .
↑ Buchsbaum, A.; Goldwasswer, M.; Venkatasubramanian, S.; Westbrook, J. (enero de 2000). "Sobre el recorrido de grafos con memoria externa". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos : 859–860 . CiteSeerX 10.1.1.27.9904 .
1 2 Esmet, J.; Bender, M.; Farach-Colton, M.; Kuszmaul, B. (junio de 2012). "El sistema de archivos de transmisión TokuFS" (PDF) . Actas de la 4.ª Conferencia USENIX sobre temas candentes en almacenamiento y sistemas de archivos . MA : USENIX Association. pág. 14.
1 2 Jannen, William; Yuan, Jun; Zhan, Yang; Akshintala, Amogh; Esmet, John; Jiao, Yizheng; Mittal, Ankur; Pandey, Prashant; Reddy, Phaneendra; Walsh, Leif; Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Kuszmaul, Bradley C.; Porter, Donald E. (febrero de 2015). "BetrFS: un sistema de archivos optimizado para escritura y con optimización a la derecha" (PDF) . Actas de la 13.ª Conferencia USENIX sobre Tecnologías de Archivos y Almacenamiento . Santa Clara, California.
↑ Repositorio de Github
^ Cormen, T.; Leiserson, CE; Rivest, R.; Stein, C. (2001). Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill . ISBN 0-262-03293-7.
↑ Armstrong, T.; Ponnekanti, V.; Borthakur, D.; Callaghan, M. (2013). «LinkBench: Un benchmark de bases de datos basado en el grafo social de Facebook». Actas de la Conferencia Internacional ACM SIGMOD de 2013 sobre Gestión de Datos . Nueva York : ACM Press. págs. 1185–1196 . doi : 10.1145/2463676.2465296 . ISBN 9781450320375. S2CID 11759711 .

[cola-1] Bender, MA; Farach-Colton, M.; Fineman, J.; Fogel, Y.; Kuszmaul, B.; Nelson, J. (junio de 2007). "Árboles B de transmisión independientes de la caché" . Actas del 19.º Simposio Anual de la ACM sobre Paralelismo en Algoritmos y Arquitecturas . CA : ACM Press: 81–92 . Archivado del original el 11 de noviembre de 2020. Consultado el 15 de marzo de 2014 .

[2] Brodal, G.; Fagerberg, R. (enero de 2003). "Límites inferiores para diccionarios de memoria externa" . Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos . Nueva York : ACM Press: 546–554 .

[3] Buchsbaum, A.; Goldwasswer, M.; Venkatasubramanian, S.; Westbrook, J. (enero de 2000). "Sobre el recorrido de grafos con memoria externa". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos : 859–860 . CiteSeerX 10.1.1.27.9904 .

[tokufs-4] 1 2 Esmet, J.; Bender, M.; Farach-Colton, M.; Kuszmaul, B. (junio de 2012). "El sistema de archivos de transmisión TokuFS" (PDF) . Actas de la 4.ª Conferencia USENIX sobre temas candentes en almacenamiento y sistemas de archivos . MA : USENIX Association. pág. 14.

[betrfs-5] 1 2 Jannen, William; Yuan, Jun; Zhan, Yang; Akshintala, Amogh; Esmet, John; Jiao, Yizheng; Mittal, Ankur; Pandey, Prashant; Reddy, Phaneendra; Walsh, Leif; Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Kuszmaul, Bradley C.; Porter, Donald E. (febrero de 2015). "BetrFS: un sistema de archivos optimizado para escritura y con optimización a la derecha" (PDF) . Actas de la 13.ª Conferencia USENIX sobre Tecnologías de Archivos y Almacenamiento . Santa Clara, California.

[ftisource-6] Repositorio de Github

[clrs-7] Cormen, T.; Leiserson, CE; Rivest, R.; Stein, C. (2001). Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill . ISBN 0-262-03293-7.

[link_bench-8] Armstrong, T.; Ponnekanti, V.; Borthakur, D.; Callaghan, M. (2013). «LinkBench: Un benchmark de bases de datos basado en el grafo social de Facebook». Actas de la Conferencia Internacional ACM SIGMOD de 2013 sobre Gestión de Datos . Nueva York : ACM Press. págs. 1185–1196 . doi : 10.1145/2463676.2465296 . ISBN 9781450320375. S2CID 11759711 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]