The Ubiquitous B-Tree.
Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979)@article{DBLP:journals/csur/Comer79,
author = {Douglas Comer},
title = {The Ubiquitous B-Tree},
journal = {ACM Comput. Surv.},
volume = {11},
number = {2},
year = {1979},
pages = {121-137},
ee = {db/journals/csur/Comer79.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
B-trees have become, de facto, a standard for file organization. File indexes of users,
dedicated database systems, and general-purpose access methods have all been proposed
and implemented using B-trees. This paper reviews B-trees and shows why they have
been so successful. It discusses the major variations of the B-tree, especially the B+-tree,
contrasting the relative merits and costs of each implementation. It illustrates a general
purpose access method which uses a B-tree.
Copyright © 1979 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
Supplement
Douglas Comer:
Surveyor's Forum: The Tree Branches.
412
Electronic Edition BibTeX
References
- [Aho74]
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The Design and Analysis of Computer Algorithms.
Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
- [Auer76]
- ...
- [Baye72]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972) BibTeX
- [Baye72a]
- Rudolf Bayer:
Binary B-Trees for Virtual Memory.
SIGFIDET Workshop 1971: 219-235 BibTeX
- [Baye73]
- Rudolf Bayer:
Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms.
Acta Inf. 1: 290-306(1972) BibTeX
- [Baye76]
- Rudolf Bayer, J. K. Metzger:
On the Encipherment of Search Trees and Random Access Files.
ACM Trans. Database Syst. 1(1): 37-52(1976) BibTeX
- [Baye77]
- Rudolf Bayer, Karl Unterauer:
Prefix B-Trees.
ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX
- [Baye77a]
- Rudolf Bayer, Mario Schkolnick:
Concurrency of Operations on B-Trees.
Acta Inf. 9: 1-21(1977) BibTeX
- [Berl78]
- Hans J. Berliner:
The B* Tree Search Algorithm: A Best-First Proof Procedure.
Artif. Intell. 12(1): 23-40(1979) BibTeX
- [Brow78]
- Mark R. Brown:
A Storage Scheme for Height-Balanced Trees.
Inf. Process. Lett. 7(5): 231-232(1978) BibTeX
- [Brow78a]
- Mark R. Brown:
A Partial Analysis of Random Height-Balanced Trees.
SIAM J. Comput. 8(1): 33-41(1979) BibTeX
- [Clam64]
- ...
- [Fost65]
- ...
- [Ghos69]
- Sakti P. Ghosh, Michael E. Senko:
File Organization: On the Selection of Random Access Index Points for Sequential Files.
J. ACM 16(1): 569-579(1969) BibTeX
- [Guib77]
- Leonidas J. Guibas, Edward M. McCreight, Michael F. Plass, Janet R. Roberts:
A New Representation for Linear Lists.
STOC 1977: 49-60 BibTeX
- [Guib78]
- Leonidas J. Guibas, Robert Sedgewick:
A Dichromatic Framework for Balanced Trees.
FOCS 1978: 8-21 BibTeX
- [Held78]
- Gerald Held, Michael Stonebraker:
B-trees Re-examined.
Commun. ACM 21(2): 139-143(1978) BibTeX
- [Horo76]
- ...
- [IBM1]
- ...
- [IBM2]
- ...
- [Karl76]
- Philip L. Karlton, Samuel H. Fuller, R. E. Scroggs, E. B. Kaehler:
Performance of Height-Balanced Trees.
Commun. ACM 19(1): 23-28(1976) BibTeX
- [Keeh74]
- Daniel G. Keehn, John O. Lacy:
VSAM Data Set Design Parameters.
IBM Systems Journal 13(3): 186-212(1974) BibTeX
- [Knut68]
- Donald E. Knuth:
The Art of Computer Programming, Volume I: Fundamental Algorithms.
Addison-Wesley 1968
BibTeX
- [Knut73]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
- [Maru77]
- K. Maruyama, S. E. Smith:
Analysis of Design Alternatives for Virtual Memory Indexes.
Commun. ACM 20(4): 245-254(1977) BibTeX
- [Maue75]
- W. D. Maurer, T. G. Lewis:
Hash Table Methods.
ACM Comput. Surv. 7(1): 5-19(1975) BibTeX
- [McCr77]
- Edward M. McCreight:
Pagination of B*-Trees with Variable-Length Records.
Commun. ACM 20(9): 670-674(1977) BibTeX
- [Mill77]
- Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder:
Optimal 2, 3-Trees.
SIAM J. Comput. 8(1): 42-59(1979) BibTeX
- [Niev74]
- Jürg Nievergelt:
Binary Search Trees and File Organisation.
ACM Comput. Surv. 6(3): 195-207(1974) BibTeX
- [Orga72]
- ...
- [Rose78]
- Arnold L. Rosenberg, Lawrence Snyder:
Minimal-Comparison 2, 3-Trees.
SIAM J. Comput. 7(4): 465-480(1978) BibTeX
- [Rubi76]
- Frank Rubin:
Experiments in Text File Compression.
Commun. ACM 19(11): 617-623(1976) BibTeX
- [Sama76]
- Behrokh Samadi:
B-Trees in a System with Multiple Users.
Inf. Process. Lett. 5(4): 107-112(1976) BibTeX
- [Seve74]
- Dennis G. Severance:
Identifier Search Mechanisms: A Survey and Generalized Model.
ACM Comput. Surv. 6(3): 175-194(1974) BibTeX
- [Wagn73]
- Robert E. Wagner:
Indexing Design Considerations.
IBM Systems Journal 12(4): 351-367(1973) BibTeX
- [Wede74]
- Hartmut Wedekind:
On the Selection of Access Paths in a Data Base System.
IFIP Working Conference Data Base Management 1974: 385-398 BibTeX
- [Wirt76]
- ...
- [Yao78]
- Andrew Chi-Chih Yao:
On Random 2-3 Trees.
Acta Inf. 9: 159-170(1978) BibTeX
Referenced by
- Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann:
Functional-Join Processing.
VLDB J. 8(3-4): 156-177(2000)
- Till Westmann, Donald Kossmann, Sven Helmer, Guido Moerkotte:
The Implementation and Performance of Compressed Databases.
SIGMOD Record 29(3): 55-67(2000)
- Jun Rao, Kenneth A. Ross:
Making B+-Trees Cache Conscious in Main Memory.
SIGMOD Conference 2000: 475-486
- Nagavamsi Ponnekanti, Hanuma Kodavalla:
Online Index Rebuild.
SIGMOD Conference 2000: 529-538
- Beng Chin Ooi, Kian-Lee Tan, Cui Yu, Stéphane Bressan:
Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Indexing.
PODS 2000: 166-174
- Gísli R. Hjaltason, Hanan Samet:
Distance Browsing in Spatial Databases.
ACM Trans. Database Syst. 24(2): 265-318(1999)
- Jun Rao, Kenneth A. Ross:
Cache Conscious Indexing for Decision-Support in Main Memory.
VLDB 1999: 78-89
- Marcel Kornacker:
High-Performance Extensible Indexing.
VLDB 1999: 699-708
- H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava:
What can Hierarchies do for Data Warehouses?
VLDB 1999: 530-541
- Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan:
GHOST: Fine Granularity Buffering of Indexes.
VLDB 1999: 339-350
- Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang:
High Level Indexing of User-Defined Types.
VLDB 1999: 554-564
- Ming-Chuan Wu:
Query Optimization for Selections Using Bitmaps.
SIGMOD Conference 1999: 227-238
- George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras:
On Indexing Mobile Objects.
PODS 1999: 261-272
- Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter:
On Two-Dimensional Indexability and Optimal Range Search Indexing.
PODS 1999: 346-357
- Elisa Bertino, Barbara Catania, Boris Chidlovskii:
Indexing Constraint Databases by Using a Dual Representation.
ICDE 1999: 618-627
- Elisa Bertino, Barbara Catania, Boris Chidlovskii:
Approximation Techniques for Indexing Two-Dimensional Constraint Databases.
DASFAA 1999: 213-220
- Gunter Saake, Andreas Heuer:
Datenbanken: Implementierungstechniken.
MITP-Verlag 1999, ISBN 3-8266-0513-6
Contents - Beng Chin Ooi, Kian-Lee Tan, Tat-Seng Chua, Wynne Hsu:
Fast Image Retrieval Using Color-Spatial Information.
VLDB J. 7(2): 115-128(1998)
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Guido Moerkotte:
Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing.
VLDB 1998: 476-487
- Gísli R. Hjaltason, Hanan Samet:
Incremental Distance Join Algorithms for Spatial Databases.
SIGMOD Conference 1998: 237-248
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
SIGMOD Conference 1998: 142-153
- Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter:
Efficient Searching with Linear Constraints.
PODS 1998: 169-178
- Ming-Chuan Wu, Alejandro P. Buchmann:
Encoded Bitmap Indexing for Data Warehouses.
ICDE 1998: 220-230
- Paul M. Aoki:
Generalizing ``Search'' in Generalized Search Trees (Extended Abstract).
ICDE 1998: 380-389
- Yasuaki Nakamura, Hiroyuki Dekihara, Ryo Furukawa:
Spatio-Temporal Data Management for Moving Objects Using the PMD-Tree.
ER Workshops 1998: 496-507
- Elisa Bertino, Barbara Catania, Boris Shidlovsky:
Towards Optimal Indexing for Segment Databases.
EDBT 1998: 39-53
- Georgios Evangelidis, David B. Lomet, Betty Salzberg:
The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation.
VLDB J. 6(1): 1-25(1997)
- June S. Park, V. Sridhar:
Probabilistic Model and Optimal Reorganization of B+-Tree with Physical Clustering.
IEEE Trans. Knowl. Data Eng. 9(5): 826-832(1997)
- Robert C. Goldstein, Christian Wagner:
Database Management with Sequence Trees and Tokens.
IEEE Trans. Knowl. Data Eng. 9(1): 186-192(1997)
- Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik:
The New Jersey Data Reduction Report.
IEEE Data Eng. Bull. 20(4): 3-45(1997)
- Patrick E. O'Neil, Dallan Quass:
Improved Query Performance with Variant Indexes.
SIGMOD Conference 1997: 38-49
- Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant:
Range Queries in OLAP Data Cubes.
SIGMOD Conference 1997: 73-88
- Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou:
On the Analysis of Indexing Schemes.
PODS 1997: 249-256
- Sridhar Ramaswamy:
Efficient Indexing for Constraint and Temporal Databases.
ICDT 1997: 419-431
- Jun Cai, Kian-Lee Tan, Beng Chin Ooi:
On Incremental Cache Coherency Schemes in Mobile Computing Environments.
ICDE 1997: 114-123
- Beng Chin Ooi, Jiawei Han, Hongjun Lu, Kian-Lee Tan:
Index Nesting - An Efficient Approach to Indexing in Object-Oriented Databases.
VLDB J. 5(3): 215-228(1996)
- Theo Härder, Joachim Reinert:
Access Path Support for Referential Integrity in SQL2.
VLDB J. 5(3): 196-214(1996)
- Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen:
Concurrency Control in B-Trees with Batch Updates.
IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
- Dennis Shasha:
Tuning Databases for High Performance.
ACM Comput. Surv. 28(1): 113-115(1996)
- Esa Falkenroth:
Computational Indexes for Time Series.
SSDBM 1996: 242-251
- Yannis Theodoridis, Timos K. Sellis:
A Model for the Prediction of R-tree Performance.
PODS 1996: 161-171
- Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai:
Efficient Search of Multi-Dimensional B-Trees.
VLDB 1995: 710-719
- Erik G. Hoel, Hanan Samet:
Benchmarking Spatial Join Operations with Spatial Output.
VLDB 1995: 606-618
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573
- Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan:
Index Concurrency Control in Firm Real-Time Database Systems.
VLDB 1995: 146-157
- Georgios Evangelidis, David B. Lomet, Betty Salzberg:
The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation.
VLDB 1995: 551-561
- André Eickler, Carsten Andreas Gerlhof, Donald Kossmann:
A Performance Evaluation of OID Mapping Techniques.
VLDB 1995: 18-29
- Sridhar Ramaswamy, Paris C. Kanellakis:
OODB Indexing by Class-Division.
SIGMOD Conference 1995: 139-150
- Michael Freeston:
A General Solution of the n-dimensional B-tree Problem.
SIGMOD Conference 1995: 80-91
- Paris C. Kanellakis:
Constraint Programming and Database Languages: A Tutorial.
PODS 1995: 46-53
- Theodore W. Leung:
Scheduling Resource Usage in Object-Oriented Queries.
DBPL 1995: 9
- Vram Kouramajian, Ramez Elmasri:
Archiving Techniques for Temporal Databases.
DASFAA 1995: 413-421
- Elisa Bertino:
Index Configuration in Object-Oriented Databases.
VLDB J. 3(3): 355-399(1994)
- Claudio Sartori, Maria Rita Scalas:
Partial Indexing for Nonuniform Data Distributions in relational DBMS's.
IEEE Trans. Knowl. Data Eng. 6(3): 420-429(1994)
- M. V. Ramakrishna:
Bounded Disorder File Organization.
IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
- Akhil Kumar:
G-Tree: A New Data Structure for Organizing Multidimensional Data.
IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
- B. Sreenath, S. Seshadri:
The hcC-tree: An Efficient Index Structure for Object Oriented Databases.
VLDB 1994: 203-213
- V. W. Setzer, Andrea Zisman:
New Concurrency Control Algorithms for Accessing and Compacting B-Trees.
VLDB 1994: 238-248
- Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux:
V-Trees - A Storage Method for Long Vector Data.
VLDB 1994: 321-330
- Hongjun Lu, Beng Chin Ooi, Kian-Lee Tan:
On Spatially Partitioned Temporal Join.
VLDB 1994: 546-557
- Erik G. Hoel, Hanan Samet:
Performance of Data-Parallel Spatial Operations.
VLDB 1994: 156-167
- Sridhar Ramaswamy, Sairam Subramanian:
Path Caching: A Technique for Optimal External Searching.
PODS 1994: 25-35
- Vram Kouramajian, Ramez Elmasri, Anurag Chaudhry:
Declustering Techniques for Parallelizing Temporal Access Structures.
ICDE 1994: 232-242
- V. Srinivasan, Michael J. Carey:
Performance of B+ Tree Concurrency Algorithms.
VLDB J. 2(4): 361-406(1993)
- Gabriel Matsliach:
Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions.
ACM Trans. Database Syst. 18(1): 157-180(1993)
- Yasuaki Nakamura, Shigeru Abe, Yutaka Ohsawa, Masao Sakauchi:
A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics.
IEEE Trans. Knowl. Data Eng. 5(4): 682-694(1993)
- Kikuo Fujimura, Pankaj Jalote:
On Robustness of B-Trees.
IEEE Trans. Knowl. Data Eng. 5(3): 530-534(1993)
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993)
- Theodore Johnson, Padmashree Krishna:
Lazy Updates for Distributed Search Structure.
SIGMOD Conference 1993: 337-346
- Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter:
Indexing for Data Models with Constraints and Classes.
PODS 1993: 233-243
- Chee Chin Low, Beng Chin Ooi, Hongjun Lu:
H-trees: A Dynamic Associative Search Index for OODB.
SIGMOD Conference 1992: 134-143
- Anatoly P. Pinchuk, Konstantin V. Shvachko:
Maintaining Dictionaries: Space-Saving Modifications of B-Trees.
ICDT 1992: 421-435
- Mark Sullivan, Michael A. Olson:
An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System.
ICDE 1992: 293-300
- Ragaa Ishak:
Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring.
ICDE 1992: 184-191
- Ramez Elmasri, Muhammad Jaseemuddin, Vram Kouramajian:
Partitioning of Time Index for Optical Disks.
ICDE 1992: 574-583
- V. Srinivasan, Michael J. Carey:
Performance of On-Line Index Construction Algorithms.
EDBT 1992: 293-309
- Christos Faloutsos, H. V. Jagadish:
Hybrid Index Organizations for Text Databases.
EDBT 1992: 310-327
- Oliver Günther, Jeff Bilmes:
Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation.
IEEE Trans. Knowl. Data Eng. 3(3): 342-356(1991)
- Alexandra Poulovassilis, Carol Small:
A Functional Programming Approach to Deductive Databases.
VLDB 1991: 491-500
- V. Srinivasan, Michael J. Carey:
Performance of B-Tree Concurrency Algorithms.
SIGMOD Conference 1991: 416-425
- Bernhard Seeger, Per-Åke Larson:
Multi-Disk B-trees.
SIGMOD Conference 1991: 436-445
- Sitaram Lanka, Eric Mays:
Fully Persistent B+-trees.
SIGMOD Conference 1991: 426-435
- Gabriel Matsliach:
Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions.
PODS 1991: 164-180
- Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu:
Efficient Implementation Techniques For the Time Index.
ICDE 1991: 102-111
- Pyung-Chul Kim, Hwan-Ik Choi, Yoon-Joon Lee, Myung-Joon Kim:
Design and Implementation of the Multiuser Index-based Data Access System.
DASFAA 1991: 156-164
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990)
- Won Kim, Jorge F. Garza, Nat Ballou, Darrell Woelk:
Architecture of the ORION Next-Generation Database System.
IEEE Trans. Knowl. Data Eng. 2(1): 109-124(1990)
- Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita:
Starburst Mid-Flight: As the Dust Clears.
IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)
- Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim:
The Time Index: An Access Structure for Temporal Data.
VLDB 1990: 1-12
- Gabriel Matsliach, Oded Shmueli:
Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments.
ICDT 1990: 109-125
- Thomas C. Rakow, Junzhong Gu, Erich J. Neuhold:
Serializability in Object-Oriented Database Systems.
ICDE 1990: 112-120
- Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker:
The Generalized Grid File: Description and Performance Aspects.
ICDE 1990: 380-388
- Andreas Heuer, Jürgen Fuchs, U. Wiebking:
OSCAR: An Object-Oriented Database System with a Nested Relational Kernel.
ER 1990: 95-110
- Lothar F. Mackert, Guy M. Lohman:
Index Scans Using a Finite LRU Buffer: A Validated I/O Model.
ACM Trans. Database Syst. 14(3): 401-424(1989)
- Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou:
A Unified Analysis of Batched Searching of Sequential and Tree-Structured Files.
ACM Trans. Database Syst. 14(4): 604-618(1989)
- Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum:
TBSAM: An Access Method for Efficient Processing of Statistical Queries.
IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
- Elisa Bertino, Won Kim:
Indexing Techniques for Queries on Nested Objects.
IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
- Ricardo A. Baeza-Yates, Per-Åke Larson:
Performance of B+-Trees with Partial Expansions.
IEEE Trans. Knowl. Data Eng. 1(2): 248-257(1989)
- Stavros Christodoulakis, Daniel Alexander Ford:
Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs.
SIGMOD Conference 1989: 306-314
- David B. Lomet, Betty Salzberg:
A Robust Multi-Attribute Search Structure.
ICDE 1989: 296-304
- Oliver Günther:
The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases.
ICDE 1989: 598-605
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Dennis Shasha, Nathan Goodman:
Concurrent Search Structure Algorithms.
ACM Trans. Database Syst. 13(1): 53-90(1988)
- Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio:
Physical Database Design for Relational Databases.
ACM Trans. Database Syst. 13(1): 91-128(1988)
- Bernhard Seeger, Hans-Peter Kriegel:
Techniques for Design and Implementation of Efficient Spatial Access Methods.
VLDB 1988: 360-371
- Ratko Orlandic, John L. Pfaltz:
Compact 0-Complete Trees.
VLDB 1988: 372-381
- Jorge F. Garza, Won Kim:
Transaction Management in an Object-Oriented Database System (Invited Paper).
SIGMOD Conference 1988: 37-45
- Edward Omiecinski:
Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File.
ICDE 1988: 589-596
- Jay Banerjee, Won Kim, Kyung-Chang Kim:
Queries in Object-Oriented Databases.
ICDE 1988: 31-38
- Witold Litwin, Djamel Eddine Zegour, Gérard Lévy:
Multilevel Trie Hashing.
EDBT 1988: 309-335
- Patrick Valduriez:
Join Indices.
ACM Trans. Database Syst. 12(2): 218-246(1987)
- Giovanni Maria Sacco:
Index Access with a Finite Buffer.
VLDB 1987: 301-309
- Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood:
Concurrency Control in Database Structures with Relaxed Balance.
PODS 1987: 170-176
- Alexandros Biliris:
Operation Specific Locking in B-Trees.
PODS 1987: 159-169
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - Giovanni Maria Sacco, Mario Schkolnick:
Buffer Management in Relational Database Systems.
ACM Trans. Database Syst. 11(4): 473-498(1986)
- Anil K. Garg, C. C. Gotlieb:
Order-Preserving Key Transformations.
ACM Trans. Database Syst. 11(2): 213-234(1986)
- Tobin J. Lehman, Michael J. Carey:
A Study of Index Structures for Main Memory Database Management Systems.
VLDB 1986: 294-303
- Tobin J. Lehman, Michael J. Carey:
Query Processing in Main Memory Database Management Systems.
SIGMOD Conference 1986: 239-250
- Witold Litwin, David B. Lomet:
The Bounded Disorder Access Method.
ICDE 1986: 38-48
- Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou:
Improving the Differential File Technique via Batch Operations for Tree Structured File Organizations.
ICDE 1986: 524-532
- Mario Schkolnick, Paolo Tiberio:
Estimating the Cost of Updates in a Relational Database.
ACM Trans. Database Syst. 10(2): 163-179(1985)
- Shou-Hsuan Stephen Huang:
Height-Balanced Trees of Order (beta,gamma,delta).
ACM Trans. Database Syst. 10(2): 261-284(1985)
- Don S. Batory:
Modeling the Storage Architectures of Commercial Database Systems.
ACM Trans. Database Syst. 10(4): 463-528(1985)
- Christos Faloutsos:
Access Methods for Text.
ACM Comput. Surv. 17(1): 49-74(1985)
- D. A. Beckley, Martha W. Evens, V. K. Raman:
Multikey Retrieval from K-d Trees and Quad-Trees.
SIGMOD Conference 1985: 291-301
- Hanan Samet:
The Quadtree and Related Hierarchical Data Structures.
ACM Comput. Surv. 16(2): 187-260(1984)
- T. V. Prabhakar, H. V. Sahasrabuddhe:
Towards an Optimal Data-Structure: CB-trees.
VLDB 1984: 235-244
- Patrick Valduriez, Yann Viémont:
A Multikey Hashing Scheme Using Predicate Trees.
SIGMOD Conference 1984: 107-114
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood:
Implementation Techniques for Main Memory Database Systems.
SIGMOD Conference 1984: 1-8
- David M. Arnow, Aaron M. Tenenbaum:
An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees.
SIGMOD Conference 1984: 33-46
- Jack A. Orenstein, T. H. Merrett:
A Class of Data Structures for Associative Searching.
PODS 1984: 181-190
- Motomichi Toyama, Shoji Ura:
Fixed Length Semiorder Preserving Code for Field Level Data File Compression.
ICDE 1984: 244-252
- Tetsuro Ito, Makoto Kizawa:
Hierarchical File Organization and Its Application to Similar-String Matching.
ACM Trans. Database Syst. 8(3): 410-433(1983)
- Michael Stonebraker, Joseph Kalash:
TIMBER: A Sophisticated Relation Browser (Invited Paper).
VLDB 1982: 1-10
- S. Misbah Deen:
An Implementation of Impure Surrogates.
VLDB 1982: 245-256
- Arvola Chan, Sy Danberg, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries:
Storage and Access Structures to Support a Semantic Data Model.
VLDB 1982: 122-130
- David B. Lomet:
Digital B-Trees.
VLDB 1981: 333-344
- Donald D. Chamberlin, A. M. Gilbert, Robert A. Yost:
A History of System R and SQL/Data System (Invited Paper).
VLDB 1981: 456-464
- Leonard J. Bass:
The Access Method Used in a Scientific Data Management System.
SSDBM 1981: 296-297
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18
- Witold Litwin:
Trie Hashing.
SIGMOD Conference 1981: 19-29
- Don S. Batory:
B+ Trees and Indexed Sequential Files: A Performance Comparison.
SIGMOD Conference 1981: 30-39
- Witold Litwin:
Linear Hashing: A New Tool for File and Table Addressing.
VLDB 1980: 212-223
- James E. Allchin, Arthur M. Keller, Gio Wiederhold:
FLASH: A Language-Independent, Portable File Access System.
SIGMOD Conference 1980: 151-156
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:54:41 2009