Indexing documents is accomplished by generating an inverted index for a collection of one or more documents, each document including one or more index terms. The inverted index includes an inverted list for each index term in the collection of documents. One or more inverted lists include a quantity of postings that exceeds a value x, a skip entry after the x.sup.th posting, and one or more additional skip entries thereafter at intervals of every y.sup.th posting. The value x is such that at least a majority of the index terms occur in x documents or fewer, and the value y is not equal to the value x.