Virtual Forced Splitting, Demotion and the BV-Tree

In external multi-dimensional access methods, Forced Splitting is an approach used to ensure that, when a page splits, no sub-tree of the page belongs under both halves, thereby guaranteeing that only one path from the root need be searched to find any point in the tree. This reduces occupancy of forcibly split pages, possibly down to single entries in pathological cases. Freeston introduced a novel approach to obtaining the benefits of forced splitting while avoiding the negative consequences for a class of access methods he called BV-Trees. Perhaps because of its rather abstract presentation and the lack of complete algorithm descriptions, we believe that this idea has not achieved the recognition it deserves. We present a different view of the BV-Tree concept in terms of what we call Virtual Forced Splitting (VFS), show how the semantics of a VFS tree can be understood by its relationship to a much simpler Forced Split tree obtained by reduction from the VFS tree. This allows an explanation of the complex issue of demotion; a requirement for correct implementation that is acknowledged but not discussed in the literature before now. We show how various multi-dimensional algorithms such as k-Nearest Neighbour and Range Search can be effectively implemented on such trees, and, finally, discuss our own implementation of a BV-Tree, and report performance results in comparison to the R*-Tree.