On the performance of B-trees using dynamic address computation

dc.contributor.authorWest, Raymond Troy, Jr.en
dc.contributor.committeechairHartson, H. Rexen
dc.contributor.committeememberKafura, Dennis G.en
dc.contributor.committeememberFoutz, Roberten
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T21:31:35Zen
dc.date.adate2013-03-12en
dc.date.available2014-03-14T21:31:35Zen
dc.date.issued1985-11-05en
dc.date.rdate2013-03-12en
dc.date.sdate2013-03-12en
dc.description.abstractThe B-tree is a one of the more popular methods in use today for indexes and inverted files in database management systems. The traditional implementation of a Bâ tree uses many pointers (more than one per key), which can directly affect the performance of the B-tree. A general method of file organization and access (called Dynanic Address Computation) has been described by Cook that can be used to implement B-trees using no pointers. A minimal amount of storage (in addition to the keys) is required. An implementation of Dynamic Address Computation and a B-tree management package is described. Analytical performance measures are derived in an attempt to understand the performance characteristics of the B-tree. It is shown that the additional costs associated with Dynamic Address Computation result in an implementation that is competitive with traditional implementations only for small applications. For very large B-trees, additional work is required to make the performance acceptable. Some examples of possible modifications are discussed.en
dc.description.degreeMaster of Scienceen
dc.format.extentv, 258 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-03122013-040251en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-03122013-040251/en
dc.identifier.urihttp://hdl.handle.net/10919/41574en
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1985.W477.pdfen
dc.relation.isformatofOCLC# 13354832en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1985.W477en
dc.subject.lcshData structures (Computer science)en
dc.subject.lcshDatabase managementen
dc.subject.lcshTrees (Graph theory)en
dc.titleOn the performance of B-trees using dynamic address computationen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
LD5655.V855_1985.W477.pdf
Size:
6.47 MB
Format:
Adobe Portable Document Format
Description:

Collections