How It Works
A fusion tree is essentially a B-tree with branching factor of w1/5 (any small exponent is also possible), which gives it a height of O(logw n). To achieve the desired runtimes for updates and queries, the fusion tree must be able to search a node containing up to w1/5 keys in constant time. This is done by compressing ("sketching") the keys so that all can fit into one machine word, which in turn allows comparisons to be done in parallel. The rest of this article will describe the operation of a static Fusion Tree; that is, only queries are supported.
Read more about this topic: Fusion Tree
Famous quotes containing the word works:
“We have not all had the good fortune to be ladies. We have not all been generals, or poets, or statesmen; but when the toast works down to the babies, we stand on common ground.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)