Memory Page Indexing Data Structure

A non-transitory machine readable medium having stored thereon instructions for performing a method comprising machine executable code which when executed by at least one machine, causes the at least one machine to:

• provide, by a storage server, a plurality of sorted keys;
• store a first subset of the plurality of sorted keys on a first memory page, wherein the first subset of the plurality of sorted keys include a first bit prefix;
• store a second subset of the plurality of sorted keys on a second memory page, wherein the second subset of the plurality of sorted keys include a second bit prefix that is different than the first bit prefix;
• construct a trie representation that includes a first entry corresponding to the first memory page and a second entry corresponding to the second memory page, wherein a position of the first entry in the trie representation is determined based on a binary value of a bit of the first bit prefix, and wherein a position of the second entry in the representation is determined based on a binary value of a bit of the second bit prefix;
• and
• traverse the trie representation, by the storage server, to access a record stored in the first memory page, wherein the record corresponds to a key having the first bit prefix.

A computing device comprising:

• a memory containing machine readable medium comprising machine executable code having stored thereon instructions for performing a method of data indexing;
• and
• a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
• provide, by a storage server, a plurality of sorted keys;
• store a first subset of the plurality of sorted keys on a first memory page, wherein the first subset of the plurality of sorted keys include a first bit prefix;
• store a second subset of the plurality of sorted keys on a second memory page, wherein the second subset of the plurality of sorted keys include a second bit prefix that is different than the first bit prefix;
• construct a trie representation that includes a first entry corresponding to the first memory page and a second entry corresponding to the second memory page, wherein a position of the first entry in the trie representation is determined based on a binary value of a bit of the first bit prefix, and wherein a position of the second entry in the representation is determined based on a binary value of a bit of the second bit prefix;
• and
• traverse the trie representation, by the storage server, to access a record stored in the first memory page, wherein the record corresponds to a key having the first bit prefix.