Database Paper Browser

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.00011516282
Overall Rank
1,524 | 89.40%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
1,216 Multi-Tenant Databases for Software as a Service: Schema-Mapping Techniques 2008 SIGMOD 0.00013232841
1,480 Write-Optimized B-Trees 2004 VLDB 0.00011746722
1,603 PLP: Page Latch-free Shared-everything OLTP 2011 VLDB 0.00011196902
1,949 Positional Update Handling in Column Stores 2010 SIGMOD 9.9864085e-05
2,558 Rose: Compressed, log-structured replication 2008 VLDB 8.5455497e-05
4,108 Cracking the Database Store 2005 CIDR 6.4440088e-05
5,119 Design Tradeoffs of Data Access Methods 2016 SIGMOD 5.6807904e-05
5,604 Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases 2013 VLDB 5.4147933e-05
5,848 MaSM: Efficient Online Updates in Data Warehouses 2011 SIGMOD 5.3021155e-05
6,201 Concurrency Control for Adaptive Indexing 2012 VLDB 5.1600319e-05
6,772 FineLine: Log-structured Transactional Storage and Recovery 2018 VLDB 4.9313122e-05
7,200 Online B-Tree Merging 2005 SIGMOD 4.8030945e-05
7,639 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 4.6904624e-05
8,049 Contention and Space Management in B-Trees 2021 CIDR 4.5973972e-05
8,106 Resumable Online Index Rebuild in SQL Server 2017 VLDB 4.5847706e-05
8,413 A Batch of PNUTS: Experiences Connecting Cloud Batch and Serving Systems 2011 SIGMOD 4.5203012e-05
8,934 A SQL:1999 Code Generator for the Pathfinder XQuery Compiler 2007 SIGMOD 4.427232e-05
Previous Page 1 / 1 Next

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
32 Differential Files: Their Application To The Maintenance Of Large Data Bases 1976 SIGMOD 0.00077486306
158 Automated Selection of Materialized Views and Indexes for SQL Databases 2000 VLDB 0.00040071492
197 Data Placement In Bubba 1988 SIGMOD 0.00035201758
823 Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998 VLDB 0.000162378
875 Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992 SIGMOD 0.00015719411
1,077 Incremental Organization for Data Recording and Warehousing 1997 VLDB 0.00014247204
1,290 Memory Management during Run Generation in External Sorting 1998 SIGMOD 0.00012795586
2,396 A Novel Index Supporting High Volume Data Warehouse Insertions 1999 VLDB 8.8997169e-05
2,502 Integrating the UB-Tree into a Database System Kernel 2000 VLDB 8.6438339e-05
3,204 Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm 2002 VLDB 7.3889212e-05
3,401 Towards Self-Tuning Data Placement in Parallel Database Systems 2000 SIGMOD 7.1400085e-05
3,428 Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases 1996 SIGMOD 7.1029689e-05
4,741 Memory-Adaptive External Sorting 1993 VLDB 5.95905e-05
4,832 Dynamic Memory Adjustment for External Mergesort 1997 VLDB 5.8924168e-05
8,004 Buffering and Read-Ahead Strategies for External Mergesort 1998 VLDB 4.6085722e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,607 A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort 2014 SIGMOD 0.00011162682
9,404 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 4.3441378e-05
4,741 Memory-Adaptive External Sorting 1993 VLDB 5.95905e-05
13,073 Experiments With B-Tree Reorganization 1980 SIGMOD 4.1945683e-05
4,672 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.0085156e-05
7,460 A Study of Sort Algorithms for Multiprocessor Database Machines 1986 VLDB 4.7241128e-05
1,774 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010604097
7,200 Online B-Tree Merging 2005 SIGMOD 4.8030945e-05
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05
875 Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates 1992 SIGMOD 0.00015719411