Type of Document	Master's Thesis
Author	West, Raymond Troy
URN	etd-03122013-040251
Title	On the performance of B-trees using dynamic address computation
Degree	Master of Science
Department	Computer Science
Advisory Committee	Advisor Name Title Hartson, H. Rex Committee Chair Foutz, Robert Committee Member Kafura, Dennis G. Committee Member
Keywords	Database management
Date of Defense	1985-11-05
Availability	restricted
Abstract The 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 Dymanic 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access  LD5655.V855_1985.W477.pdf 6.83 Mb 00:31:35 00:16:15 00:14:13 00:07:06 00:00:36 next to an author's name indicates that all files or directories associated with their ETD are accessible from the Virginia Tech campus network only.

If you have questions or technical problems, please Contact DLA.