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 que son asintóticamente más rápidas que un árbol B. Al igual que un árbol B, un índice de árbol fractal es una generalización de un árbol de búsqueda binario en el sentido de que un nodo puede tener más de dos hijos. Además, a diferencia de un árbol B, un índice de árbol fractal tiene buffers en cada nodo, que permiten almacenar inserciones, eliminaciones y otros cambios en ubicaciones intermedias. El objetivo de los buffers 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. Al igual que 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 al caché, [1] pero la implementación actual es una extensión del árbol B ε . [2] El B ε está relacionado con el árbol de repositorio almacenado en búfer. [3] El árbol de repositorio almacenado en búfer tiene grado 2, mientras que el árbol B ε tiene grado B ε . El índice del árbol fractal también se ha utilizado en un sistema de archivos prototipo . [4] [5] Está disponible una implementación de código abierto del índice de árbol fractal, [6] que demuestra los detalles de implementación que se describen a continuación.
En los índices de árboles fractales, los nodos internos ( que no son hojas ) 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 se pueden unir o dividir. Cada nodo interno de un árbol B contendrá una cantidad de claves 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 están entre los dos valores entre corchetes. En este sentido, son como árboles B.
Tanto los índices de árboles fractales como los árboles B explotan el hecho de que cuando se recupera un nodo del almacenamiento, se recupera un bloque de memoria, cuyo tamaño se indica con . Por lo tanto, los nodos se ajustan para que tengan 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 la cantidad 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 debe ser suficiente para llenar el nodo, con cierta variabilidad para las divisiones y fusiones de nodos. Para fines de análisis teórico, si las claves caben 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 los árboles fractales utilizan un factor de ramificación más pequeño, digamos, de . La profundidad del árbol es entonces , por lo que coincide asintóticamente con el árbol B. El espacio restante en cada nodo se utiliza para almacenar en búfer inserciones, eliminaciones y actualizaciones, a las que nos referimos en conjunto como mensajes. Cuando un búfer está lleno, se envía a los niños de forma masiva. Hay varias opciones sobre cómo se vacían los buffers, y todas conducen a una complejidad de E/S similar. Cada mensaje en un búfer de nodo se enviará a un hijo en particular, según lo determine su clave. Supongamos, para ser más concretos, que se descartan los mensajes que se dirigen al mismo niño y que, entre los niños, elegimos el que tiene más mensajes. Entonces hay al menos mensajes que se pueden transmitir 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 descarga varias veces y el costo de una descarga es . Por tanto, el coste 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 fluido entre el costo de búsqueda, que depende de la profundidad del árbol de búsqueda y, por lo tanto, del factor de ramificación, versus el tiempo de inserción, que depende de la profundidad del árbol pero más sensiblemente del tamaño de los lavados del búfer.
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 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.
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 el caché está frío, 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 índices de árboles B y árboles fractales ya están almacenados en caché en la RAM. En este caso, el coste de una búsqueda está dominado por el coste de buscar la hoja, que es el mismo en ambos casos. Por lo tanto, para muchas cargas de trabajo, los índices de los árboles fractales pueden coincidir con los árboles B en términos de tiempo de búsqueda.
Donde difieren es en las inserciones, eliminaciones y actualizaciones. Una inserción en el índice de un árbol fractal requiere, mientras que los árboles B requieren . Por lo tanto, los índices de los árboles fractales son más rápidos que los árboles B por un factor de . Dado que 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 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 E/S por inserción. Por lo tanto, debido a que los mejores y peores casos de los árboles B difieren ampliamente, mientras que los índices de los árboles fractales siempre están cerca de su mejor caso, la aceleración real que los índices de los árboles fractales logran con respecto a los árboles B depende de los detalles de la carga de trabajo.
Los árboles de fusión con estructura logarítmica (LSM) se refieren a una clase de estructuras de datos que consta de dos o más estructuras de índice de capacidades en crecimiento exponencial. Cuando un árbol en algún nivel alcanza su capacidad, se fusiona con el siguiente nivel más grande. La complejidad de IO 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 cuanto al rendimiento de inserción.
Supongamos que un LSM se implementa mediante árboles B, cada uno de los cuales tiene una capacidad mayor que su predecesor. El tiempo de fusión depende de tres hechos: el orden de las claves en un árbol B de elementos se puede producir en IO; Se pueden combinar dos listas ordenadas de elementos y en una lista ordenada en IO; y se puede construir un árbol B de una lista ordenada de elementos en IO. Cuando un árbol se desborda, se fusiona en un árbol cuyo tamaño es mayor; por lo tanto, un nivel que contiene elementos requiere IO para fusionarse. Un elemento se puede fusionar una vez por nivel, dando 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 al décimo nivel es , ya que el décimo nivel tiene capacidad . Por tanto, el tiempo total es . Esto es mayor que los índices del árbol B y del árbol fractal en un factor logarítmico. De hecho, aunque los índices de árboles B y árboles fractales se encuentran en la curva de compensación óptima entre inserciones y consultas, los LSM no. Son incomparables con los árboles B y están dominados por índices de árboles fractales.
Algunas notas sobre los LSM: hay formas de acelerar las consultas. Por ejemplo, si solo se requieren consultas de membresía y no hay consultas de sucesor/predecesor/rango, entonces se pueden usar filtros Bloom para acelerar las consultas. Además, el factor de crecimiento entre niveles se puede establecer en algún otro valor, lo que ofrece una variedad 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.
El índice del árbol fractal es un refinamiento del árbol B ε . Como un árbol B ε , consta de nodos con claves y buffers y logra el equilibrio óptimo entre inserción y consulta. El índice del árbol fractal se diferencia en incluir la optimización del rendimiento y en ampliar la funcionalidad. Ejemplos de funcionalidad mejorada incluyen la semántica ACID . Las implementaciones de árbol B de la semántica ACID generalmente implican bloquear filas que participan 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 árboles fractales 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 propios buffers están indexados para acelerar las búsquedas. En segundo lugar, las hojas son mucho más grandes que las de 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 gran alcance, 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 recuperar en su conjunto para consultas de rango rápido, pero que se dividen en partes más pequeñas llamadas nodos de sótano que se pueden recuperar individualmente. Acceder a un nodo 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 los árboles fractales, en comparación con los árboles B ε , permite que las consultas tanto de rango como de puntos sean rápidas.
Las inserciones, eliminaciones y actualizaciones se insertan como mensajes en buffers que se dirigen hacia las hojas. La infraestructura de mensajería se puede aprovechar para implementar una variedad de otras operaciones, algunas de las cuales se analizan a continuación.
Un upsert es una declaración que inserta una fila si no existe y la actualiza si existe. En un árbol B, una inserción se implementa buscando primero la fila y luego implementando una inserción o una actualización, según el 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 una inserción insertando un mensaje de inserción especial. Un mensaje de este tipo 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:
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 los upserts en órdenes de magnitud.
Hasta ahora, todos los tipos de mensajes han modificado filas individuales. Sin embargo, los mensajes de difusión, que se copian en todos los buffers 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 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 difiere hasta el momento en que los buffers se desborden y las hojas se habrían actualizado de todos modos.
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 árboles fractales también se han utilizado en prototipos de sistemas de archivos, TokuFS [4] y BetrFS. [5]
