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: 11196
Venue: VLDB
Year: 2015
Pagerank: 7.591263e-05
Overall Rank: 3,256 | 77.67%
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
882	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.0001342403
948	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.0001303916
1,141	Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores	2017	VLDB	0.0001200422
1,238	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011543368
1,390	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00010942775
4,296	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.7773228e-05
5,234	MxTasks: How to Make Efficient Synchronization and Prefetching Easy	2021	SIGMOD	6.3051801e-05
8,474	OptiQL: Robust Optimistic Locking for Memory-Optimized Indexes	2023	SIGMOD	5.4172941e-05
9,547	Tabular: Efficiently Building Efficient Indexes	2025	VLDB	5.2528121e-05
10,568	Operation-Aware Hybrid Locking for Modern In-Memory Indexes	2026	VLDB	5.093636e-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

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
38	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00047648573
105	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033877899
157	OLTP Through the Looking Glass, and What We Found There	2008	SIGMOD	0.0002863588
1,089	High Performance Transactions in Deuteronomy	2015	CIDR	0.00012242396
1,358	PLP: Page Latch-free Shared-everything OLTP	2011	VLDB	0.0001104203
1,822	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.6765747e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB
2	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
3	10,568	Operation-Aware Hybrid Locking for Modern In-Memory Indexes	2026	VLDB
4	10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
5	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
6	1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB
7	13,004	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB
8	4,030	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD
9	948	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB
10	1,390	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD