Shiftable memory supporting in-memory data structures

Patent metadata

Field	Value
Publication number	US-9606746-B2
Application number	US-201114349113-A
Country	US
Kind code	B2
Filing date	Oct 27, 2011
Priority date	Oct 27, 2011
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

A shiftable memory supporting in-memory data structures employs built-in data shifting capability. The shiftable memory includes a memory having built-in shifting capability to shift a contiguous subset of data from a first location to a second location within the memory. The shiftable memory further includes a data structure defined on the memory to contain data comprising the contiguous subset. The built-in shifting capability of the memory to facilitate one or more of movement of the data, insertion of the data and deletion of the data within the data structure.

First claim

What is claimed is:

1. A shiftable memory supporting in-memory data structures comprising:
a memory having built-in shifting capability to shift a contiguous subset of the data from a first location to a second location within the memory, the contiguous subset of data having a size that is smaller than a total size of the memory, the built-in shifting capability to shift only data of the contiguous subset; and
a data structure defined on the memory to contain data comprising the contiguous subset, the built-in shifting capability to facilitate one or more of movement of the data, insertion of the data and deletion of the data within the data structure, wherein the data structure defined on the memory is located in both of the memory having built-in shifting capability and another, non-shiftable memory.

2. The shiftable memory supporting in-memory data structures of claim 1 , wherein the data structure comprises a data tree.

3. The shiftable memory supporting in-memory data structures of claim 2 , wherein the data tree comprises a B+ tree.

4. The shiftable memory supporting in-memory data structures of claim 1 , wherein the data structure comprises a hash table.

5. The shiftable memory supporting in-memory data structures of claim 1 , wherein the data of the data structure comprises one or both of ghost records and record gaps.

6. The shiftable memory supporting in-memory data structures of claim 1 , further comprising a data structure operator to operate on the data structure in the memory.

7. The shiftable memory supporting in-memory data structures of claim 6 , wherein the built-in shifting capability in conjunction with the data structure operator to provide one or both of sorting data of the data structure and maintaining a substantially sorted order of the data in the data structure.

8. The shiftable memory supporting in-memory data structures of claim 6 , wherein the data structure operator comprises one or more of a library sort operator, an interpolation search operator, a binary search operator and a sequential search operator.

9. A shiftable memory system having in-memory data structure support comprising:
a shiftable memory comprising a plurality of memory cells with built-in data shifting capability to shift a contiguous subset of data stored in the memory cells from a first location to a second location within the shiftable memory, a size of the contiguous subset being smaller than a total size of the shiftable memory; and
a data structure operator defined on the shiftable memory to operate on an in-memory data structure, the in-memory data structure to contain data comprising the contiguous subset, wherein the data structure operator comprises one or more of: a rotation operator; an interpolation search operator; a binary search operator; and a sequential search operator,
wherein the built-in data shifting capability in conjunction with the data structure operator facilitate one or more of moving data records of the data structure, inserting data records of the data structure and deleting data records of the data structure.

10. The shiftable memory system of claim 9 , wherein the data structure operator comprises a sort operator to one or both of sort the data in the data structure and maintain a substantially sorted order of the data in the data structure, the data structure comprising a substantially sorted array of data records.

11. A method of using shiftable memory with in-memory data structures, the method comprising:
defining a data structure comprising memory cells of the shiftable memory, the shiftable memory having a plurality of memory cells with built-in shifting capability to shift a contiguous subset of data from a first location to a second location within the shiftable memory, a size of the contiguous subset of data being less than a total size of the shiftable memory;
inserting one or both of ghost records and record gaps in the data of the data structure; and
executing a data structure operator to operate on the data structure, the data structure to contain data comprising the contiguous subset of data,
wherein the built-in shifting capability of the shiftable memory facilitates executing the data structure operator by providing one or both of a downshift an upshift of the contiguous sub set.

12. The method of using shiftable memory with in-memory data structures of claim 11 , wherein executing a data structure operator further comprises
performing a search of the data of the data structure, and
wherein the built-in shifting capability to facilitate one or both of sorting the data of the data structure and maintaining a substantially sorted order of the data of the data structure.

Assignees

• Graefe Goetz
• Kelly Terence P
• Kuno Harumi
• Tarjan Robert E
• Hewlett Packard Entpr Dev Lp

Inventors

• Graefe Goetz
• Kelly Terence P
• Kuno Harumi
• Tarjan Robert E

Classifications

• G11C15/04 Primary

  using semiconductor elements · CPC title

• G11C19/188

  Organisation of a multiplicity of shift registers, e.g. regeneration, timing or input-output circuits · CPC title

• G11C19/00

  Digital stores in which the information is moved stepwise, e.g. shift registers · CPC title

• G11C19/287

  Organisation of a multiplicity of shift registers · CPC title

• G06F3/0673

  Single storage device · CPC title