ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

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

  1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
  2. Till Westmann, Donald Kossmann, Sven Helmer, Guido Moerkotte: The Implementation and Performance of Compressed Databases. SIGMOD Record 29(3): 55-67(2000)
  3. Jun Rao, Kenneth A. Ross: Making B+-Trees Cache Conscious in Main Memory. SIGMOD Conference 2000: 475-486
  4. Nagavamsi Ponnekanti, Hanuma Kodavalla: Online Index Rebuild. SIGMOD Conference 2000: 529-538
  5. 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
  6. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
  7. Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89
  8. Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
  9. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: What can Hierarchies do for Data Warehouses? VLDB 1999: 530-541
  10. Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan: GHOST: Fine Granularity Buffering of Indexes. VLDB 1999: 339-350
  11. 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
  12. Ming-Chuan Wu: Query Optimization for Selections Using Bitmaps. SIGMOD Conference 1999: 227-238
  13. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  14. Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter: On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999: 346-357
  15. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Indexing Constraint Databases by Using a Dual Representation. ICDE 1999: 618-627
  16. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Approximation Techniques for Indexing Two-Dimensional Constraint Databases. DASFAA 1999: 213-220
  17. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  18. 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)
  19. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  20. Guido Moerkotte: Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. VLDB 1998: 476-487
  21. Gísli R. Hjaltason, Hanan Samet: Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998: 237-248
  22. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: The Pyramid-Technique: Towards Breaking the Curse of Dimensionality. SIGMOD Conference 1998: 142-153
  23. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178
  24. Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230
  25. Paul M. Aoki: Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998: 380-389
  26. Yasuaki Nakamura, Hiroyuki Dekihara, Ryo Furukawa: Spatio-Temporal Data Management for Moving Objects Using the PMD-Tree. ER Workshops 1998: 496-507
  27. Elisa Bertino, Barbara Catania, Boris Shidlovsky: Towards Optimal Indexing for Segment Databases. EDBT 1998: 39-53
  28. 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)
  29. 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)
  30. Robert C. Goldstein, Christian Wagner: Database Management with Sequence Trees and Tokens. IEEE Trans. Knowl. Data Eng. 9(1): 186-192(1997)
  31. 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)
  32. Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49
  33. Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant: Range Queries in OLAP Data Cubes. SIGMOD Conference 1997: 73-88
  34. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256
  35. Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431
  36. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
  37. 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)
  38. Theo Härder, Joachim Reinert: Access Path Support for Referential Integrity in SQL2. VLDB J. 5(3): 196-214(1996)
  39. 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)
  40. Dennis Shasha: Tuning Databases for High Performance. ACM Comput. Surv. 28(1): 113-115(1996)
  41. Esa Falkenroth: Computational Indexes for Time Series. SSDBM 1996: 242-251
  42. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
  43. Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB 1995: 710-719
  44. Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618
  45. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573
  46. Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan: Index Concurrency Control in Firm Real-Time Database Systems. VLDB 1995: 146-157
  47. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561
  48. André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
  49. Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150
  50. Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91
  51. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  52. Theodore W. Leung: Scheduling Resource Usage in Object-Oriented Queries. DBPL 1995: 9
  53. Vram Kouramajian, Ramez Elmasri: Archiving Techniques for Temporal Databases. DASFAA 1995: 413-421
  54. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
  55. 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)
  56. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
  57. Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
  58. B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213
  59. V. W. Setzer, Andrea Zisman: New Concurrency Control Algorithms for Accessing and Compacting B-Trees. VLDB 1994: 238-248
  60. Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330
  61. Hongjun Lu, Beng Chin Ooi, Kian-Lee Tan: On Spatially Partitioned Temporal Join. VLDB 1994: 546-557
  62. Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167
  63. Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35
  64. Vram Kouramajian, Ramez Elmasri, Anurag Chaudhry: Declustering Techniques for Parallelizing Temporal Access Structures. ICDE 1994: 232-242
  65. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
  66. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
  67. 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)
  68. Kikuo Fujimura, Pankaj Jalote: On Robustness of B-Trees. IEEE Trans. Knowl. Data Eng. 5(3): 530-534(1993)
  69. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  70. Theodore Johnson, Padmashree Krishna: Lazy Updates for Distributed Search Structure. SIGMOD Conference 1993: 337-346
  71. Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243
  72. Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143
  73. Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435
  74. Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300
  75. Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. ICDE 1992: 184-191
  76. Ramez Elmasri, Muhammad Jaseemuddin, Vram Kouramajian: Partitioning of Time Index for Optical Disks. ICDE 1992: 574-583
  77. V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309
  78. Christos Faloutsos, H. V. Jagadish: Hybrid Index Organizations for Text Databases. EDBT 1992: 310-327
  79. 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)
  80. Alexandra Poulovassilis, Carol Small: A Functional Programming Approach to Deductive Databases. VLDB 1991: 491-500
  81. V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
  82. Bernhard Seeger, Per-Åke Larson: Multi-Disk B-trees. SIGMOD Conference 1991: 436-445
  83. Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435
  84. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
  85. Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu: Efficient Implementation Techniques For the Time Index. ICDE 1991: 102-111
  86. 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
  87. 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)
  88. 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)
  89. 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)
  90. Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1-12
  91. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  92. Thomas C. Rakow, Junzhong Gu, Erich J. Neuhold: Serializability in Object-Oriented Database Systems. ICDE 1990: 112-120
  93. Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388
  94. Andreas Heuer, Jürgen Fuchs, U. Wiebking: OSCAR: An Object-Oriented Database System with a Nested Relational Kernel. ER 1990: 95-110
  95. 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)
  96. 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)
  97. 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)
  98. Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
  99. Ricardo A. Baeza-Yates, Per-Åke Larson: Performance of B+-Trees with Partial Expansions. IEEE Trans. Knowl. Data Eng. 1(2): 248-257(1989)
  100. Stavros Christodoulakis, Daniel Alexander Ford: Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs. SIGMOD Conference 1989: 306-314
  101. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
  102. Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605
  103. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  104. Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
  105. Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
  106. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
  107. Ratko Orlandic, John L. Pfaltz: Compact 0-Complete Trees. VLDB 1988: 372-381
  108. Jorge F. Garza, Won Kim: Transaction Management in an Object-Oriented Database System (Invited Paper). SIGMOD Conference 1988: 37-45
  109. Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596
  110. Jay Banerjee, Won Kim, Kyung-Chang Kim: Queries in Object-Oriented Databases. ICDE 1988: 31-38
  111. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  112. Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
  113. Giovanni Maria Sacco: Index Access with a Finite Buffer. VLDB 1987: 301-309
  114. Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood: Concurrency Control in Database Structures with Relaxed Balance. PODS 1987: 170-176
  115. Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169
  116. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  117. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
  118. Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)
  119. Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303
  120. Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
  121. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
  122. 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
  123. Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985)
  124. Shou-Hsuan Stephen Huang: Height-Balanced Trees of Order (beta,gamma,delta). ACM Trans. Database Syst. 10(2): 261-284(1985)
  125. Don S. Batory: Modeling the Storage Architectures of Commercial Database Systems. ACM Trans. Database Syst. 10(4): 463-528(1985)
  126. Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985)
  127. D. A. Beckley, Martha W. Evens, V. K. Raman: Multikey Retrieval from K-d Trees and Quad-Trees. SIGMOD Conference 1985: 291-301
  128. Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
  129. T. V. Prabhakar, H. V. Sahasrabuddhe: Towards an Optimal Data-Structure: CB-trees. VLDB 1984: 235-244
  130. Patrick Valduriez, Yann Viémont: A Multikey Hashing Scheme Using Predicate Trees. SIGMOD Conference 1984: 107-114
  131. Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
  132. 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
  133. David M. Arnow, Aaron M. Tenenbaum: An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees. SIGMOD Conference 1984: 33-46
  134. Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
  135. Motomichi Toyama, Shoji Ura: Fixed Length Semiorder Preserving Code for Field Level Data File Compression. ICDE 1984: 244-252
  136. Tetsuro Ito, Makoto Kizawa: Hierarchical File Organization and Its Application to Similar-String Matching. ACM Trans. Database Syst. 8(3): 410-433(1983)
  137. Michael Stonebraker, Joseph Kalash: TIMBER: A Sophisticated Relation Browser (Invited Paper). VLDB 1982: 1-10
  138. S. Misbah Deen: An Implementation of Impure Surrogates. VLDB 1982: 245-256
  139. 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
  140. David B. Lomet: Digital B-Trees. VLDB 1981: 333-344
  141. Donald D. Chamberlin, A. M. Gilbert, Robert A. Yost: A History of System R and SQL/Data System (Invited Paper). VLDB 1981: 456-464
  142. Leonard J. Bass: The Access Method Used in a Scientific Data Management System. SSDBM 1981: 296-297
  143. John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18
  144. Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
  145. Don S. Batory: B+ Trees and Indexed Sequential Files: A Performance Comparison. SIGMOD Conference 1981: 30-39
  146. Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
  147. 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