Utilization of B-trees with Inserts, Deletes and Modifies

Summary: Extends Yao-style analysis to B-tree equilibrium under parameterized mixes of inserts and deletes (modifies as delete+insert), deriving per-level split/merge probabilities and accounting for intra-node "ghost" items. Shows utilization can fall to ~39% for heavy modify workloads, gives a rule-of-thumb for split probability and two analytical models (one more accurate by modeling ghosted items). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hda3a77a2ac52a585
Venue: PODS
Year: 1989
Pagerank: 8.009544e-05
Overall Rank: 2,791 | 81.24%
DOI: 10.1145/73721.73745

Incoming Non-self Citations Over Time

Authors

1. Theodore Johnson (New York University)
2. Dennis Shasha (New York University)

BibTeX Citation

@inproceedings{johnson_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Utilization of B-trees with Inserts, Deletes and Modifies}},
        url = {https://dl.acm.org/doi/10.1145/73721.73745},
        doi = {10.1145/73721.73745},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Johnson, Theodore and Shasha, Dennis},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,692	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	9.8570044e-05
1,757	Write-Optimized B-Trees	2004	VLDB	9.7131504e-05
1,854	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory	2020	VLDB	9.4991601e-05
2,658	Lazy Updates for Distributed Search Structure	1993	SIGMOD	8.1636113e-05
2,882	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.9116043e-05
5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0475065e-05
6,530	Contention and Space Management in B-Trees	2021	CIDR	5.7549598e-05
8,075	Buffered Persistence in B+ Trees	2024	SIGMOD	5.3942942e-05
11,555	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	4.9793485e-05
12,648	No Bits Left Behind	2011	CIDR	4.9793485e-05
13,057	Transaction support for indexed summary views	2004	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,326	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
2	9,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
3	6,530	Contention and Space Management in B-Trees	2021	CIDR
4	3,077	The Performance Of A Multiversion Access Method	1990	SIGMOD
5	14,324	Relaxed Multi-Way Trees with Group Updates	2001	PODS
6	471	Concurrent Operations on B-Trees with Overtaking	1985	PODS
7	1,692	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
8	5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
9	13,564	Experiments With B-Tree Reorganization	1980	SIGMOD
10	10,366	Bounding the Fragmentation of B-Trees Subject to Batched Insertions	2026	PODS