Back to papers
Sorting And Indexing With Partitioned B-Trees
Summary: Partitioned B‑trees (add artificial leading key + online reorg) unify sorting and indexing, enabling accurate deep read‑ahead and dynamic resource allocation during external merge sort. Delivers faster usable index creation and streaming loads into fully indexed DBs using only standard RDBMS primitives.
(summarized by gpt-5-mini on Feb 09 2026)
Paper ID
1
Venue
CIDR
Year
2003
Pagerank
0.00010540965
Overall Rank
1,508 | 89.66%
DOI
-
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{graefe_cidr03,
address = {Amsterdam, Netherlands},
series = {{CIDR} '03},
title = {{Sorting And Indexing With Partitioned B-Trees}},
booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
author = {Graefe, Goetz},
year = {2003}
}
Incoming Citations (Sorted by Pagerank)
Showing 17 of 17 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
1,358
PLP: Page Latch-free Shared-everything OLTP 2011
VLDB
0.0001104203
1,477
Multi-Tenant Databases for Software as a Service: Schema-Mapping Techniques 2008
SIGMOD
0.00010654969
1,629
Positional Update Handling in Column Stores 2010
SIGMOD
0.00010184131
1,731
Write-Optimized B-Trees 2004
VLDB
9.9081882e-05
2,843
Rose: Compressed, log-structured replication 2008
VLDB
8.0617003e-05
3,876
Cracking the Database Store 2005
CIDR
7.0544298e-05
4,826
Design Tradeoffs of Data Access Methods 2016
SIGMOD
6.4904836e-05
5,564
MaSM: Efficient Online Updates in Data Warehouses 2011
SIGMOD
6.1716245e-05
5,715
Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013
VLDB
6.1105343e-05
5,903
Concurrency Control for Adaptive Indexing 2012
VLDB
6.0464632e-05
6,396
Contention and Space Management in B-Trees 2021
CIDR
5.8870425e-05
6,512
FineLine: Log-structured Transactional Storage and Recovery 2018
VLDB
5.8563029e-05
7,486
Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007
SIGMOD
5.6073128e-05
7,804
Online B-Tree Merging 2005
SIGMOD
5.5415082e-05
8,194
Resumable Online Index Rebuild in SQL Server 2017
VLDB
5.469529e-05
8,642
A Batch of PNUTS: Experiences Connecting Cloud Batch and Serving Systems 2011
SIGMOD
5.3942591e-05
9,090
A SQL:1999 Code Generator for the Pathfinder XQuery Compiler 2007
SIGMOD
5.3251649e-05
Outgoing Citations (Sorted by Pagerank)
Showing 15 of 15 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
59
Differential Files: Their Application To The Maintenance Of Large Data Bases 1976
SIGMOD
0.00040060625
87
Automated Selection of Materialized Views and Indexes for SQL Databases 2000
VLDB
0.00035281619
188
Data Placement In Bubba 1988
SIGMOD
0.00026126036
807
Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998
VLDB
0.00013884448
924
Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992
SIGMOD
0.00013185068
981
Incremental Organization for Data Recording and Warehousing 1997
VLDB
0.0001284025
1,801
Memory Management during Run Generation in External Sorting 1998
SIGMOD
9.7286236e-05
2,155
Integrating the UB-Tree into a Database System Kernel 2000
VLDB
9.0713545e-05
2,396
A Novel Index Supporting High Volume Data Warehouse Insertions 1999
VLDB
8.6345567e-05
2,787
Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm 2002
VLDB
8.1205738e-05
3,416
Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases 1996
SIGMOD
7.430628e-05
3,454
Towards Self-Tuning Data Placement in Parallel Database Systems 2000
SIGMOD
7.4001286e-05
4,708
Memory-Adaptive External Sorting 1993
VLDB
6.5519325e-05
4,955
Dynamic Memory Adjustment for External Mergesort 1997
VLDB
6.4297637e-05
8,451
Buffering and Read-Ahead Strategies for External Mergesort 1998
VLDB
5.4230411e-05
Semantically Similar Papers