# US 2021/0342323 A1 · Systems and methods for compressing keys in hierarchical data structures

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

- Number: US 2021/0342323 A1
- Document ID: US20210342323A1
- Status: Published application
- Kind: A1
- Application number: 16/863,025
- Filed: 2020-04-30
- Published: 2021-11-04
- Earliest claimed: 2020-04-30
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Sridhar Valaguru
- Web page: https://patentgrep.com/patent/US20210342323A1

## CPC

- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/182: Distributed file systems
- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The present disclosure describes systems and methods for enhancing the space utilization of storing keys in hierarchical data structures, such as B+Tree leaf blocks, by partially or fully compressing the keys. Partially compressing the keys may include storing certain keys as offsets from a start key. Fully compressing the keys may include setting a “type” value included in the header of the leaf block to a value indicating that the keys are implicitly represented by an ordinal key index, which defines the ordinal arrangement of keys in the leaf block. Partially or fully compressing keys, according to the implementations described herein, reduces the amount of space needed to store keys in a leaf block of a B+Tree.

## Claims

### Claim 1

A file system, comprising:
one or more processors; and
a non-transitory computer-readable storage medium containing instructions which, when executed on the one or more processors, cause the one or more processors to perform operations including:
accessing a set of keys, each key of the set of keys being associated with a pointer to one or more data blocks of a block-oriented storage device, the set of keys being arranged according to an ordinal key index, and the set of keys including a start key being first from amongst the set of keys;
defining a hierarchical data structure configured to store the set of keys, the hierarchical data structure including a leaf block, and the leaf block being configured to store a subset of the set of keys according to the ordinal key index;
determining whether the subset of the set of keys is contiguous;
in response to determining that the subset of the set of keys is contiguous, compressing the subset of the set of keys; and
storing the compressed subset of the set of keys in the leaf block.

### Claim 2 (depends on 1)

The file system of claim 1, wherein the operation of compressing the subset of the set of keys further comprises:
comparing the start key with each subsequent key of the subset of the set of keys; and
determining, based on the comparison, an offset for each subsequent key of the subset of the set of keys, the offset representing a difference between the start key and the subsequent key.

### Claim 3 (depends on 2)

The file system of claim 2, wherein the operation of compressing the subset of the set of keys further comprises:
storing the start key in full in the leaf block; and
storing, in the leaf block, the offset for each subsequent key of the subset of the set of keys, the offset for each subsequent key being stored in the leaf block according to the ordinal key index.

### Claim 4 (depends on 2)

The file system of claim 2, wherein the operation of compressing the subset of the set of keys further comprises:
determining that the offset for each subsequent key of the subset of the set of keys has a same size;
in response to determining that the offsets for the subset of the set of keys are the same size, performing an additional compression of the subset of the set of keys by setting a value for a block type variable included in a header of the leaf block, the value indicating that the offset for each subsequent key of the subset of the set of keys matches the ordinal key index; and
storing the start key in full in the leaf block without storing the subsequent keys or the offsets of the subsequent keys.

### Claim 5 (depends on 4)

The file system of claim 4, wherein each subsequent key after the start key in the subset of the set of keys is implicitly represented by the ordinal key index.

### Claim 6 (depends on 1)

The file system of claim 1, wherein the operations further comprise:
in response to determining that the subset of the set of keys are not contiguous, storing the subset of the set of keys in a new data structure including a set of records, the subset of the set of keys being contiguous in the new data structure, and each record of the set of records of the new data structure including a key after the start key of the subset of the set of keys and the associated offset of the key; and
compressing the subset of the set of keys using the ordinal key index.

### Claim 7 (depends on 1)

The file system of claim 1, wherein the hierarchical data structure is a B+Tree, wherein each key of the subset of the set of keys represents a file offset of a file, and wherein the B+Tree is used to store a file layout tree representing the file.

### Claim 8

A computer-implemented method comprising:
accessing a set of keys, each key of the set of keys being associated with a pointer to one or more data blocks of a block-oriented storage device, the set of keys being arranged according to an ordinal key index, and the set of keys including a start key being first from amongst the set of keys;
defining a hierarchical data structure configured to store the set of keys, the hierarchical data structure including a leaf block, and the leaf block being configured to store a subset of the set of keys according to the ordinal key index;
determining whether the subset of the set of keys is contiguous;
in response to determining that the subset of the set of keys is contiguous, compressing the subset of the set of keys; and
storing the compressed subset of the set of keys in the leaf block.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein compressing the subset of the set of keys further comprises:
comparing the start key with each subsequent key of the subset of the set of keys; and
determining, based on the comparison, an offset for each subsequent key of the subset of the set of keys, the offset representing a difference between the start key and the subsequent key.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein compressing the subset of the set of keys further comprises:
storing the start key in full in the leaf block; and
storing, in the leaf block, the offset for each subsequent key of the subset of the set of keys, the offset for each subsequent key being stored in the leaf block according to the ordinal key index.

### Claim 11 (depends on 9)

The computer-implemented method of claim 9, wherein compressing the subset of the set of keys further comprises:
determining that the offset for each subsequent key of the subset of the set of keys has a same size;
in response to determining that the offsets for the subset of the set of keys are the same size, performing an additional compression of the subset of the set of keys by setting a value for a block type variable included in a header of the leaf block, the value indicating that the offset for each subsequent key of the subset of the set of keys matches the ordinal key index; and
storing the start key in full in the leaf block without storing the subsequent keys or the offsets of the subsequent keys.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11, wherein each subsequent key after the start key in the subset of the set of keys is implicitly represented by the ordinal key index.

### Claim 13 (depends on 8)

The computer-implemented method of claim 8, further comprising:
in response to determining that the subset of the set of keys are not contiguous, storing the subset of the set of keys in a new data structure including a set of records, the set of keys being contiguous in the new data structure, and each record of the set of records of the new data structure including a key after the start key of the subset of the set of keys and the associated offset of the key; and
compressing the subset of the set of keys using the ordinal key index.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, wherein the hierarchical data structure is a B+Tree, wherein each key of the subset of the set of keys represents a file offset of a file, and wherein the B+Tree is used to store a file layout tree representing the file.

### Claim 15

A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a processing apparatus to perform operations including:
accessing a set of keys, each key of the set of keys being associated with a pointer to one or more data blocks of a block-oriented storage device, the set of keys being arranged according to an ordinal key index, and the set of keys including a start key being first from amongst the set of keys;
defining a hierarchical data structure configured to store the set of keys, the hierarchical data structure including a leaf block, and the leaf block being configured to store a subset of the set of keys according to the ordinal key index;
determining whether the subset of the set of keys is contiguous;
in response to determining that the subset of the set of keys is contiguous, compressing the subset of the set of keys; and
storing the compressed subset of the set of keys in the leaf block.

### Claim 16 (depends on 15)

The non-transitory machine-readable storage medium of claim 15, wherein the operation of compressing the subset of the set of keys further comprises:
comparing the start key with each subsequent key of the subset of the set of keys; and
determining, based on the comparison, an offset for each subsequent key of the subset of the set of keys, the offset representing a difference between the start key and the subsequent key.

### Claim 17 (depends on 16)

The non-transitory machine-readable storage medium of claim 16, wherein the operation of compressing the subset of the set of keys further comprises:
storing the start key in full in the leaf block; and
storing, in the leaf block, the offset for each subsequent key of the subset of the set of keys, the offset for each subsequent key being stored in the leaf block according to the ordinal key index.

### Claim 18 (depends on 16)

The non-transitory machine-readable storage medium of claim 16, wherein the operation of compressing the subset of the set of keys further comprises:
determining that the offset for each subsequent key of the subset of the set of keys has a same size;
in response to determining that the offsets for the subset of the set of keys are the same size, performing an additional compression of the subset of the set of keys by setting a value for a block type variable included in a header of the leaf block, the value indicating that the offset for each subsequent key of the subset of the set of keys matches the ordinal key index; and
storing the start key in full in the leaf block without storing the subsequent keys or the offsets of the subsequent keys.

### Claim 19 (depends on 18)

The non-transitory machine-readable storage medium of claim 18, wherein each subsequent key after the start key in the subset of the set of keys is implicitly represented by the ordinal key index.

### Claim 20 (depends on 15)

The non-transitory machine-readable storage medium of claim 15, wherein the operations further comprise:
in response to determining that the subset of the set of keys are not contiguous, storing the subset of the set of keys in a new data structure including a set of records, the subset of the set of keys being contiguous in the new data structure, and each record of the set of records of the new data structure including a key after the start key of the subset of the set of keys and the associated offset of the key; and
compressing the subset of the set of keys using the ordinal key index.
