# US 2008/0307181 A1 · Disk-Resident Streaming Dictionary

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0307181 A1
- Document ID: US20080307181A1
- Status: Published application
- Kind: A1
- Application number: 11/760,379
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Assignees: Massachusetts Institute of Technology; Rutgers University; The Research Foundation of State University of NY
- Inventors: Bradley C. Kuszmaul; Michael A. Bender; Martin Farach-Colton
- Web page: https://patentgrep.com/patent/US20080307181A1

## CPC

- G06F 11/1471: involving logging of persistent data for recovery
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2272: {Management thereof}
- G06F 2201/82: Solving problems relating to consistency
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### 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.

### Claim 2 (depends on 1)

The method of claim 1 further comprising in which to look up a key in a subtree rooted at a node, the buffer of the node is searched for command a containing the key,
returning the key-value pair of the command if such a command is found and the command is an insert command,
returning an indication that the key is not found if such a command is found and the command is a delete command, f an if no such command is found, then the pivot keys of the node are used to determine an appropriate child node, and the key is then looked up in the subtree rooted at the child node.

### Claim 3 (depends on 2)

The method of claim 2, further comprising in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, then a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 4 (depends on 3)

The method of claim 3 further comprising in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root-node of the subtree.

### Claim 5 (depends on 4)

The method of claim 4 further comprising to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 6 (depends on 5)

The method of claim 5 further comprising in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 7 (depends on 6)

The method of claim 6 further comprising to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.

### Claim 8 (depends on 1)

The method of claim 1, further comprising in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, then a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 9 (depends on 8)

The method of claim 8 further comprising in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root node of the subtree.

### Claim 10 (depends on 9)

The method of claim 9 further comprising to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 11 (depends on 8)

The method of claim 8 further comprising in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 12 (depends on 11)

The method of claim 11 further comprising to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.

### Claim 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.

### Claim 14 (depends on 13)

The computer readable medium of claim 13 further comprising instructions for in which to look up a key in a subtree rooted at a node, the buffer of the node is searched for command a containing the key,
returning the key-value pair of the command if such a command is found and the command is an insert command,
returning an indication that the key is not found if such a command is found and the command is a delete command, f and if no such command if found, then the pivot keys of the node are used to determine an appropriate child node, and the key is then looked up in the subtree rooted at the child node.

### Claim 15 (depends on 14)

The computer readable medium of claim 14, further comprising instructions for in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, then a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 16 (depends on 15)

The computer readable medium of claim 15 further comprising instructions for in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root node of the subtree.

### Claim 17 (depends on 16)

The computer readable medium of claim 16 further comprising instructions for to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 18 (depends on 17)

The computer readable medium of claim 17 further comprising instructions for in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 19 (depends on 18)

The computer readable medium of claim 18 further comprising instructions for to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.

### Claim 20 (depends on 13)

The computer readable medium of claim 13, further comprising instructions for in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, than a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 21 (depends on 20)

The computer readable medium of claim 20 further comprising instructions for in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root node of the subtree.

### Claim 22 (depends on 21)

The computer readable medium of claim 21 further comprising instructions for to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 23 (depends on 20)

The computer readable medium of claim 20 further comprising instructions for in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 24 (depends on 23)

The computer readable medium of claim 23 further comprising instructions for to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.

### Claim 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.

### Claim 26 (depends on 25)

The computer system of claim 25 further comprising in which to look up a key in a subtree rooted at a node, the buffer of the node is searched for a command a containing the key, returning the key-value pair of the command if such a command is found and the command is an insert command,
returning an indication that the key is not found if such a command is found and the command is a delete command, f and if no such command is found, then the pivot keys of the node are used to determine an appropriate child node, and the key is then looked up in the subtree rooted at the child node.

### Claim 27 (depends on 26)

The computer system of claim 26, further comprising in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, then a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 28 (depends on 27)

The computer system of claim 27 further comprising in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root node of the subtree.

### Claim 29 (depends on 28)

The computer system of claim 28 further comprising to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 30 (depends on 29)

The computer system of claim 29 further comprising in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 31 (depends on 30)

The computer system of claim 30 further comprising to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.

### Claim 32 (depends on 25)

The computer system of claim 25, further comprising in which upon inserting a command into the buffer of the root node of a subtree, if the buffer overflows, then a child node which is the root of a child subtree is chosen, and some commands are pushed from the buffer of the root of the subtree into the child subtree, removing the commands from the buffer of the root of the subtree,
where to push a command into a non-leaf node inserts the command into the buffer of the node.

### Claim 33 (depends on 32)

The computer system of claim 32 further comprising in which to insert a key-value pair into a subtree, a command to insert the key-value pair is pushed into the root node of the subtree.

### Claim 34 (depends on 33)

The computer system of claim 33 further comprising to push an insert command into a leaf node, the corresponding key-value pair is inserted into the set of key-value pairs of the leaf node, removing any previously extant key-value pairs that have the same key from the set.

### Claim 35 (depends on 32)

The computer system of claim 32 further comprising in which to delete a key-value pair from a subtree, a delete command identifying the key is pushed into the root node of the subtree.

### Claim 36 (depends on 35)

The computer system of claim 35 further comprising to push a delete command into a leaf node, any key-value pair with a matching key is removed from the set of key-value pairs of the leaf node.
