|
|
|
@inproceedings{DBLP:conf/vldb/Deen82,
author = {S. Misbah Deen},
title = {An Implementation of Impure Surrogates},
booktitle = {Eigth International Conference on Very Large Data Bases, September
8-10, 1982, Mexico City, Mexico, Proceedings},
publisher = {Morgan Kaufmann},
year = {1982},
isbn = {0-934613-14-1},
pages = {245-256},
ee = {db/conf/vldb/Deen82.html},
crossref = {DBLP:conf/vldb/82},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Surrogates or internal identifiers can be made to facilitate both fast access and storage in- dependence if they are implemented properly. Such an implementation is discussed here; it permits the tuplcs of a relation to be accessed very fast by primary key for both random and sequential search without retarding the per- formance of secondary keys. It employs a key compression and a hasiiing algorithm and attempts to place tuples on data pages in the primary key sequence. Subsequent updates are absorbed by a dynamic allocation of overflows. An indexing technique called a hash tree holds surrogates in primary key order, and facili- tates fast sequential access. The access speed remains high even at a 90% load factor, with- out being significantly affected by storage reorganisation resulting from the addition of new attributes, deletion of old attributes or change of data page sizes.
These techniques have been implemented in the PRECI database system at Aberdeen.
Copyright © 1982 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
