Bounded disorder: The effect of the index

AbstractIn this paper we complete the analysis done by Ramakrishna and Mukhopadhyay for a data node in the bounded disorder (BD) file organization of Litwin and Lomet, by introducing the B-tree index into the model. Also, we extend the analysis to the case of BD files with two partial expansions as proposed by Lomet. Our main contribution is a detailed analysis of search and insertion costs, and its comparison with B+-trees