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
hbec8b49fb56df47a
Venue
CIDR
Year
2003
Pagerank
0.00010311314
Overall Rank
1,540 | 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,382
PLP: Page Latch-free Shared-everything OLTP 2011
VLDB
0.0001085396
1,499
Multi-Tenant Databases for Software as a Service: Schema-Mapping Techniques 2008
SIGMOD
0.00010467167
1,631
Positional Update Handling in Column Stores 2010
SIGMOD
0.00010019069
1,757
Write-Optimized B-Trees 2004
VLDB
9.7107503e-05
2,894
Rose: Compressed, log-structured replication 2008
VLDB
7.8968405e-05
3,952
Cracking the Database Store 2005
CIDR
6.9006859e-05
4,875
Design Tradeoffs of Data Access Methods 2016
SIGMOD
6.3699172e-05
5,640
MaSM: Efficient Online Updates in Data Warehouses 2011
SIGMOD
6.0541838e-05
5,827
Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013
VLDB
5.9772416e-05
6,005
Concurrency Control for Adaptive Indexing 2012
VLDB
5.9137728e-05
6,495
FineLine: Log-structured Transactional Storage and Recovery 2018
VLDB
5.7640595e-05
6,532
Contention and Space Management in B-Trees 2021
CIDR
5.7522354e-05
7,630
Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007
SIGMOD
5.4795145e-05
7,962
Online B-Tree Merging 2005
SIGMOD
5.4157047e-05
8,358
Resumable Online Index Rebuild in SQL Server 2017
VLDB
5.3459276e-05
8,811
A Batch of PNUTS: Experiences Connecting Cloud Batch and Serving Systems 2011
SIGMOD
5.2708766e-05
9,273
A SQL:1999 Code Generator for the Pathfinder XQuery Compiler 2007
SIGMOD
5.2032182e-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.00039592759
88
Automated Selection of Materialized Views and Indexes for SQL Databases 2000
VLDB
0.00035340164
192
Data Placement In Bubba 1988
SIGMOD
0.00025689465
816
Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998
VLDB
0.00013686255
951
Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992
SIGMOD
0.00012887578
968
Incremental Organization for Data Recording and Warehousing 1997
VLDB
0.00012793641
1,823
Memory Management during Run Generation in External Sorting 1998
SIGMOD
9.5571894e-05
2,199
Integrating the UB-Tree into a Database System Kernel 2000
VLDB
8.8732148e-05
2,433
A Novel Index Supporting High Volume Data Warehouse Insertions 1999
VLDB
8.4740186e-05
2,845
Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm 2002
VLDB
7.9439702e-05
3,483
Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases 1996
SIGMOD
7.2628249e-05
3,511
Towards Self-Tuning Data Placement in Parallel Database Systems 2000
SIGMOD
7.2414794e-05
4,471
Memory-Adaptive External Sorting 1993
VLDB
6.5823759e-05
4,694
Dynamic Memory Adjustment for External Mergesort 1997
VLDB
6.4643405e-05
8,626
Buffering and Read-Ahead Strategies for External Mergesort 1998
VLDB
5.2992199e-05
Semantically Similar Papers