To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing

Summary: Empirical HTM vs lock-free indexing for in-memory B-trees; HTM helps only for simple, fixed keys, not complex workloads. Lock-free designs excel under contention; HTM can simplify multi-threading via multi-word CAS with 10–15% throughput loss, on Bw-tree and a memory-optimized B-tree. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb6d69c255540db84
Venue: VLDB
Year: 2015
Pagerank: 7.4436949e-05
Overall Rank: 3,301 | 77.81%
DOI: 10.14778/2809974.2809990

Incoming Non-self Citations Over Time

Authors

1. Darko Makreshanski (ETH Zurich)
2. Justin Levandoski (Microsoft)
3. Ryan Stutsman (Microsoft)

BibTeX Citation

@article{makreshanski_vldb15,
        title = {{To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing}},
        author = {Makreshanski, Darko and Levandoski, Justin and Stutsman, Ryan},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {11},
        doi = {10.14778/2809974.2809990},
        url = {https://doi.org/10.14778/2809974.2809990},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
907	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00013158824
964	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012810196
1,161	Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores	2017	VLDB	0.00011768531
1,241	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011378254
1,320	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00011045319
4,362	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.6380763e-05
5,337	MxTasks: How to Make Efficient Synchronization and Prefetching Easy	2021	SIGMOD	6.1744712e-05
8,642	OptiQL: Robust Optimistic Locking for Memory-Optimized Indexes	2023	SIGMOD	5.2957446e-05
9,727	Tabular: Efficiently Building Efficient Indexes	2025	VLDB	5.1349531e-05
10,750	Operation-Aware Hybrid Locking for Modern In-Memory Indexes	2026	VLDB	4.9793485e-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

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
35	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00048001919
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033526937
157	OLTP Through the Looking Glass, and What We Found There	2008	SIGMOD	0.00028317906
1,083	High Performance Transactions in Deuteronomy	2015	CIDR	0.00012113053
1,382	PLP: Page Latch-free Shared-everything OLTP	2011	VLDB	0.00010858298
1,855	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.4973014e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,692	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
2	13,326	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
3	10,750	Operation-Aware Hybrid Locking for Modern In-Memory Indexes	2026	VLDB
4	11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
5	5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
6	1,717	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB
7	13,294	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB
8	4,072	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD
9	964	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB
10	1,320	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD