A class of hybrid list file organizations

摘要

A new class of hybrid list organizations is proposed in this paper. A hybrid list organization of length parameter Lth is to store a key list as an inverted list or as a multilist depending on whether the list length is larger than Lth or not. By varying the value of Lth one obtains a spectrum of list structures. The pure inverted list and pure multilist organizations are included in the class as degenerate cases. Efficiencies of file organizations in a particular data base system are dependent upon the data base characteristics. Evaluations through analysis and simulation show that, for some realistic data base systems, there exist non-degenerate hybrid list organizations which are indeed superior in performance.