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.0061967e-05
Overall Rank: 2,791 | 81.25%
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,691	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	9.8555388e-05
1,757	Write-Optimized B-Trees	2004	VLDB	9.7107503e-05
1,856	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory	2020	VLDB	9.4960518e-05
2,658	Lazy Updates for Distributed Search Structure	1993	SIGMOD	8.1597547e-05
2,880	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.9118308e-05
5,662	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0448437e-05
6,532	Contention and Space Management in B-Trees	2021	CIDR	5.7522354e-05
8,082	Buffered Persistence in B+ Trees	2024	SIGMOD	5.3917406e-05
11,561	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	4.9769913e-05
12,654	No Bits Left Behind	2011	CIDR	4.9769913e-05
13,063	Transaction support for indexed summary views	2004	SIGMOD	4.9769913e-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,332	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
2	9,559	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
3	6,532	Contention and Space Management in B-Trees	2021	CIDR
4	3,079	The Performance Of A Multiversion Access Method	1990	SIGMOD
5	14,329	Relaxed Multi-Way Trees with Group Updates	2001	PODS
6	472	Concurrent Operations on B-Trees with Overtaking	1985	PODS
7	1,691	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
8	5,662	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
9	13,570	Experiments With B-Tree Reorganization	1980	SIGMOD
10	10,378	Bounding the Fragmentation of B-Trees Subject to Batched Insertions	2026	PODS