Patent ID: 8996531
Filing Date: 2015-03-31
Classification: G06F

Abstract:
1. The method of using a computer to represent each inverted list record in a database, said inverted list record containing a key and a list of one or more ordered logical or physical pointers associated with said key, the number of said pointers being n, said method comprising: using the computer for subdividing said inverted list into m ordered groups of pointers, each group containing at least one pointer, and m being smaller than or equal to n; representing each said group by a record that includes the key of said inverted list record followed by said group of pointers, said record called a chunk record, the group of pointers within a chunk record being called the value of said chunk record, the pointer with the smallest value in the group being called the lowest pointer, the pointer with the largest value in the group being called the highest pointer, each chunk record being stored in an index structure organized by pages, the term index data record being used to denote any chunk record in the database, and implementing a prefix compression among the multiple index data records by identifying a common prefix part between a current index data record to be compressed and a previous index data record, said common prefix part denotes storage units that are equal in the current index data record and the previous index data record, starting with the first storage unit of the current index data record and the previous index data record; wherein said common prefix part is empty if the index data record to be compressed is a first index data record in the page; and where said prefix compression compresses the current index data record by storing only a length in storage units of the common prefix part, and not storing an actual content of the common prefix part, where said index data record does not use any pointers to address other index data records or any data from the inverted list record said index record represents; where all data from any inverted list record are entirely stored in the index structure and not in any external overflow areas; where the value of said index data record does not include any keys; allowing the sequential read of the pointers in an inverted list through a cursor C with a component C.pos identifying the current chunk record in the ordered list of chunk records, and a component C.cont representing a group of pointers in the form <ps,pe>, where C.cont.ps identifies the lowest pointer and C.cont.pe the highest pointer in the group, C.cont being set when the current chunk record identified by C.pos is read and being derived from the current chunk record by setting C.cont.ps=p and C.cont.pe=ps+delta, where p is the lowest pointer in the group, and delta is the length of the interval of contiguous or sparse pointers, said delta being explicitly stored or estimated, and further characterized by an operation of advancing the cursor to the next pointer wherein: if the current pointer C.cont.ps is not the last pointer in the current chunk record, C.cont.ps is set to the next pointer in the current chunk record, if the current pointer C.cont.ps is the last pointer in the current chunk record, the next chunk record in the inverted list is read, if said chunk record does not exist an end-of-scan condition being returned.