Stochastically Balancing Trees for File and Database Systems
Aziz M. Barbar, Anis Ismail · International Journal of Green Computing · 2013
With the constant improvement in data storage technologies, a new generation of indexing mechanisms is to be created to exploit the improvements in disk access speeds that were previously impractical. The self-balancing tree B-Tree, has long been the indexing structure of choice for reducing the amount of disk access at the expense of size of data block to be read or written. A new technique based on a dynamically growing multilevel list structure, which is stochastically balanced rather than self balanced, is discussed and compared to the B-Tree. An analogy between the technique and the structures is established to better compare the computational complexities.