Analysis of grid file algorithms (Q1060565)

Grid file algorithms were suggested by \textit{J. Nievergelt, H. Hinterberger} and \textit{K. C. Sevcik} [ACM Trans. Database Syst. 9, 38-71 (1984)] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions: \(O(v^ c)\) or \(O(v^{\xi})\), where \(c=1+b^{-1}\), \(\xi =1+(s- 1)/(sb+1)\), s is the number of attributes being used, v the file size, and b the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.