Selecting pages implementing leaf nodes and internal nodes of a data set index for reuse

Patent metadata

Field	Value
Publication number	US-2016266809-A1
Application number	US-201615159716-A
Country	US
Kind code	A1
Filing date	May 19, 2016
Priority date	Sep 14, 2012
Publication date	Sep 15, 2016
Grant date	—

Abstract

Provided are a computer program product, system, and method for selecting pages implementing leaf nodes and internal nodes of a data set index for reuse in memory. Pages in the memory are allocated to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set. At least at least one duration parameter indicates an amount of time after which an unused page implement one of the internal nodes or leaf nodes is eligible for reuse. Selection is made of at least one selected page allocated to at least one of the leaf nodes and the internal nodes that has not been used for one of the at least one duration parameter for reuse.

First claim

1 . A computer program product for managing a data set stored in a storage in a memory, the computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therein that executes to perform operations, the operations comprising:
allocating pages in the memory to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set; maintaining at least one duration parameter indicating an amount of time after which an unused page implement one of the internal nodes or leaf nodes is eligible for reuse; selecting at least one selected page allocated to at least one of the leaf nodes and the internal nodes that has not been used for one of the at least one duration parameter for reuse.

2 . The computer program product of claim 1 , wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set.

3 . The computer program product of claim 1 , wherein the at least one duration parameter includes a leaf node duration and an internal node duration, wherein the leaf node duration is used to select one of the leaf nodes for reuse and wherein the internal node duration is used to select one of the internal nodes for use.

4 . (canceled)

5 . The computer program product of claim 3 , wherein the operations further comprise:
determining whether a utilization rate indicating an amount of the pages that are not available for reuse to be allocated to leaf nodes and internal nodes exceeds a threshold; and decreasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate exceeds the threshold.

6 . The computer program product of claim 5 , wherein the operations further comprise:
increasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate does not exceed the threshold.

7 . The computer program product of claim 5 , wherein the utilization rate is based on a number of the pages allocated to the leaf nodes and the internal nodes not indicated as available for reuse and a total number of pages allocated.

8 . A system for managing a data set stored in a storage, comprising:
a processor; a memory; a computer readable storage medium having code executed by the processor to perform operations, the operations comprising:
allocating pages in the memory to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set;
maintaining at least one duration parameter indicating an amount of time after which an unused page implement one of the internal nodes or leaf nodes is eligible for reuse; and
selecting at least one selected page allocated to at least one of the leaf nodes and the internal nodes that has not been used for one of the at least one duration parameter for reuse.

9 . The system of claim 8 , wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set.

10 . The system of claim 8 , wherein the at least one duration parameter includes a leaf node duration and an internal node duration, wherein the leaf node duration is used to select one of the leaf nodes for reuse and wherein the internal node duration is used to select one of the internal nodes for use.

11 . (canceled)

12 . The system of claim 10 , wherein the operations further comprise:
determining whether a utilization rate indicating an amount of the pages that are not available for reuse to be allocated to leaf nodes and internal nodes exceeds a threshold; and decreasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate exceeds the threshold.

13 . The system of claim 12 , wherein the operations further comprise:
increasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate does not exceed the threshold.

14 . The system of claim 12 , wherein the utilization rate is based on a number of the pages allocated to the leaf nodes and the internal nodes not indicated as available for reuse and a total number of pages allocated.

15 . A method, comprising:
allocating pages in a memory to internal nodes and leaf nodes of a tree data structure in a non-transitory computer readable storage medium representing all or a portion of a data set index for the data set; maintaining at least one duration parameter indicating an amount of time after which an unused page implement one of the internal nodes or leaf nodes is eligible for reuse; selecting at least one selected page allocated to at least one of the leaf nodes and the internal nodes that has not been used for one of the at least one duration parameter for reuse.

16 . The method of claim 15 , wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set.

17 . The method of claim 15 , wherein the at least one duration parameter includes a leaf node duration and an internal node duration, wherein the leaf node duration is used to select one of the leaf nodes for reuse and wherein the internal node duration is used to select one of the internal nodes for use.

18 . (canceled)

19 . The method of claim 17 , wherein the operations further comprise:
determining whether a utilization rate indicating an amount of the pages that are not available for reuse to be allocated to leaf nodes and internal nodes exceeds a threshold; and decreasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate exceeds the threshold.

20 . The method of claim 19 , wherein the operations further comprise:
increasing at least one of the leaf node duration and the internal node duration in response to determining that the utilization rate does not exceed the threshold.

21 . The method of claim 19 , wherein the utilization rate is based on a number of the pages allocated to the leaf nodes and the internal nodes not indicated as available for reuse and a total number of pages allocated.

Assignees

• IBM

Inventors

• Erdmann Derek L
• Reed David C
• Reed Thomas C
• Smith Max D

Classifications

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F12/023

  Free address space management · CPC title

• G06F12/1009

  using page tables, e.g. page table structures · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title