Abstract
Directory information trees (DITs) are repositories for information about people and resources, such as names, telephone numbers, e-mail addresses, application preferences, etc. Directory services provide information in DITs to numerous clients or applications. DITs have the following two characteristics. (1) The ratio of interrogations to updates is at least 10 to 1. (2) They contain a huge number of entries, each of which is usually of small size.In the previous implementations, traditional data structures, such as hash tables and B-trees, are used to maintain DITs. Those implementations are efficient for an interrogation regarding a small portion of a DIT. However, while an interrogation regarding a huge subtree is issued, the implementations cost a lot of time, since every access to an entry needs a disk seek. This disadvantage can be much avoided if the allocation of disk storage to entries is taken into consideration during the implementation of DITs.In this thesis, we discuss the storage allocation problems for entries of a DIT. An allocation method, named the grouped depth first order arrangement, is proposed. As compared with the previous implementations, the proposed method much reduces the number of disk seeks needed by any kind of interrogations, with a slightly higher cost for updates. Theoretical analyses and simulations are provided to compare the proposed method with the previous implementations. Under the consideration that the ratio of interrogations to updates is at least 10 to 1, the proposed method much outperforms the previous implementations in both aspects.