Disk-Resident Streaming Dictionary

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.

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.