Browse Prior Art Database

Use of a Binary Tree for Storage De Allocation

IP.com Disclosure Number: IPCOM000053738D
Original Publication Date: 1981-Nov-01
Included in the Prior Art Database: 2005-Feb-12

Publishing Venue

IBM

Related People

Authors:
Goncharsky, SL Woodrum, LJ [+details]

Abstract

Many current storage de-allocation techniques maintain a chained list of all space available for allocation. Each time a new entry is to be made in this list, a search is made to see if the space to be made available is adjacent to an existing entry in the free space chain. The method described here uses a binary tree to represent available space. This reduces the worst-case number of comparisons necessary before making an entry from N to 2 log - N, where N is the number of entries.