Fixed Time Cost Management of a Sorted Group of Objects in Storage
Original Publication Date: 2003-Nov-19
Included in the Prior Art Database: 2003-Nov-19
The Fundamental Problem The time cost to manage a sorted list containing N objects is defines as the cost of inserting the N+1 object, or the cost of finding one. The theoretic mean cost is in the order of Log(N) denoted in the literature as O(Log(N)). The total cost of building this list, or of accessing all its objects based on this cost model is therefore O(N*Log(N)). If the list can only be accessed sequentially (i.e., no direct access to the Nth element), than the cost per object is O(N), and the total cost is O(N2). Direct access to the items is possible if they are of a fixed size, or there is a management structure consisting of fixed size pointers to them. When the list consists of variable size objects, with very large N, compounded into a larger object, this management problem becomes critical to the system performance. Objects in storage systems bear a large cost tag per operation, specifically when the lists and/or objects are large and require significant I/O penalties.