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:
“On pragmatistic principles, if the hypothesis of God works satisfactorily in the widest sense of the word, it is true.”
—William James (1842–1910)