Disk-Resident Streaming Dictionary
First Claim
1. A method organizing data in a disk storage system comprising:
- organizing as key-value pairs in which the keys comprise one or more bits of data and the values comprise zero or more bits of data, and where there exists a total ordering on the keys;
placing the key-value pairs in nodes structured as a tree, where the tree comprises leaf nodes and non-leaf nodes, and where leaf nodes comprise a set of key-value pairs, and where non-leaf nodes, each of which is the root of a subtree, comprise a buffer, a sequence of least one child pointer, and pivot keys,where the buffer contains space for one or more commands, and contains zero or more commands, where a command comprises an insert command, or a delete command, or possibly other commands, where an insert command comprises a key-value pair, and a delete command comprises a key,and each child pointer comprises information that identifies a child node which is the root of a child subtree, and the pivot keys are a sequence of zero or more keys;
where for each child pointer, except for the first child pointer of the sequence of child pointers, there is a corresponding pivot key and in which the pivot key associated with a child pointer is ordered before the pivot key associated with any subsequent child pointer, and in which the keys stored in a subtree referenced by a child pointer are ordered greater than any pivot key associated with the child pointer or any previous child pointer, and the keys stored in the subtree are ordered less than or equal to the pivot key associated with any subsequent child pointer.
4 Assignments
0 Petitions
Accused Products
Abstract
A method, apparatus and computer program product for storing data in a disk storage system is presented. A dictionary data structure is defined and stored on the disk storage system. Key-value pairs can be inserted and deleted into the dictionary data structure, with full transactional semantics, at a rate that is faster than one insertion per disk-head movement. Keys can be looked up with only a logarithmic number of transfers, even for keys that have been recently inserted or deleted. Queries can be performed on ranges of key-value pairs, including recently inserted or deleted pairs, at a constant fraction of the bandwidth of the disk. The dictionary employs indirect logging for physical block logging.
55 Citations
36 Claims
-
1. A method organizing data in a disk storage system comprising:
-
organizing as key-value pairs in which the keys comprise one or more bits of data and the values comprise zero or more bits of data, and where there exists a total ordering on the keys;
placing the key-value pairs in nodes structured as a tree, where the tree comprises leaf nodes and non-leaf nodes, and where leaf nodes comprise a set of key-value pairs, and where non-leaf nodes, each of which is the root of a subtree, comprise a buffer, a sequence of least one child pointer, and pivot keys,where the buffer contains space for one or more commands, and contains zero or more commands, where a command comprises an insert command, or a delete command, or possibly other commands, where an insert command comprises a key-value pair, and a delete command comprises a key, and each child pointer comprises information that identifies a child node which is the root of a child subtree, and the pivot keys are a sequence of zero or more keys; where for each child pointer, except for the first child pointer of the sequence of child pointers, there is a corresponding pivot key and in which the pivot key associated with a child pointer is ordered before the pivot key associated with any subsequent child pointer, and in which the keys stored in a subtree referenced by a child pointer are ordered greater than any pivot key associated with the child pointer or any previous child pointer, and the keys stored in the subtree are ordered less than or equal to the pivot key associated with any subsequent child pointer. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer readable medium having computer readable code thereon for organizing data in a disk storage system comprising instructions for:
-
organizing as key-value pairs in which the keys comprise one or more bits of data and the values comprise zero or more bits of data, and where there exists a total ordering on the keys;
placing the key-value pairs in nodes structured as a tree, where the tree comprises leaf nodes and non-leaf nodes, and where leaf nodes comprise a set of key-value pairs, and where non-leaf nodes, each of which is the root of a subtree, comprise a buffer, a sequence of least one-child pointer, and pivot keys,where the buffer contains space for one or more commands, and contains zero or more commands, where a command comprises an insert command, or a delete command, or possibly other commands, where an insert command comprises a key-value pair, and a delete command comprises a key, and each child pointer comprises information that identifies a child node which is the root of a child subtree, and the pivot keys are a sequence of zero or more keys; where for each child pointer, except for the first child pointer of the sequence of child pointers, there is a corresponding pivot key and in which the pivot key associated with a child pointer is ordered before the pivot key associated with any subsequent child pointer, and in which the keys stored in a subtree referenced by a child pointer are ordered greater than any pivot key associated with the child pointer or any previous child pointer, and the keys stored in the subtree are ordered less than or equal to the pivot key associated with any subsequent child pointer. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A computer system comprising a processor;
- a main memory;
a disk; and
wherein the memory is encoded with an application for storing data on the disk, that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of organizing data in a disk storage system comprising;organizing as key-value pairs in which the keys comprise one or more bits of data and the values comprise zero or more bits of data, and where there exists a total ordering on the keys;
placing the key-value pairs in nodes structured as a tree, where the tree comprises leaf nodes and non-leaf nodes, and where leaf nodes comprise a set of key-value pairs, and where non-leaf nodes, each of which is the root of a subtree, comprise a buffer, a sequence of least one child pointer, and pivot keys,where the buffer contains space for one or more commands, and contains zero or more commands, where a command comprises an insert command, or a delete command, or possibly other commands, where an insert command comprises a key-value pair, and a delete command comprises a key, and each child pointer comprises information that identifies a child node which is the root of a child subtree, and the pivot keys are a sequence of zero or more keys; where for each child pointer, except for the first child pointer of the sequence of child pointers, there is a corresponding pivot key and in which the pivot key associated with a child pointer is ordered before the pivot key associated with any subsequent child pointer, and in which the keys stored in a subtree referenced by a child pointer are ordered greater than any pivot key associated with the child pointer or any previous child pointer, and the keys stored in the subtree are ordered less than or equal to the pivot key associated with any subsequent child pointer. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
- a main memory;
Specification