THE AVERAGE HEIGHT OF A NODE IN THE BANG ABSTRACT DIRECTORY TREE

The abstract logical data structure for the BANG file directory is a m ultiway tree structure with one node for each bucket in the file. Unde r assumptions of ''perfect hashing'' or ''growth on data principle'', we model the growth of the tree. The average cost for search and inser tion is found to be logarithmic in the file size. The order constant i s small and depends on the capacity of a bucket. Simulation confirms t he analytic results. Similar assumptions should be applicable to the a nalysis of other multi-dimensional file structures.