Patent ID: 11860844
Assignee: PLIOPS LTD.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 22:
23. A device comprising a memory controller and a non-volatile memory unit, the memory controller is configured to manage a log structured merged (LSM) tree of key value (KV) pairs stored in the non-volatile memory unit, the memory controller is configured to manage the LSM tree by:
merging runs of the LSM tree to provide merged runs;
writing merged runs to the non-volatile memory;
adding new runs to the LSM tree, wherein the adding comprises writing runs to the non-volatile memory;
updating at least one management data structure (MDS) to reflect the merging and the adding; wherein an MDS of the at least one MDS stores a mapping between keys of the KV pairs of the LSM tree, fingerprints associated with the KV pairs of the LSM tree, and compressed run identifiers that identify runs of the LSM tree; and
compressing run identifiers, by applying a variable length encoding, to provide the compressed run identifiers; wherein the LSM tree comprises a first layer and a last layer, wherein the first layer is smaller than the last layer; wherein the compressing comprises allocating compressed run identifiers of runs of the last layer that are shorter than compressed run identifiers of runs of the first layer.