B-Tree

The Original Publication

• Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)

A Well-Known Survey

• Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)

Concurrency Control

• Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976)
• Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977)
• Yat-Sang Kwong, Derick Wood: Concurrent Operations in Large Ordered Indices. LNCS 83: 207-222 (1980)
• Yat-Sang Kwong, Derick Wood: Approaches to Concurrency in B-Trees. MFCS 1980: 402-413
• Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86(1980)
• Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
• Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982)
• Georg Lausen: Integrated Concurrency Control in Shared B-Trees. Computing 33(1): 13-26(1984)
• Martin L. Kersten, Hans Tebra: Application of an Optimistic Concurrency Control Method. Softw., Pract. Exper. 14(2): 153-168(1984)
• Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334
• Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 , journal version: J. Comput. Syst. Sci. 33(2): 275-296(1986)
• Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19
• Dennis Shasha: What Good are Concurrent Search Structure Algorithms for databases Anyway? IEEE Database Eng. Bull. 8(2): 84-90(1985)
• Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389
• Alexandros Biliris: A Comparative Study of Concurrency Control Methods in B-Trees. Aegean Workshop on Computing 1986: 305-316
• Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169
• Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood: Concurrency Control in Database Structures with Relaxed Balance. PODS 1987: 170-176
• Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285
• Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
• C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
• V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
• Thomas Eiter, Michael Schrefl, Markus Stumptner: Sperrverfahren für B-Bäume im Vergleich. Informatik Spektrum 14(4): 183-200(1991)
• David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
• C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
• Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
• V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
• V. W. Setzer, Andrea Zisman: New Concurrency Control Algorithms for Accessing and Compacting B-Trees. VLDB 1994: 238-248
• 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)

Space Utilization

• Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495
• Bernhard Eisenbarth, Nivio Ziviani, Gaston H. Gonnet, Kurt Mehlhorn, Derick Wood: The Theory of Fringe Analysis and Its Application to 2-3 Trees and B-Trees. Information and Control 55(1-3): 125-174(1982)
• Klaus Küspert: Storage Utilization in B*-Trees with a Generalized Overflow Technique. Acta Inf. 19: 35-55(1983)
• Clement Leung: Approximate Storage Utilisation of B-Trees: A Simple Derivation and Generalisation. Information Processing Letters 19(4): 199-201 (1984)
• Ricardo A. Baeza-Yates, Per-Åke Larson: Performance of B+-Trees with Partial Expansions. IEEE Trans. Knowl. Data Eng. 1(2): 248-257(1989)
• Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246

1970

• Vincent Y. Lum: Multi-Attribute Retrieval with combined Indexes. CACM 13(11): 660-665 (1970)

1977

• Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977)
• Edward M. McCreight: Pagination of B*-Trees with Variable-Length Records. CACM 20(9): 670-674 (1977)

1978

• Gerald Held, Michael Stonebraker: B-trees Re-examined. CACM 21(2): 139-143 (1977)
• Lawrence Snyder: On B-trees Re-examined. CACM 21(7): 594 (1977)

1979

• David B. Lomet: Multi-Table Search for B-Tree Files. SIGMOD Conference 1979: 35-42
• Arnold L. Rosenberg, Lawrence Snyder: Compact B-Trees. SIGMOD Conference 1979: 43-51

1980

• Yat-Sang Kwong, Derick Wood: On B-Trees: Routing Schemes and Concurrency. SIGMOD Conference 1980: 207-211

1981

• Arnold L. Rosenberg, Lawrence Snyder: Time- and Space-Optimality in B-Trees. ACM Trans. Database Syst. 6(1): 174-193(1981) , see comments in SIGMOD Record 13(2): 35-38
• Mohamed Ouksel, Peter Scheuermann: Multidimensional B-Trees: Analysis of Dynamic Behavior. BIT 21: 401-418 (1981)

1982

• Peter Scheuermann, Aris M. Ouksel: Multidimensional B-trees for associative searching in database systems. Inf. Syst. 7(2): 123-137(1982)

1983

• Nguyen Hoan Phuc, M. Becker, P. Sevray: Performance Comparison Between B*-Tree and Prefix Binary Tree Index Organizations. ICOD 1983: 358-376
• David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
• U. I. Gupta, D. T. Lee, C. K. Wong: Ranking and Unranking of B-Trees. J. Algorithms 4(1): 51-60(1983)

1984

• David M. Arnow, Aaron M. Tenenbaum: An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees. SIGMOD Conference 1984: 33-46
• George Diehr, Bruce Faaland: Optimal Pagination of B-Trees with Variable-Length Items. CACM 27(3): 241-247 (1984)
• Gopal K. Gupta: A Self-Assessment Procedure Dealing with Binary Trees and B-Trees. CACM 27(5): 435-443 (1984)

1985

• Jeffrey R. Spirn, Shalom Tsur: Memory Management for B-Trees. Performance Evaluation 4: 159-174 (1985)
• Klaus Küspert: Quantitative Bewertung Fehlertoleranter B*-Baum-Implementierungen in Datenbanksystemen durch Simulationsreihen. MMBR 1985: 202-216
• William E. Wright: Some Average Performance Measures for the B-Tree. Acta Inf. 21: 541-557(1985)

1988

• Arthur M. Keller, Gio Wiederhold: Concurrent Use of B-trees with Variable-Length Entries. SIGMOD Record 17(2): 89-90(1988)
• Jaideep Srivastava, C. V. Ramamoorthy: Efficient Algorithms for Maintenance of Large Database. ICDE 1988: 402-408

1989

• Ricardo A. Baeza-Yates: Modeling Splits in File Structures. Acta Inf. 26(4): 349-362(1989)
• Bin Zhang, Meichun Hsu: Unsafe Operations in B-Trees. Acta Inf. 26(5): 421-438(1989)
• Ricardo A. Baeza-Yates: The Expected Behaviour of B+-Trees. Acta Inf. 26(5): 439-471(1989)
• Carl Langenhop, William E. Wright: A Model of the Dynamic Behavior of B-Trees. Acta Inf. 27(1): 41-59(1989)
• Frank Olken, Doron Rotem: Random Sampling from B+ Trees. VLDB 1989: 269-277
• Jiang-Hsing Chu, Gary D. Knott: An Analysis of B-trees and their Variants. Inf. Syst. 14(5): 359-370(1989)

1990

• Thomas Hardjono, Jennifer Seberry: Search Key Substitution in the Encipherment of B-Trees. VLDB 1990: 50-58
• Ricardo A. Baeza-Yates: An Adaptive Overflow Technique for B-trees. EDBT 1990: 16-28
• William Boswell, Alan L. Tharp: Alternatives to the B+-Tree. ICCI 1990: 266-274

1991

• Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435
• Bernhard Seeger, Per-Åke Larson: Multi-Disk B-trees. SIGMOD Conference 1991: 436-445
• Alan L. Tharp, William Boswell: B+ Trees, Bounded Disorder and Adaptive Hashing. Inf. Syst. 16(1): 65-71(1991)

1992

• Christos Faloutsos, H. V. Jagadish: On B-Tree Indices for Skewed Distributions. VLDB 1992: 363-374
• David E. Ferguson: Bit-Tree, A Data Structure for Fast File Processing. CACM 35(6): 114-120 (June 1992)
• Gennady Antoshenkov: Random Sampling from Pseudo-Ranked B+ Trees. VLDB 1992: 375-382
• C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370
• Patrick E. O'Neil: The SB-Tree: An Index-Sequential Structure for High-Performance Sequential Access. Acta Inf. 29(3): 241-265(1992)
• Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. ICDE 1992: 184-191
• Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300
• Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435
• V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309

1993

• Theodore Johnson, Dennis Shasha: B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half. J. Comput. Syst. Sci. 47(1): 45-76(1993)
• Kikuo Fujimura, Pankaj Jalote: On Robustness of B-Trees. IEEE Trans. Knowl. Data Eng. 5(3): 530-534(1993)

1995

• Jan Jannink: Implementing Deletion in B+-Trees. SIGMOD Record 24(1): 33-38(1995)
• R. Maelbrancke, H. Olivie: Optimizing Jan Jannink's Implementation of B+-tree Deletion. SIGMOD Record 24(3): 5-7(1995)

• Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573

1996

• Cheng Hian Goh, Hongjun Lu, Beng Chin Ooi, Kian-Lee Tan: Indexing Temporal Data Using Existing B+-Trees. Data Knowl. Eng. 18(2): 147-165(1996)

Last update Thu Nov 29 03:58:26 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page