In-place index compression

Abstract

The present invention provides in a data processing system storing a plurality of discrete entities, each identified by a single parameter within a monotonic parameter spectrum, resident at an addressable location and locatable by searching a system maintained hierarchical index mapping parameters onto location addresses, a method of compressing the index by the system, which method is interruptable to permit valid searching of the index and executes in a variable length ordered sequence of processing cycles, each comprising a variable length sequence of two part iterations, each iteration comprising the selective performance of each of an ordered fixed sequence of basic operations, wherein each full cycle initially operates on successive index levels in the direction opposite to that in which the index is searched while performing the first part of each iteration and thereafter operates on successive levels in the reverse direction performing the second part of each iteration, parameter relocation at a level being performed by duplicating a parameter at its target location in a first part of the iteration at that level and deleting the original presence of the parameter in the second part of that iteration.