Pagination of B*-trees with variable-length records

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pagination of B*-trees with variable-length records

Full text

Pdf (458 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 9 (September 1977) table of contents

Pages: 670 - 674

Year of Publication: 1977

ISSN:0001-0782

Author

Edward M. McCreight

Xerox Palo Alto Research Center, Palo Alto, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 36, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359810.359839 What is a DOI?

ABSTRACT

A strategy is presented for pagination of B*-trees with variable-length records. If records of each length are uniformly distributed within the file, and if a wide distribution of record lengths exists within the file, then this strategy results in shallow trees with fast access times. The performance of this strategy in an application is presented, compared with that of another strategy, and analyzed.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bayer, R., and McCreight, E. Organization and maintenance of large ordered indexes. Acta lnformatica 1 (1972), 290-306.
	2	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	3	Bayer, R., and Unterauer, K. Prefix B-Trees. Res. Rep. RJ 1796, IBM Res. Lab., San Jose, Calif., June 1976.
	4	Wagner, R.E. Indexing design considerations. IBM Syst. J. 12, 4 (1973), 351-367.
	5	Keehn, D.G., and Lacy, J.O. VSAM data set design parameters. IBM Syst. 13, 3 (1974), 186-212.
	6	Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

CITED BY 9

	L. L. Larmore , D. S. Hirschberg, Efficient optimal pagination of scrolls, Communications of the ACM, v.28 n.8, p.854-856, Aug. 1985
	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
	Daniel Swinehart , Gene McDaniel , David Boggs, WFS a simple shared file system for a distributed environment, Proceedings of the seventh ACM symposium on Operating systems principles, p.9-17, December 10-12, 1979, Pacific Grove, California, United States
	D. S. Hirschberg , L. L. Larmore, New applications of failure functions, Journal of the ACM (JACM), v.34 n.3, p.616-625, July 1987
	George Diehr , Bruce Faaland, Optimal pagination of B-trees with variable-length items, Communications of the ACM, v.27 n.3, p.241-247, March 1984
	Porter Eugene Smith , James H. Graham, A simple balanced search tree, Proceedings of the 1993 ACM conference on Computer science, p.461-465, February 16-18, 1993, Indianapolis, Indiana, United States
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Mayank Bawa , Tyson Condie , Prasanna Ganesan, LSH forest: self-tuning indexes for similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Leonardo Guerreiro Azevedo , Rodrigo Salvador Monteiro , Geraldo Zimbrão , Jano Moreira De Souza, Polyline Spatial Join Evaluation Using Raster Approximation, Geoinformatica, v.7 n.4, p.315-336, December 2003

INDEX TERMS

Keywords:
B-tree, database, index, searching, storage structure, tree

Collaborative Colleagues:

Edward M. McCreight: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player