Method and data structure for a low memory overhead database and apparatus for implementing the same. Under one embodiment, the data structure includes an index table for storing a plurality of entries, each of the entries corresponding to one of a plurality of hash values, with each entry including a section pointer to identify a memory address of one of a plurality of sections of a key database and including valid bits to indicate a size of the respective section of the key database. The key database is stores a plurality of data entries, with each data entry including a search key having one of the plurality of hash values, and wherein the data entries are grouped into the plurality of sections, with each section storing data entries with search keys having the same hash value.