Patent ID: 7647291

Claim:
A system for compression, the system comprising: a memory device that stores a b-tree data structure comprising a plurality of compressed and uncompressed normalized index keys, each normalized index key generated by normalizing a plurality of column values that constitute an index key, the normalized index keys stored in sorted order, with no gaps between the stored normalized index keys, and stores a plurality of slots with no gaps between the stored slots, wherein the memory device stores the plurality of compressed and uncompressed normalized index keys starting after a header and the plurality of normalized index keys grows towards an end of the memory device as additional index keys are added; and, a processor that compresses the stored normalized keys on a memory page by: (a) determining if a first normalized index key in the memory device should be compressed; (b) comparing the first normalized index key with a second normalized index key preceding the first normalized index key in the memory device; (c) generating a common byte length between the first normalized index key and the second normalized index key consisting of a number of bytes in a common prefix between the first normalized index key and the second normalized index key; (d) replacing the first normalized index key in the memory page with the generated common byte length followed by the bytes from the first normalized index key that were not in the common prefix between the first normalized index key and the second normalized index key; (e) shifting the normalized index keys following the first normalized index key to fill any empty memory space resulting from compressing the first normalized index key and updating memory offsets contained in the slots corresponding to the shifted normalized index keys; and (f) updating an indicator in the slot corresponding to the first normalized index key to reflect that the key is now compressed, wherein each slot corresponds to a normalized index key in the memory page and comprises a memory offset of the corresponding key and an indicator indicating if the corresponding normalized index key is compressed, wherein the processor compresses the stored normalized index keys before a memory page split.