Memory Optimization System for Inverted Indexes

A system comprising:

• a memory;
• and
• at least one processor coupled to the memory and configured to:
• determine a value identifier corresponding to a value to be searched for in a database based on a query;
• retrieve, from a lookup table;
• a prefix of an offset corresponding to a location in a posting list that identifies one or more row locations where the value is found in the database;
• retrieve, from a directory page, a suffix of the offset corresponding to the location;
• generate the offset based on the prefix and the suffix;
• retrieve, from the posting list, one or more row positions corresponding to the generated offset;
• and
• return the one or more retrieved row positions responsive to the query.

A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, cause the at least one computing device to perform operations comprising:

• determining a value identifier corresponding to a value to be searched for in a database based on a query;
• retrieving, from a lookup table, a prefix of an offset corresponding to a location in a posting list that identifies one or more row locations where the value is found in the database;
• retrieving;
• from a directory page;
• a suffix of the offset corresponding to the location;
• generating the offset based on the prefix and the suffix;
• retrieving, from the posting list, one or more row identifiers corresponding to the generated offset;
• and
• returning the one or more retrieved row identifiers responsive to the query.