Prefix B-trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Prefix B-trees

Full text

Pdf (1.13 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 2 , Issue 1 (March 1977) table of contents

Pages: 11 - 26

Year of Publication: 1977

ISSN:0362-5915

Authors

Rudolf Bayer	Technische Univ. München, Munich, West Germany
Karl Unterauer	Technische Univ. München, Munich, West Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 192, Citation Count: 70

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/320521.320530 What is a DOI?

ABSTRACT

Two modifications of B-trees are described, simple prefix B-trees and prefix B-trees. Both store only parts of keys, namely prefixes, in the index part of a B*-tree. In simple prefix B-trees those prefixes are selected carefully to minimize their length. In prefix B-trees the prefixes need not be fully stored, but are reconstructed as the tree is searched. Prefix B-trees are designed to combine some of the advantages of B-trees, digital search trees, and key compression techniques while reducing the processing overhead of compression techniques.

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	AUER, 1~. Schlfisselkompressionen in B*-b~iumen. Diplomarbeit, Tech. U. Miinchen, Mtinchen, Germany, 1976.
	2	BAYER, R. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta lnformatica 1 (1972), 290-306.
	3	BArER, R. Storage characteristics and methods for searching and addressing. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 440-444.
	4	BAYER, l~., AND McCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), 173-189.
	5	R. Bayer , J. K. Metzger, On the encipherment of search trees and random access files, ACM Transactions on Database Systems (TODS), v.1 n.1, p.37-52, March 1976 [doi>10.1145/320434.320445]
	6	BXYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. IBM Res. Rep. RJ 1791, IBM Res. Lab., San Jose, CMif., May 1976.
	7	BXYER, R., AND UNTERXU~R, K. Prefix B-trees. IBM Res. Rep. RJ 1796, IBM Res. Lab., San Jose, Calif.~ June 1976.
	8	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
	9	WA~N~R, R.E. Indexing design considerations. IBM Syst. J. ~ (1973), 351-367.
	10	WEDEKIND, H. On the selection of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds., North-Holland Pub. Co., Amsterdam, 1974, pp. 385-397.

CITED BY 70

	Wilfred J. Hansen, A Cost Model for the Internal Organization of B+-Tree Nodes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.508-532, Oct. 1981
	Tan Watanabe , Tsuneharu Ohsawa , Takaji Suzuki, A simple database language for personal computers, Communications of the ACM, v.26 n.9, p.646-653, Sept. 1983
	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	Anil K. Garg , C. C. Gotlieb, Order-preserving key transformations, ACM Transactions on Database Systems (TODS), v.11 n.2, p.213-234, June 1986
	Arnold L. Rosenberg , Lawrence Snyder, Time- and space-optimality in B-trees, ACM Transactions on Database Systems (TODS), v.6 n.1, p.174-193, March 1981
	Kurt Maly, A note on virtual memory indexes, Communications of the ACM, v.21 n.9, p.786-787, Sept. 1978
	David B. Lomet, Multi-table search for B-tree files, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts
	A. Malhotra , H. M. Markowitz , D. P. Pazel, EAS-E: an integrated approach to application development, ACM Transactions on Database Systems (TODS), v.8 n.4, p.515-542, Dec. 1983
	Michael Freeston, A general solution of the n-dimensional B-tree problem, ACM SIGMOD Record, v.24 n.2, p.80-91, May 1995
	Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999
	Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, ACM SIGMOD Record, v.30 n.2, p.235-246, June 2001
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	David E. Ferguson, Bit-Tree: a data structure for fast file processing, Communications of the ACM, v.35 n.6, p.114-120, June 1992
	H. V. Jagadish , Nick Koudas , Divesh Srivastava, On effective multi-dimensional indexing for strings, ACM SIGMOD Record, v.29 n.2, p.403-414, June 2000
	Witold Litwin, Trie hashing, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan
	Rudolf Bayer, B-trees and databases, past and future, Software pioneers: contributions to software engineering, Springer-Verlag New York, Inc., New York, NY, 2002
	Paolo Ferragina , Roberto Grossi, Fast string searching in secondary storage: theoretical developments and experimental results, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.373-382, January 28-30, 1996, Atlanta, Georgia, United States
	Beng Chin Ooi , Kian-Lee Tan, B-trees: bearing fruits of all kinds, Australian Computer Science Communications, v.24 n.2, p.13-20, January-February 2002
	Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Harry M. Markowitz , Ashok Malhotra , Donald P. Pazel, The EAS-E application development system: principles and language summary, Communications of the ACM, v.27 n.8, p.785-799, Aug 1984
	David B. Lomet, A high performance, universal, key associative access method, ACM SIGMOD Record, v.13 n.4, May 1983
	David Lomet, The evolution of effective B-tree: page organization and techniques: a personal account, ACM SIGMOD Record, v.30 n.3, September 2001
	Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003
	David B. Lomet, A simple bounded disorder file organization with good performance, ACM Transactions on Database Systems (TODS), v.13 n.4, p.525-551, Dec. 1988
	George P. Copeland , Setrag N. Khoshafian, A decomposition storage model, ACM SIGMOD Record, v.14 n.4, p.268-279, May 1985
	Anthony I. Wasserman, The data management facilities of PLAIN, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts
	Philip Bohannon , Peter Mcllroy , Rajeev Rastogi, Main-memory index structures with fixed-size partial keys, ACM SIGMOD Record, v.30 n.2, p.163-174, June 2001
	Witold A. Litwin , Nick Roussopoulos , Gerald Levy , Wang Hong, Trie Hashing with Controlled Load, IEEE Transactions on Software Engineering, v.17 n.7, p.678-691, July 1991
	J. K. Mullin, Optimal Semijoins for Distributed Database Systems, IEEE Transactions on Software Engineering, v.16 n.5, p.558-560, May 1990
	Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Ehud Gudes , Shalom Tsur, Experiments with B-tree reorganization, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Rickard Cöster , Martin Svensson, Inverted file search algorithms for collaborative filtering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
	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
	Ricardo Baeza-Yates , Alistair Moffat , Gonzalo Navarro, Searching large text collections, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	T. H. Merrett , N. Laliberte, Including Scalars in a Programming Language Based on the Relational Algebra, IEEE Transactions on Software Engineering, v.15 n.11, p.1437-1443, November 1989
	Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach, ACM Transactions on Database Systems (TODS), v.31 n.2, p.439-484, June 2006
	Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, A space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.79-110, January 2006
	Paolo Ferragina , Roberto Grossi , Ankur Gupta , Rahul Shah , Jeffrey Scott Vitter, On searching compressed string collections cache-obliviously, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
	Goetz Graefe, B-tree indexes, interpolation search, and skew, Proceedings of the 2nd international workshop on Data management on new hardware, June 25-25, 2006, Chicago, Illinois
	Qun Chen , Andrew Lim , Kian Win Ong , Jiqing Tang, Indexing XML documents for XPath query processing in external memory, Data & Knowledge Engineering, v.59 n.3, p.681-699, December 2006
	Carsten Binnig , Stefan Hildenbrand , Franz Färber, Dictionary-based order-preserving string compression for main memory column stores, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Goetz Graefe, The five-minute rule 20 years later (and how flash memory changes the rules), Communications of the ACM, v.52 n.7, July 2009
	Goetz Graefe, Efficient columnar storage in B-trees, ACM SIGMOD Record, v.36 n.1, p.3-6, March 2007
	David B. Lomet, Digital B-trees, Proceedings of the seventh international conference on Very Large Data Bases, p.333-344, September 09-11, 1981, Cannes, France
	Y. Edmund Lien , Jonathan E. Shopiro , Shalom Tsur, DSIS - a database system with interrelational semantics, Proceedings of the seventh international conference on Very Large Data Bases, p.465-477, September 09-11, 1981, Cannes, France
	Gang Qian , Qiang Zhu , Qiang Xue , Sakti Pramanik, The ND-tree: a dynamic indexing technique for multidimensional non-ordered discrete data spaces, Proceedings of the 29th international conference on Very large data bases, p.620-631, September 09-12, 2003, Berlin, Germany
	Goetz Graefe, Write-optimized B-trees, Proceedings of the Thirtieth international conference on Very large data bases, p.672-683, August 31-September 03, 2004, Toronto, Canada
	Shankar Pal , Istvan Cseri , Oliver Seeliger , Gideon Schaller , Leo Giakoumakis , Vasili Zolotov, Indexing XML data stored in a relational database, Proceedings of the Thirtieth international conference on Very large data bases, p.1146-1157, August 31-September 03, 2004, Toronto, Canada
	Torsten Grust , Jan Rittinger , Jens Teubner, Why off-the-shelf RDBMSs are better at XPath than you might expect, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Ariel Futoransky , Damián Saura , Ariel Waissbein, The ND2DB attack: database content extraction using timing attacks on the indexing algorithms, Proceedings of the first conference on First USENIX Workshop on Offensive Technologies, p.3-3, August 06, 2007, Boston, MA
	Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996
	Gennady Antoshenkov, Dictionary-based order-preserving string compression, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.26-39, February 1997
	Ratko Orlandic , John L. Pfaltz, Compact 0-Complete Trees, Proceedings of the 14th International Conference on Very Large Data Bases, p.372-381, August 29-September 01, 1988
	V. W. Setzer , Andrea Zisman, New Concurrency Control Algorithms for Accessing and Compacting B-Trees, Proceedings of the 20th International Conference on Very Large Data Bases, p.238-248, September 12-15, 1994
	Frank Ramsak , Volker Markl , Robert Fenk , Martin Zirkel , Klaus Elhardt , Rudolf Bayer, Integrating the UB-Tree into a Database System Kernel, Proceedings of the 26th International Conference on Very Large Data Bases, p.263-272, September 10-14, 2000
	Harry Leslie , Rohit Jain , Dave Birdsall , Hedieh Yaghmai, Efficient Search of Multi-Dimensional B-Trees, Proceedings of the 21th International Conference on Very Large Data Bases, p.710-719, September 11-15, 1995
	Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Goetz Graefe, The Five-minute Rule 20 Years Later: and How Flash Memory Changes the Rules, Queue, v.6 n.4, July/August 2008
	Yibin Chen, On the Signature Tree Construction and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.18 n.9, p.1207-1224, September 2006
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Goetz Graefe, The five-minute rule twenty years later, and how flash memory changes the rules, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China
	Ira Assent , Ralph Krieger , Farzad Afschari , Thomas Seidl, The TS-tree: efficient time series search and retrieval, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	I. Elizabeth Shanthi , Y. Izaaz , R. Nadarajan, On the SD-tree construction for optimal signature operations, Proceedings of the 1st Bangalore annual Compute conference, January 18-20, 2008, Bangalore, India
	Manuel Mayr, Pathfinder meets DB2®: relational XQuery optimization techniques, Proceedings of the 2008 EDBT Ph.D. workshop, March 25-25, 2008, Nantes, France
	Changqing Chen , Sakti Pramanik , Qiang Zhu , Watve Alok , Gang Qian, The C-ND tree: a multidimensional index for hybrid continuous and non-ordered discrete data spaces, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Nikolas Askitis , Justin Zobel, B-tries for disk-based string management, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.157-179, January 2009