| dc.description.abstract | A wide range of R-tree variants exists that competes to give the best performance for different uses. This has gone on since the original R-tree was published in 1984. A new wave of variants appeared to take advantage of new hardware such as SSDs, which has noticeable differences to HDDs.
The B+-tree, an even older structure, has also had several different papers with goals to increase its performance. One of the newer ones (2015) describes the Bloomtree, which is a B+-tree that makes use of three different leaf types. One of them utilises bloomfilters to reduce reads, hence the name. Unlike other B+-tree variants that trades writes for reads to fit the characteristics of an SSD, this Bloomtree reports a decrease in both reads and writes. This would indisputably increase performance, given the structure doesn t have any special needs such as extreme CPU usage.
Given the performance increase the Bloomtree yields, it s interesting to see if its concepts can be applied to an R-tree. R-trees have strong similarities to B+-trees, and is in some ways just an n-dimensional B+-tree. Therefore, given its resemblance, it seems like a plausible task.
During the paper, only some parts of the Bloomtree was successfully applied to an R-tree. There was unfortunately not found a suited replacement for the most interesting leaf node, the one which uses bloomfilters. Without that node, it essentially then became an R-tree with overflow blocks. The B + has one such overflow structure, which performed poorly. Therefore no particular performance gain was expected, other than that it should perform better than it s overflow B+-tree equivalent. Simulations done in this paper showed that overflow with the overflow linear R-tree did perform better than it s B+-tree equivalent, and could actually rival the performance of the plain linear R-tree. | |
