Managing locality in space reuse in a shadow written B-tree via interior node free space list
US5261088A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 26, 1990 |
| Grant date | Nov 9, 1993 |
| Priority date | — |
| Expiry date | Apr 26, 2010 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99957
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for managing space re-use with respect to the indices (nodes) of shadow written tree organized dynamic random accessed files/records/pages located in the external store of a CPU. The method reserves space in all non-leaf nodes and maintains a list of available node addresses. When a new node is required then space, if available, is obtained from the parent node list. Only when the parent list becomes exhausted is space (node) obtained from a node inventory manager. Deletion of a node causes its address to be placed on the free or available list maintained by that node's parent. If there is no space, then space on the parent node list is obtained by returning to the inventory manager that node on the list having the least locality with the existing subordinate (children) nodes of the parent.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.