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: 868
Venue: PODS
Year: 1989
Pagerank: 8.1875737e-05
Overall Rank: 2,738 | 81.22%
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,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00010073735
1,731	Write-Optimized B-Trees	2004	VLDB	9.9081882e-05
1,823	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory	2020	VLDB	9.6739945e-05
2,605	Lazy Updates for Distributed Search Structure	1993	SIGMOD	8.3494816e-05
2,866	Optimal Column Layout for Hybrid Workloads	2019	VLDB	8.0175489e-05
5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.1856695e-05
6,396	Contention and Space Management in B-Trees	2021	CIDR	5.8870425e-05
7,906	Buffered Persistence in B+ Trees	2024	SIGMOD	5.5181056e-05
11,218	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	5.093636e-05
12,357	No Bits Left Behind	2011	CIDR	5.093636e-05
12,767	Transaction support for indexed summary views	2004	SIGMOD	5.093636e-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,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
2	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
3	6,396	Contention and Space Management in B-Trees	2021	CIDR
4	3,033	The Performance Of A Multiversion Access Method	1990	SIGMOD
5	14,013	Relaxed Multi-Way Trees with Group Updates	2001	PODS
6	464	Concurrent Operations on B-Trees with Overtaking	1985	PODS
7	1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
8	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
9	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
10	10,149	Bounding the Fragmentation of B-Trees Subject to Batched Insertions	2026	PODS