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 al mismo tiempo que un árbol B, pero con inserciones y eliminaciones asintóticamente más rápidas que un árbol B. Como un árbol B, un índice de árbol fractal es una generalización de un árbol de búsqueda binariaen 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 que las inserciones, eliminaciones y otros cambios se almacenen en ubicaciones intermedias. El objetivo de los búferes es programar escrituras en disco para que cada escritura realice una gran cantidad de trabajo útil, evitando así el peor rendimiento de los árboles B, en los que cada escritura en disco puede cambiar una pequeña cantidad de datos en el disco. Como un árbol B, los índices de árboles fractales 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 búsqueda anticipada ajena a la memoria caché, [1] pero la implementación actual es una extensión de B εárbol. [2] La B ε está relacionada con el árbol del repositorio almacenado en búfer. [3] El árbol del repositorio en búfer tiene un grado 2, mientras que el árbol B ε tiene un grado B ε . El índice de árbol fractal también se ha utilizado en un prototipo de sistema de archivos . [4] [5] Una de código abierto aplicación del índice de árbol fractal está disponible, [6] que demuestra los detalles de implementación se describen a continuación.
Índice de árbol fractal | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado | 2007 | ||||||||||||||||||||
Inventado por | Michael A. Bender, Martin Farach-Colton , Bradley C. Kuszmaul | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Descripción general
En los índices de árboles fractales, los nodos internos ( no hoja ) pueden tener un número variable de nodos secundarios dentro de un rango predefinido. Cuando se insertan o eliminan datos de un nodo, su número de nodos secundarios cambia. Para mantener el rango predefinido, los nodos internos pueden unirse o dividirse. Cada nodo interno de un árbol B contendrá 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 de los subárboles se almacenan en el orden del árbol de búsqueda , es decir, todas las claves de un subárbol se encuentran entre los dos valores entre corchetes. En este sentido, son como árboles B.
Los índices de árboles fractales y los árboles B explotan el hecho de que cuando un nodo se extrae del almacenamiento, un bloque de memoria, cuyo tamaño se denota por , se busca. Por lo tanto, los nodos están ajustados para tener un tamaño aproximado. 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á dominada por el número de lecturas / escrituras que induce una estructura de datos. (Ver, por ejemplo, [7] para los siguientes análisis).
En un árbol B, esto significa que el número de claves en un nodo está destinado a ser suficiente para llenar el nodo, con cierta variabilidad para las divisiones y fusiones de nodos. A los efectos del análisis teórico, si las claves encajan en un nodo, entonces el árbol tiene profundidad , y esta es la complejidad de E / S tanto de las búsquedas como de las inserciones.
Los nodos de árboles fractales usan un factor de ramificación más pequeño, digamos, de . La profundidad del árbol es entonces, haciendo coincidir asintóticamente el árbol B. El espacio restante en cada nodo se utiliza para almacenar en búfer las inserciones, la eliminación y las actualizaciones, a las que nos referimos en conjunto como mensajes. Cuando un búfer está lleno, se descarga a los niños a granel. Hay varias opciones sobre cómo se vacían los búferes, todas conduciendo a una complejidad de E / S similar. Cada mensaje en un búfer de nodo se vaciará a un niño en particular, según lo determinado por su clave. Supongamos, para ser concretos, que se tiran mensajes que se dirigen al mismo niño, y que entre losniños, elegimos el que tiene más mensajes. Entonces hay al menosmensajes que se pueden enviar al niño. Cada descarga requiere descargas, y por lo tanto, el costo por mensaje de una descarga es .
Considere el costo de una inserción. Cada mensaje se ruboriza veces, y el costo de una descarga es . Por lo tanto, el costo de una inserción es. Finalmente, tenga en cuenta que el factor de ramificación puede variar, pero para cualquier factor de ramificación, el costo de una descarga es , lo que proporciona un equilibrio suave entre el costo de búsqueda, que depende de la profundidad del árbol de búsqueda y, por lo tanto, el factor de ramificación, frente al tiempo de inserción, que depende de la profundidad del árbol, pero más sensiblemente del tamaño de las descargas de búfer.
Comparaciones con otros índices de memoria externa
Esta sección compara índices de árboles fractales con otras estructuras de datos de indexación de memoria externa. La literatura teórica sobre este tema es muy amplia, 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 E / S, digamos si la caché está fría, entonces un índice de árbol fractal induciría más IO. Sin embargo, para muchas cargas de trabajo, la mayoría o todos los nodos internos de los árboles B y los índices de árboles fractales ya están almacenados en caché en la RAM. En este caso, el costo de una búsqueda está dominado por el costo de buscar la hoja, que es el mismo en ambos casos. Por lo tanto, para muchas cargas de trabajo, los índices de árboles fractales pueden coincidir con los árboles B en términos de tiempo de búsqueda.
Donde difieren es en inserciones, eliminaciones y actualizaciones. Una inserción en un índice de árbol fractal toma mientras que los árboles B requieren . Por lo tanto, los índices de árboles fractales son más rápidos que los árboles B en un factor de. Desdepuede ser bastante grande, esto produce una mejora potencial de dos órdenes de magnitud en los tiempos de inserción del peor de los casos, lo que 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 unE / S por inserción. Por lo tanto, debido a que los mejores y peores casos de árboles B difieren ampliamente, mientras que los índices de árboles fractales siempre están cerca de su mejor caso, la aceleración real que logran los índices de árboles fractales sobre los árboles B depende de los detalles de la carga de trabajo.
Árboles de fusión estructurados por registros
Los árboles de fusión estructurados en registros (LSM) se refieren a una clase de estructuras de datos que consta de dos o más estructuras de índice de capacidades de crecimiento exponencial. Cuando un árbol en algún nivel alcanza su capacidad, se fusiona con el siguiente nivel más grande. La IO-complejidad 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 que para analizar la complejidad de los LSM, debemos elegir una versión específica. Para fines de comparación, seleccionamos la versión de LSM que coincide con los índices de árboles fractales en el rendimiento de inserción.
Suponga que un LSM se implementa a través de Árboles B, cada uno de los cuales tiene una capacidad que es más grande que su predecesor. El tiempo de fusión depende de tres hechos: El orden de clasificación de las claves en un-El árbol del artículo B se puede producir en IOs; Dos listas ordenadas de y los elementos se pueden combinar en una lista ordenada en IOs; y un árbol B de una lista ordenada de los elementos se pueden incorporar IOs. Cuando un árbol se desborda, se fusiona en un árbol cuyo tamaño es más grande, por lo tanto, un nivel que mantiene los artículos requieren IO para fusionar. Un elemento puede combinarse una vez por nivel, lo que da un tiempo total de, 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 elel nivel es, ya que el el nivel tiene capacidad. Por tanto, el tiempo total es. Esto es más grande que los índices del árbol B y del árbol fractal por un factor logarítmico. De hecho, aunque los árboles B y los índices de árboles fractales se encuentran en la curva de compensación óptima entre inserciones y consultas, los LSM no lo están. Son incomparables con los árboles B y están dominados por índices de árboles fractales.
Algunas notas sobre los LSM: hay formas de agilizar las consultas. Por ejemplo, si solo se requieren consultas de membresía y no se requieren consultas de sucesor / predecesor / rango, entonces los filtros Bloom se pueden usar para acelerar las consultas. Además, el factor de crecimiento entre niveles se puede establecer en algún otro valor, dando un rango de compensaciones de inserción / consulta. Sin embargo, para cada elección de tasa de inserción, el índice de árbol fractal correspondiente tiene consultas más rápidas.
Árboles B ε
El índice del árbol fractal es un refinamiento del árbol B ε . Al igual que un árbol B ε , consta de nodos con claves y búferes y realiza la compensación óptima entre inserción / consulta. El índice de árbol fractal difiere en la inclusión de la optimización del rendimiento y en la ampliación de la funcionalidad. Los ejemplos de funcionalidad mejorada incluyen la semántica ACID . Las implementaciones de árbol B de la semántica ACID generalmente implican bloquear filas que están involucradas en transacciones activas. Este esquema funciona bien en un árbol B porque tanto las inserciones como las consultas implican recuperar la misma hoja en la memoria. Por lo tanto, bloquear una fila insertada no genera una penalización de IO. Sin embargo, en los índices de árboles fractales, las inserciones son mensajes y una fila puede residir en más de un nodo al mismo tiempo. Por lo tanto, los índices de árbol fractal requieren una estructura de bloqueo separada que sea eficiente en IO o que resida en la memoria para implementar el bloqueo involucrado en la implementación de la semántica ACID.
Los índices de árboles fractales también tienen 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 para que sean lo suficientemente grandes como para que su tiempo de acceso esté dominado por el tiempo de ancho de banda y, por lo tanto, amortice la latencia de búsqueda y rotación. Las hojas grandes son una ventaja con consultas de rango grande 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 árboles fractales es tener hojas grandes que se pueden buscar en su totalidad para consultas de rango rápido, pero que se dividen en partes más pequeñas llamadas nodos del sótano que se pueden buscar individualmente. Acceder a un nodo del sótano es más rápido que acceder a una hoja, debido al tiempo de ancho de banda reducido. Por lo tanto, la subestructura de las hojas en los índices de árboles fractales, en comparación con los árboles B ε , permite que las consultas de rango y punto sean rápidas.
Índices de árbol de mensajería y fractales
Las inserciones, eliminaciones y actualizaciones se insertan como mensaje en búferes que se abren paso hacia las hojas. La infraestructura de mensajería se puede aprovechar para implementar una variedad de otras operaciones, algunas de las cuales se describen a continuación.
Upserts
Un upsert es una declaración que inserta una fila si no existe y la actualiza si existe. En un árbol B, un upsert se implementa buscando primero la fila y luego implementando una inserción o una actualización, dependiendo del resultado de la búsqueda. Esto requiere recuperar la fila en la memoria si aún no está almacenada en caché. Un índice de árbol fractal puede implementar un upsert insertando un mensaje upsert especial. En teoría, un mensaje de este tipo puede implementar piezas de código arbitrarias durante la actualización. En la práctica, se admiten cuatro operaciones de actualización:
- x = constante
- x = x + constante (un incremento generalizado)
- x = x - constante (una disminución generalizada)
- x = si (x = 0, 0, x-1) (una disminución con un piso en 0)
Estos corresponden a las operaciones de actualización utilizadas en LinkBench, [8] un punto de referencia propuesto por Facebook. Al evitar la búsqueda inicial, los mensajes upsert pueden mejorar la velocidad de los upserts en órdenes de magnitud.
Cambios de esquema
Hasta ahora, todos los tipos de mensajes tienen filas individuales modificadas. Sin embargo, los mensajes de difusión, que se copian en todos los búferes salientes, pueden modificar todas las filas de una base de datos. Por ejemplo, los mensajes de difusión se pueden utilizar para cambiar el formato de todas las filas de una base de datos. Aunque el trabajo total requerido para cambiar todas las filas no cambia con respecto al método de fuerza bruta de atravesar la tabla, la latencia se 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 las filas que encuentren. El cambio de esquema es inmediato y el trabajo se aplaza hasta un momento en el que los búferes se desborden y las hojas se hayan actualizado de todos modos.
Implementaciones
El índice de árbol fractal ha sido implementado y comercializado por Tokutek . Está disponible como TokuDB como 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 un sistema de archivos prototipo, TokuFS. [4]
Referencias
- ^ Bender, MA; Farach-Colton, M .; Fineman, J .; Fogel, Y .; Kuszmaul, B .; Nelson, J. (junio de 2007). "Árboles B de transmisión de caché ajenos" . Actas del XIX Simposio anual de ACM sobre paralelismo en algoritmos y arquitecturas . CA : ACM Press: 81–92.
- ^ 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 . NY : ACM Press: 546–554.
- ^ Buchsbaum, A .; Goldwasswer, M .; Venkatasubramanian, S .; Westbrook, J. (enero de 2000). "Sobre el recorrido del gráfico de memoria externa". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos : 859–860. CiteSeerX 10.1.1.27.9904 .
- ^ a b Esmet, J .; Bender, M .; Farach-Colton, M .; Kuszmaul, B. (junio de 2012). "El sistema de archivos de transmisión por secuencias TokuFS" (PDF) . Actas de la 4ª Conferencia de USENIX sobre temas de actualidad en almacenamiento y sistemas de archivos . MA : Asociación USENIX. págs. 14-14.
- ^ 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 optimizado a la derecha" (PDF) . Actas de la 13ª Conferencia de 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. Cite journal requiere
|journal=
( ayuda ) - ^ Armstrong, T .; Ponnekanti, V .; Borthakur, D .; Callaghan, M. (2013). "LinkBench: un punto de referencia de base de datos basado en el gráfico social de Facebook". Actas de la Conferencia Internacional ACM SIGMOD 2013 sobre Gestión de Datos . NY : ACM Press: 1185–1196.