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.00010316015
Overall Rank
1,539 | 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.00010858298
1,499
Multi-Tenant Databases for Software as a Service: Schema-Mapping Techniques 2008
SIGMOD
0.00010471977
1,632
Positional Update Handling in Column Stores 2010
SIGMOD
0.00010021251
1,757
Write-Optimized B-Trees 2004
VLDB
9.7131504e-05
2,894
Rose: Compressed, log-structured replication 2008
VLDB
7.9005767e-05
3,951
Cracking the Database Store 2005
CIDR
6.9039096e-05
4,885
Design Tradeoffs of Data Access Methods 2016
SIGMOD
6.3706825e-05
5,637
MaSM: Efficient Online Updates in Data Warehouses 2011
SIGMOD
6.0569403e-05
5,827
Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013
VLDB
5.979772e-05
6,005
Concurrency Control for Adaptive Indexing 2012
VLDB
5.9164805e-05
6,494
FineLine: Log-structured Transactional Storage and Recovery 2018
VLDB
5.7659228e-05
6,530
Contention and Space Management in B-Trees 2021
CIDR
5.7549598e-05
7,624
Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007
SIGMOD
5.4821096e-05
7,958
Online B-Tree Merging 2005
SIGMOD
5.4182694e-05
8,353
Resumable Online Index Rebuild in SQL Server 2017
VLDB
5.3484595e-05
8,803
A Batch of PNUTS: Experiences Connecting Cloud Batch and Serving Systems 2011
SIGMOD
5.2733728e-05
9,263
A SQL:1999 Code Generator for the Pathfinder XQuery Compiler 2007
SIGMOD
5.2056825e-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.00039605949
88
Automated Selection of Materialized Views and Indexes for SQL Databases 2000
VLDB
0.00035351639
191
Data Placement In Bubba 1988
SIGMOD
0.00025700375
815
Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998
VLDB
0.00013689839
951
Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992
SIGMOD
0.00012893557
966
Incremental Organization for Data Recording and Warehousing 1997
VLDB
0.0001279879
1,823
Memory Management during Run Generation in External Sorting 1998
SIGMOD
9.5606648e-05
2,198
Integrating the UB-Tree into a Database System Kernel 2000
VLDB
8.8759215e-05
2,431
A Novel Index Supporting High Volume Data Warehouse Insertions 1999
VLDB
8.4776498e-05
2,845
Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm 2002
VLDB
7.9474809e-05
3,482
Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases 1996
SIGMOD
7.2662396e-05
3,511
Towards Self-Tuning Data Placement in Parallel Database Systems 2000
SIGMOD
7.244841e-05
4,469
Memory-Adaptive External Sorting 1993
VLDB
6.5854799e-05
4,692
Dynamic Memory Adjustment for External Mergesort 1997
VLDB
6.4673313e-05
8,617
Buffering and Read-Ahead Strategies for External Mergesort 1998
VLDB
5.3017239e-05
Semantically Similar Papers