Access Restriction

Author Maly, Kurt
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Maintenance costs ♦ Pages ♦ Linked representation ♦ B-tree ♦ File organization ♦ Index
Abstract In [4] Maruyama and Smith analyzed design alternatives for virtual memory indexes. The indexes investigated were those modeled on the structure of VSAM [5] which are closely related to B-trees [1]. Maruyama and Smith presented alternatives for search strategies, page format, and whether or not to compress keys. They made a comparative analysis based on the average cost of processing the index for retrieval of a key with its associated data pointer (or a sequence of keys and data pointers). The analysis showed that the optimal solution depends on machine and file characteristics and they provided formulas for selecting the best alternative. In this brief note1 we propose that another alternative for the page format be considered. The basic idea is to replace the sequential representation within a page by a linked representation. The main advantage of this method is realized in the construction (and maintenance) phase of the index. Although this phase is difficult to analyze quantitatively—as alluded to in [4]—we provide data to substantiate our claim of a net saving in construction cost without any corresponding loss in the average retrieval cost. In the ensuing discussion we assume that the reader is familiar both with B-trees and the paper of Maruyama and Smith [4].
Description Affiliation: Univ. of Minnesota, Minneapolis (Maly, Kurt)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 9
Page Count 2
Starting Page 786
Ending Page 787

Open content in new tab

   Open content in new tab
Source: ACM Digital Library