DATA MANAGEMENT SYSTEM EMPLOYING A HASH-BASED AND TREE-BASED KEY-VALUE DATA STRUCTURE

摘要

Disclosed is a data management system configured to provide a key-value data structure architecture for use with a storage device. The key-value data structure includes a logic tree having a tree-based index and a hash table having a hash-based index. For a 'scan' (or range query) operation, the data management system scans the tree-based index to determine which keys exist between two search keys in the tree-based index. For a 'get' (e.g., a value request) operation, the data management system applies a hash function to a provided key to determine an index in the hash table by which to retrieve a value that corresponds with the provided key. Other operations (e.g., 'put', 'update', 'delete') may include updating both the tree-based index and the hash-based index. The logic tree stores keys and stores a zero byte-sized value with each of the keys, to limit the size of the logic tree.