Patent ID: 7783855
Filing Date: 2010-08-24
Classification: G06F,H03M

Abstract:
1. A computer-implemented method, comprising: providing a first index page comprising a first plurality of key entries and a first keymap, said first index page being stored in a volatile memory, said first keymap indicating a sort order of said first plurality of key entries based on key values of said first plurality of key entries, said first keymap comprising respective positions of said key entries of said first plurality of key entries on said first index page, wherein said first plurality of key entries comprises a first key entry, a second key entry, and a third key entry; wherein said key values comprise a first key value, a second key value and a third key value; wherein said first key entry has said first key value, said second key entry has said second key value and said third key entry has said third key value, wherein said first keymap indicates that said second key value is between said first key value and said third key value; wherein said second key entry has a position in said first index page that is not between a position of said first key entry and a position of said third key entry in said first index page; compressing said first plurality of key entries of said first index page in accordance with said sort order indicated by said first keymap of said first index page thereby providing a compressed first plurality of key entries; generating a second keymap indicating said sort order of said first plurality of key entries and also comprising respective post-compression positions of said key entries of said first plurality of key entries; and storing a second index page in a persistent storage, said second index page comprising said compressed first plurality of key entries and said second keymap.