B-Tree

The Original Publication

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

A Well-Known Survey

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

Concurrency Control

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

Space Utilization

Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495 BibTeX
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) BibTeX
Klaus Küspert: Storage Utilization in B*-Trees with a Generalized Overflow Technique. Acta Inf. 19: 35-55(1983) BibTeX
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) BibTeX
Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246 BibTeX

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) BibTeX
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 BibTeX
Arnold L. Rosenberg, Lawrence Snyder: Compact B-Trees. SIGMOD Conference 1979: 43-51 BibTeX

1980

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

1981

Arnold L. Rosenberg, Lawrence Snyder: Time- and Space-Optimality in B-Trees. ACM Trans. Database Syst. 6(1): 174-193(1981) BibTeX , 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) BibTeX

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) BibTeX
U. I. Gupta, D. T. Lee, C. K. Wong: Ranking and Unranking of B-Trees. J. Algorithms 4(1): 51-60(1983) BibTeX

1984

David M. Arnow, Aaron M. Tenenbaum: An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees. SIGMOD Conference 1984: 33-46 BibTeX
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) BibTeX

1988

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

1989

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

1990

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

1991

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

1992

Christos Faloutsos, H. V. Jagadish: On B-Tree Indices for Skewed Distributions. VLDB 1992: 363-374 BibTeX
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 BibTeX
C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370 BibTeX
Patrick E. O'Neil: The SB-Tree: An Index-Sequential Structure for High-Performance Sequential Access. Acta Inf. 29(3): 241-265(1992) BibTeX
Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. ICDE 1992: 184-191 BibTeX
Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300 BibTeX
Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435 BibTeX
V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309 BibTeX

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) BibTeX
Kikuo Fujimura, Pankaj Jalote: On Robustness of B-Trees. IEEE Trans. Knowl. Data Eng. 5(3): 530-534(1993) BibTeX

1995

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

The software described in these articles is available on http://www-db.stanford.edu:80/pub/jannink/btree/.

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

The Generalized Search Tree (GiST) is a generalization of B+-Trees which can be adapted to work like R-Trees or a varity of other search tree data structures.

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) BibTeX