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.00010277834
Overall Rank
1,543 | 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,384
PLP: Page Latch-free Shared-everything OLTP 2011
VLDB
0.00010824715
1,500
Multi-Tenant Databases for Software as a Service: Schema-Mapping Techniques 2008
SIGMOD
0.00010434847
1,637
Positional Update Handling in Column Stores 2010
SIGMOD
9.9898497e-05
1,770
Write-Optimized B-Trees 2004
VLDB
9.6795618e-05
2,905
Rose: Compressed, log-structured replication 2008
VLDB
7.871271e-05
3,965
Cracking the Database Store 2005
CIDR
6.878328e-05
4,897
Design Tradeoffs of Data Access Methods 2016
SIGMOD
6.3489205e-05
5,651
MaSM: Efficient Online Updates in Data Warehouses 2011
SIGMOD
6.0346713e-05
5,839
Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013
VLDB
5.957817e-05
6,013
Concurrency Control for Adaptive Indexing 2012
VLDB
5.8958102e-05
6,507
FineLine: Log-structured Transactional Storage and Recovery 2018
VLDB
5.7453056e-05
6,543
Contention and Space Management in B-Trees 2021
CIDR
5.733215e-05
7,645
Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007
SIGMOD
5.4613959e-05
7,979
Online B-Tree Merging 2005
SIGMOD
5.3978271e-05
8,373
Resumable Online Index Rebuild in SQL Server 2017
VLDB
5.3282795e-05
8,828
A Batch of PNUTS: Experiences Connecting Cloud Batch and Serving Systems 2011
SIGMOD
5.2534605e-05
9,297
A SQL:1999 Code Generator for the Pathfinder XQuery Compiler 2007
SIGMOD
5.1860131e-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.00039478403
89
Automated Selection of Materialized Views and Indexes for SQL Databases 2000
VLDB
0.00035265687
194
Data Placement In Bubba 1988
SIGMOD
0.00025627096
818
Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998
VLDB
0.00013657405
956
Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992
SIGMOD
0.00012845453
969
Incremental Organization for Data Recording and Warehousing 1997
VLDB
0.00012755618
1,824
Memory Management during Run Generation in External Sorting 1998
SIGMOD
9.545532e-05
2,211
Integrating the UB-Tree into a Database System Kernel 2000
VLDB
8.8443254e-05
2,443
A Novel Index Supporting High Volume Data Warehouse Insertions 1999
VLDB
8.4468451e-05
2,853
Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm 2002
VLDB
7.9179824e-05
3,492
Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases 1996
SIGMOD
7.2390768e-05
3,518
Towards Self-Tuning Data Placement in Parallel Database Systems 2000
SIGMOD
7.2204376e-05
4,490
Memory-Adaptive External Sorting 1993
VLDB
6.5618088e-05
4,677
Dynamic Memory Adjustment for External Mergesort 1997
VLDB
6.4575536e-05
8,646
Buffering and Read-Ahead Strategies for External Mergesort 1998
VLDB
5.2817166e-05
Semantically Similar Papers