Fractal tree index

The search time of a B-tree is asymptotically the same as that of a fractal tree index. However, a fractal tree index has deeper trees than a B-tree, and if each node were to require an I/O, say if the cache is cold, then a fractal tree index would induce more IO. However, for many workloads most or all internal nodes of both B-trees and fractal tree indexes are already cached in RAM. In this case, the cost of a search is dominated by the cost of fetching the leaf, which is the same in both cases. Thus, for many workloads, fractal tree indexes can match B-trees in terms of search time.

Where they differ is on insertions, deletions and updates. An insertion in a fractal tree index takes ${\displaystyle O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)}$ whereas B-trees require ${\displaystyle O(\log _{B}N)}$. Thus, fractal tree indexes are faster than B-trees by a factor of ${\displaystyle O({\sqrt {B}})}$. Since ${\displaystyle B}$ can be quite large, this yields a potential two-order-of-magnitude improvement in worst-case insertion times, which is observed in practice. Both B-trees and fractal tree indexes can perform insertions faster in the best case. For example, if keys are inserted in sequential order, both data structures achieve a ${\displaystyle O\left({\frac {1}{B}}\right)}$ I/Os per insertion. Thus, because the best and worst cases of B-trees differ so widely, whereas fractal tree indexes are always near their best case, the actual speedup that fractal tree indexes achieve over B-trees depends on the details of the workload.

Log-structured merge-trees (LSMs) refer to a class of data structures which consists of two or more index structures of exponentially growing capacities. When a tree at some level reaches its capacity, it is merged into the next bigger level. The IO-complexity of an LSM depends on parameters such as the growth factor between levels and the data structure chosen at each level, so in order to analyze the complexity of LSMs, we need to pick a specific version. For comparison purposes, we select the version of LSMs that match fractal tree indexes on insertion performance.

Suppose an LSM is implemented via ${\displaystyle O(\log _{B}N)}$ B-trees, each of which has a capacity that is ${\displaystyle {\sqrt {B}}}$ larger than its predecessor. The merge time depends on three facts: The sorted order of keys in an ${\displaystyle N}$-item B-tree can be produced in ${\displaystyle O\left({\frac {N}{B}}\right)}$ IOs; Two sorted lists of ${\displaystyle N}$ and ${\displaystyle M}$ items can be merged into a sorted list in ${\displaystyle O\left({\frac {N+M}{B}}\right)}$ IOs; and a B-tree of a sorted list of ${\displaystyle N}$ items can be built in ${\displaystyle O\left({\frac {N}{B}}\right)}$ IOs. When a tree overflows, it is merged into a tree whose size is ${\displaystyle O({\sqrt {B}})}$ larger, therefore a level that holds ${\displaystyle k}$ items requires ${\displaystyle O\left({\frac {k}{\sqrt {B}}}\right)}$ IOs to merge. An item may be merged once per level, giving a total time of ${\displaystyle O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)}$, which matches the fractal tree index.

The query time is simply the B-tree query time at each level. The query time into the ${\displaystyle i}$^th level is ${\displaystyle O(\log _{B}B^{\frac {i}{2}})=O(i)}$, since the ${\displaystyle i}$^th level has capacity ${\displaystyle B^{\frac {i}{2}}}$. The total time is therefore ${\displaystyle O(\log _{B}^{2}N)}$. This is larger than both the B-tree and fractal tree indexes by a logarithmic factor. In fact, although B-trees and fractal tree indexes are both on the optimal tradeoff curve between insertions and queries, LSMs are not. They are incomparable with B-trees and are dominated by fractal tree indexes.

A few notes about LSMs: there are ways to make the queries faster. For example, if only membership queries are required and no successor/predecessor/range queries are, then Bloom filters can be used to speed up queries. Also, the growth factor between levels can be set to some other value, giving a range of insertion/query tradeoffs. However, for every choice of insertion rate, the corresponding fractal tree index has faster queries.

The fractal tree index is a refinement of the B^ε tree. Like a B^ε tree, it consists of nodes with keys and buffers and realizes the optimal insertion/query tradeoff. The fractal tree index differs in including performance optimization and in extending the functionality. Examples of improved functionality include ACID semantics. B-tree implementations of ACID semantics typically involve locking rows that are involved in an active transactions. Such a scheme works well in a B-tree because both insertions and queries involve fetching the same leaf into memory. Thus, locking an inserted row does not incur an IO penalty. However, in fractal tree indexes, insertions are messages, and a row may reside in more than one node at the same time. Fractal tree indexes therefore require a separate locking structure that is IO-efficient or resides in memory in order to implement the locking involved in implementing ACID semantics.

Fractal tree indexes also have several performance optimizations. First, buffers are themselves indexed in order to speed up searches. Second, leaves are much larger than in B-trees, which allows for greater compression. In fact, the leaves are chosen to be large enough that their access time is dominated by the bandwidth time, and therefore amortizes away the seek and rotational latency. Large leaves are an advantage with large range queries but slow down point queries, which require accessing a small portion of the leaf. The solution implemented in fractal tree indexes is to have large leaves that can be fetched as a whole for fast range queries but are broken into smaller pieces call basement nodes which can be fetched individually. Accessing a basement node is faster than accessing a leaf, because of the reduced bandwidth time. Thus the substructure of leaves in fractal tree indexes, as compared to B^ε trees allows both range and point queries to be fast.

An upsert is a statement that inserts a row if it does not exist and updates it if it does. In a B-tree, an upsert is implemented by first searching for the row and then implementing an insertion or an update, depending on the result of the search. This requires fetching the row into memory if it is not already cached. A fractal tree index can implement an upsert by inserting a special upsert message. Such a message can, in theory, implement arbitrary pieces of code during the update. In practice, four update operations are supported:

1. x = constant
2. x = x + constant (a generalized increment)
3. x = x − constant (a generalized decrement)
4. x = if (x=0, 0, x-1) (a decrement with a floor at 0)

These correspond to the update operations used in LinkBench,[8] a benchmark proposed by Facebook. By avoiding the initial search, upsert messages can improve the speed of upserts by orders of magnitude.

So far, all message types have modified single rows. However, broadcast messages, which are copied to all outgoing buffers, can modify all rows in a database. For example, broadcast messages can be used to change the format of all rows in a database. Although the total work required to change all rows is unchanged over the brute-force method of traversing the table, the latency is improved, since, once the message is injected into the root buffer, all subsequent queries will be able to apply the schema modification to any rows they encounter. The schema change is immediate and the work is deferred to such a time when buffers overflow and leaves would have gotten updated anyway.