Patent ID: 8185551
Filing Date: 2012-05-22
Classification: G06F

Abstract:
1. A method organizing data in a disk storage system comprising: organizing a plurality of key-value pairs, wherein a total ordering is applied upon the respective keys via placing respective key-value pairs in nodes structured as a tree, wherein the tree comprises at least one leaf node and at least one non-leaf node, wherein the leaf node includes at least one respective key-value pair, and wherein the non-leaf nodes comprise a buffer, a child pointer sequence and at least one pivot key from a pivot key sequence, wherein the leaf node comprises a root of a subtree; wherein the buffer contains space for at least one of: an insert command, a delete command, and a different type of command, wherein the insert command is associated with a particular key-value pair, and the delete command is associated with a particular key, each child pointer from the child pointer sequence identifying a child node comprising a root of a child subtree; wherein, for each child pointer occurring after a primary child pointer in the child pointer sequence, there is a corresponding pivot key ordered before a pivot key associated with any subsequent child pointer occurring in the child pointer sequence, wherein the keys stored in a respective subtree referenced by a child pointer are ordered greater than any pivot key associated with the child pointer or any previous child pointer, wherein the keys stored in the subtree are ordered less than or equal to the pivot key associated with any subsequent child pointer; wherein a first non-leaf node of the tree includes a first pivot key associated with a child pointer referencing a root of a first subtree, a second pivot key associated with a child pointer referencing a root of a second subtree and a first buffer, where the first pivot key is ordered in the first non-leaf node before the second pivot key according to the pivot key sequence; wherein the root of the first subtree includes a third pivot key and a second buffer, wherein the pivot key sequence orders the third pivot key between the first pivot key and the second pivot key; wherein the first subtree includes a first leaf node for storing at least one key-value pair having a key corresponding to a position in the pivot key sequence occurring between the first pivot key and the third pivot key and a second leaf node for storing at least one key-value pair having a key corresponding to a position in the pivot key sequence occurring between the third pivot key and the second pivot key; wherein the first buffer includes an insert command identifying the key and a value of a first key-value pair currently in the first leaf node; wherein the second buffer includes a delete command identifying the key of the first key-value pair; upon detecting the first buffer has reached a threshold capacity, pushing the insert command from the first buffer to the second buffer of the first subtree; and upon detecting the insert command in the second buffer, removing the delete command from the second buffer based on the insert command being newer than the delete command.