WaterfallTree is an algorithm that effectively solves one of the most fundamental problems in the database world – speed degradation in random keys indexing. Since its discovery, the technology is theoretically justified and implemented.
WaterfallTree achieves significant improvement in the speed of indexing by minimizing the number of random write operations. The created algorithm allows tangible increase in the overall speed of data systems, regardless of their size.
From algorithmic point of view WaterfallTree (W-tree) is a natural generalization of B+-tree. In B+-tree the logic operations with records and keys are executed synchronously (one by one). In WaterfallTree operations are executed asynchronously (in groups). Upon receipt of an operation in B+-tree, it sinks down to its relevant leaf. Upon receipt of an operation in W-tree, it stops in the first non-overloaded node.
Logical operations in W-tree are accumulated within the internal nodes, grouped in branches. When a node is overloaded, an appropriate branch is chosen and its adjacent operations are poured down the tree. The operations flow down and are arranged by their keys, and the process subsides with the progress down the tree.
Unlike B-tree, the keys in W-tree can be duplicated. On its way from the root to the leaf certain key may appear more than once. These are the asynchronous operations with certain key – insert, replace, delete etc. Along their way they reach, replace and annihilate each other, until they reach the leaves. In the leaves the operations are cleared to records.
Since all movements in W-tree are massive, this allows the execution of maximum workload for one seek of the external device.
The WaterfallTree technology is naturally susceptible to parallelization. Operations along the tree are poured down independently on the different branches, thus utilizing multicore machines. STSdb 4.0 uses such parallelization in its engine and achieves insane performance.