Patent ID: 8244969

Claim:
A memory system comprising: a non-volatile memory comprising a plurality of pages, where units of the memory smaller than one of the pages of the memory are not independently writable, and where each of the pages of the memory comprises a respective user-accessible portion; a map configured to associate respective element identifiers of each of a plurality of elements with a respective physical location of the element in the memory, where the respective physical location comprises an address of a respective one of the pages of the memory and a respective offset within the respective page of the memory; a coalescing buffer comprising a plurality of pages, a size of each of the pages of the coalescing buffer being sufficient to contain the respective user-accessible portion of one of the pages of the memory; wherein the memory system is configured to write a first one of the elements to the memory by determining a particular page of the coalescing buffer according to a respective expected write frequency associated with each of the pages of the coalescing buffer, storing the first element in a first portion of the particular one of the pages of the coalescing buffer, copying the particular page of the coalescing buffer to a particular one of the pages of the memory, and updating the map so that the address of the respective page of the respective physical location of the first element is an address of the particular page of the memory, and so that the respective offset of the respective physical location of the first element is according to the first portion of the particular page of the coalescing buffer; and wherein the memory system is further configured, subsequent to the storing of the first element in the particular page of the coalescing buffer and prior to the copying of the particular page of the coalescing buffer to the particular page of the memory, to store a second one of the elements in a second portion of the particular page of the coalescing buffer, the second element different from the first element, the second portion separate from the first portion.