Data replication for external searching in static tree structures
Susanne E. Hambrusch, Chuan-Ming Liu · 2000
This paper explores the use of data replication to improve external searc hing in static tree structures.We present general and eÆcient mappings from the nodes of a tree T to blocks of size B when nodes of T can be replicated.The amount of replication is controlled and block utilization and blocknumber are optimized.We consider total node replication (measuring the total space used) and individual node replication (measuring the replication of indivdual nodes).For an arbitrary tree T of size N and heigh th, w e show that by using at most 3 2 N space one can achiev ea b l o c knumber proportional to the optimal blocknumberofdh=Be.We sho w that when every node can be replicated only a constan tnumber of times, no signi cant reduction in the blocknumber may b e possible.Our w orkalso shows that generating mappings in which all but one block c o n tain exactly B nodes increases the blocknumberby a t m o s t 2 .