What about Binary Search Trees?
summary
Covers concrete designs and tradeoffs: partial external BST (needs parent+grandparent to remove leaves), two locking policies (per-node vs per-field) and top-down locking order, and the 2010 practical implementation that uses optimistic hand‑over‑hand traversal. Compares lock‑based vs lock‑free descriptors (Java implementations suffer from extra indirection; C++ versions use pointer tag bits), discusses rebalancing approaches (AVL rotations, chromatic/AB trees, daemon or collaborative rebuilders), uses LL/SC primitives and epoch‑based memory reclamation, and reports skip lists are ~2–3× slower and use more memory.
AI-written summary · about
chapters (30)
- 0:00Concurrent BST introduction
- 2:14BST basics and concurrency
- 4:21BST types explained
- 6:08Partial external BST intro
- 9:17Insert/remove in partial BSTs
- 12:08Locking strategies for BSTs
- 14:15Conditional locking benefits
- 15:40Optimal BSTs with conditional locking
- 17:48Performance challenges and rebalancing
- 19:12AVL rebalancing in BSTs
- 20:58Relaxed AVL balancing
- 22:03Top-down and rebuilding rebalancing
- 23:29First concurrent BST implementation
- 25:38Lock-free BSTs and versioning
- 27:45Contention-friendly BSTs
- 30:33Internal BST issues
- 32:40Doubly linked list for BSTs
- 35:50Log-free BSTs and descriptors
- 37:35Descriptor-based BSTs in C++/Java
- 40:27Memory management in log-free BSTs
- 42:37Balancing log-free BSTs
- 44:06LLX/SC primitives for trees
- 46:55Collaborative subtree rebuilding
- 47:36Weight-free BSTs and windows
- 48:19BST vs skip lists performance
- 50:30Best log-free BSTs in C++
- 51:11Modern BST alternatives
- 52:17Memory management for BSTs
- 53:18Q&A on BSTs and skip lists
- 57:12Future of concurrent BSTs
related talks
26mConcurrency: Unlocking a Solution
13mDMTree: Towards Efficient Tree Indexing on Disaggregated Memory via Compute-side...
14mSMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory
28mLinear Algebraic Depth-First Search
01h 05mAn Interesting Lock-free Queue - Part 2 of N
01h 04mDebugging data races
01h 13mCRDTs: The hard parts
20mPre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines