Method and data structure for a low memory overhead database

A method comprising:

• applying a hash function to a search key to create a hash value;
• accessing an entry in an index table corresponding to the hash value, the corresponding entry of the index table including a valid bit and a section pointer;
• accessing a section of a key database identified by the section pointer based at least in part on the valid bit, the accessed section including a number of data entries;
• and
• comparing the data entries contained in the accessed section with the search key.