# US 2026/0064284 A1 · Multilevel index amortization improvement by intermediate level dynamic sizing

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

- Number: US 2026/0064284 A1
- Document ID: US20260064284A1
- Status: Published application
- Kind: A1
- Application number: 18/825,205
- Filed: 2024-09-05
- Published: 2026-03-05
- Earliest claimed: 2024-09-05
- Assignees: Dell Products L.P.
- Applicants: Dell Products L.P.
- Inventors: Amit Zaitman; Uri Shabi; Alexander Shknevsky
- Web page: https://patentgrep.com/patent/US20260064284A1

## CPC

- G06F 3/0616: {in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for improving amortization when hardening index entries across a multilevel hash table. The techniques include, in a first hardening cycle, in response to a first group of index entries filling a bucket at an in-memory hash table level L1, hardening the bucket at L1 to an initial bucket at an intermediate on-drive hash table level L2. The techniques include, in subsequent successive hardening cycles, incrementally increasing the number of buckets at L2 to a final number of buckets according to an arithmetic series, and, in response to a next group of index entries up to a last group of index entries filling the bucket at L1, hardening the bucket at L1 across the incrementally increased number of buckets at L2. The techniques include, in response to the final number of buckets at L2 being filled, hardening the buckets at L2 across buckets at an on-drive hash table level L3.

## Claims

### Claim 1

A method comprising:
in a first hardening cycle, in response to a first group of index entries filling a single bucket data structure (“bucket”) at an in-memory hash table level (“L1”), hardening the single bucket at L1 to a single initial bucket at an intermediate on-drive hash table level (“L2”);
in subsequent successive hardening cycles:
incrementally increasing a number of buckets at L2 to a final number of buckets according to an arithmetic series; and
in response to a next group of index entries up to a last group of index entries filling the single bucket at L1, hardening the single bucket at L1 across the incrementally increased number of buckets at L2; and
in response to the final number of buckets at L2 being filled with index entries, hardening the final number of buckets at L2 across a predetermined number of buckets at an on-drive hash table level (“L3”), the predetermined number of buckets at L3 being greater than the final number of buckets at L2.

### Claim 2 (depends on 1)

The method of claim 1 comprising:
in the first hardening cycle, having hardened the single bucket at L1 to the single initial bucket at L2, deleting or removing the first group of index entries from the single bucket at L1.

### Claim 3 (depends on 2)

The method of claim 2 comprising:
in the subsequent successive hardening cycles, having hardened the single bucket at L1 across the incrementally increased number of buckets at L2, deleting or removing the next group of index entries up to the last group of index entries from the single bucket at L1.

### Claim 4 (depends on 1)

The method of claim 1 comprising:
having hardened the final number of buckets at L2 across the predetermined number of buckets at L3, resetting the number of buckets at L2 to an initial number defined by a single bucket.

### Claim 5 (depends on 1)

The method of claim 1 wherein “|L1|” denotes a size of L1 in terms of a first number of buckets, wherein “|L2|” denotes a size of L2 in terms of the final number of buckets, wherein “|L3|” denotes a size of L3 in terms of the predetermined number of buckets, and wherein the incrementally increasing of the number of buckets at L2 to the final number of buckets according to an arithmetic series includes incrementally increasing the size of L2 to |L2| expressed as:
❘
"\[LeftBracketingBar]"
L
2
❘
"\[RightBracketingBar]"
=
2
⁢
❘
"\[LeftBracketingBar]"
L
1
❘
"\[RightBracketingBar]"
⁢
❘
"\[LeftBracketingBar]"
L
3
❘
"\[RightBracketingBar]"
.

### Claim 6 (depends on 5)

The method of claim 5 wherein “R2” denotes a ratio of |L2| to |L1|, wherein “R3” denotes a ratio of |L3| to |L1|, wherein “B” denotes a fullness threshold for each bucket at L1, L2, and L3 in terms of a predetermined number of index entries, and wherein the method comprises:
determining an amortization for hardening the final number of buckets at L2 across the predetermined number of buckets at L3,
wherein the amortization is expressed as:
Amortization
⁢
=
2
⁢
R
2
*
B
R
2
2
+
R
2
+
2
⁢
R
3
.

### Claim 7 (depends on 6)

The method of claim 6 wherein the incrementally increasing of the number of buckets at L2 to the final number of buckets according to the arithmetic series includes incrementally increasing the number of buckets at L2 to the final number of buckets according to the arithmetic series expressed as:
∑
k
=
1
R
2
k
=
1
+
2
+
3
+
…
+
R
2
=
R
2
(
R
2
+
1
)
2
=
R
2
2
+
R
2
2
.

### Claim 8

A system comprising:
a memory; and
processing circuitry configured to execute program instructions out of the memory to:
in a first hardening cycle, in response to a first group of index entries filling a single bucket data structure (“bucket”) at an in-memory hash table level (“L1”), harden the single bucket at L1 to a single initial bucket at an intermediate on-drive hash table level (“L2”);
in subsequent successive hardening cycles:
incrementally increase a number of buckets at L2 to a final number of buckets according to an arithmetic series; and
in response to a next group of index entries up to a last group of index entries filling the single bucket at L1, harden the single bucket at L1 across the incrementally increased number of buckets at L2; and
in response to the final number of buckets at L2 being filled with index entries, harden the final number of buckets at L2 across a predetermined number of buckets at an on-drive hash table level (“L3”), wherein the predetermined number of buckets at L3 is greater than the final number of buckets at L2.

### Claim 9 (depends on 8)

The system of claim 8 wherein the processing circuitry is configured to execute the program instructions out of the memory, in the first hardening cycle, having hardened the single bucket at L1 to the single initial bucket at L2, to delete or remove the first group of index entries from the single bucket at L1.

### Claim 10 (depends on 9)

The system of claim 9 wherein the processing circuitry is configured to execute the program instructions out of the memory, in the subsequent successive hardening cycles, having hardened the single bucket at L1 across the incrementally increased number of buckets at L2, to delete or remove the next group of index entries up to the last group of index entries from the single bucket at L1.

### Claim 11 (depends on 8)

The system of claim 8 wherein the processing circuitry is configured to execute the program instructions out of the memory, having hardened the final number of buckets at L2 across the predetermined number of buckets at L3, to reset the number of buckets at L2 to an initial number defined by a single bucket.

### Claim 12 (depends on 8)

The system of claim 8 wherein “|L1|” denotes a size of L1 in terms of a first number of buckets, wherein “|L2|” denotes a size of L2 in terms of the final number of buckets, wherein “|L3|” denotes a size of L3 in terms of the predetermined number of buckets, and wherein the processing circuitry is configured to execute the program instructions out of the memory to incrementally increase the size of L2 to |L2| expressed as:
❘
"\[LeftBracketingBar]"
L
2
❘
"\[RightBracketingBar]"
=
2
⁢
❘
"\[LeftBracketingBar]"
L
1
❘
"\[RightBracketingBar]"
⁢
❘
"\[LeftBracketingBar]"
L
3
❘
"\[RightBracketingBar]"
.

### Claim 13 (depends on 12)

The system of claim 12 wherein “R2” denotes a ratio of |L2| to |L1|, wherein “R3” denotes a ratio of |L3| to |L1|, wherein “B” denotes a fullness threshold for each bucket at L1, L2, and L3 in terms of a predetermined number of index entries, and wherein the processing circuitry is configured to execute the program instructions out of the memory to:
determine an amortization for hardening the final number of buckets at L2 across the predetermined number of buckets at L3,
wherein the amortization is expressed as:
Amortization
⁢
=
2
⁢
R
2
*
B
R
2
2
+
R
2
+
2
⁢
R
3
.

### Claim 14 (depends on 13)

The system of claim 13 wherein the processing circuitry is configured to execute the program instructions out of the memory to incrementally increase the number of buckets at L2 to the final number of buckets according to the arithmetic series expressed as:
∑
k
=
1
R
2
k
=
1
+
2
+
3
+
…
+
R
2
=
R
2
(
R
2
+
1
)
2
=
R
2
2
+
R
2
2
.

### Claim 15

A computer program product including a set of non-transitory, computer-readable media having program instructions that, when executed by processing circuitry, cause the processing circuitry to perform a method comprising:
in a first hardening cycle, in response to a first group of index entries filling a single bucket data structure (“bucket”) at an in-memory hash table level (“L1”), hardening the single bucket at L1 to a single initial bucket at an intermediate on-drive hash table level (“L2”);
in subsequent successive hardening cycles:
incrementally increasing a number of buckets at L2 to a final number of buckets according to an arithmetic series; and
in response to a next group of index entries up to a last group of index entries filling the single bucket at L1, hardening the single bucket at L1 across the incrementally increased number of buckets at L2; and
in response to the final number of buckets at L2 being filled with index entries, hardening the final number of buckets at L2 across a predetermined number of buckets at an on-drive hash table level (“L3”), the predetermined number of buckets at L3 being greater than the final number of buckets at L2.

### Claim 16 (depends on 15)

The computer program product of claim 15 wherein the method comprises:
in the first hardening cycle, having hardened the single bucket at L1 to the single initial bucket at L2, deleting or removing the first group of index entries from the single bucket at L1.

### Claim 17 (depends on 16)

The computer program product of claim 16 wherein the method comprises:
in the subsequent successive hardening cycles, having hardened the single bucket at L1 across the incrementally increased number of buckets at L2, deleting or removing the next group of index entries up to the last group of index entries from the single bucket at L1.

### Claim 18 (depends on 15)

The computer program product of claim 15 wherein the method comprises:
having hardened the final number of buckets at L2 across the predetermined number of buckets at L3, resetting the number of buckets at L2 to an initial number defined by a single bucket.

### Claim 19 (depends on 15)

The computer program product of claim 15 wherein “|L1|” denotes a size of L1 in terms of a first number of buckets, wherein “|L2|” denotes a size of L2 in terms of the final number of buckets, wherein “|L3|” denotes a size of L3 in terms of the predetermined number of buckets, and wherein the incrementally increasing of the number of buckets at L2 to the final number of buckets according to an arithmetic series includes incrementally increasing the size of L2 to |L2| expressed as:
❘
"\[LeftBracketingBar]"
L
2
❘
"\[RightBracketingBar]"
=
2
⁢
❘
"\[LeftBracketingBar]"
L
1
❘
"\[RightBracketingBar]"
⁢
❘
"\[LeftBracketingBar]"
L
3
❘
"\[RightBracketingBar]"
.

### Claim 20 (depends on 19)

The computer program product of claim 19 wherein “R2” denotes a ratio of |L2| to |L1|, wherein “R3” denotes a ratio of |L3| to |L1|, wherein “B” denotes a fullness threshold for each bucket at L1, L2, and L3 in terms of a predetermined number of index entries, and wherein the method comprises:
determining an amortization for hardening the final number of buckets at L2 across the predetermined number of buckets at L3,
wherein the amortization is expressed as:
Amortization
⁢
=
2
⁢
R
2
*
B
R
2
2
+
R
2
+
2
⁢
R
3
.
