Use of Binary Trees for Storage Allocation
Original Publication Date: 1981-Nov-01
Included in the Prior Art Database: 2005-Feb-12
Many current storage allocation techniques require sequential searching through a chained list containing the available space until a block has been found where the desired amount can be obtained. To minimize storage fragmentation, storage is usually allocated multiples of a relatively large fixed block size. The method described here uses a binary tree to keep track of sizes of space available and the corresponding location.