[DB Seminar] Spring 2018: Ziqi Wang
Lock-free data structures have long been rumored to provide better performance and scalability than their lock-based counterparts. On the other hand, however, there are state-of-the-art in-memory indices using various fine-grained synchronization techniques that outperform the classical lock coupling implementation. In this talk, we investigate into a concrete, optimized implementation of a lock-free B+Tree, the Bw-Tree, and then conduct an apple-to-apple comparison between the Bw-Tree and other state-of-the-art in-memory indices such as the Skiplist, MassTree, BTree (OLC) and ART (OLC). We also present a detailed dissection of the composition of Bw-Tree’s performance figures, using the BTree (OLC) as a baseline. We believe our study could provide more insight into the performance characteristic of both worlds with or without locks, and serve as a reference for system designers to measure trade-offs between different index types.
 Levandoski, Justin J., David B. Lomet, and Sudipta Sengupta. “The Bw-Tree: A B-tree for new hardware platforms.” In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 302-313. IEEE, 2013.
 Crain, Tyler, Vincent Gramoli, and Michel Raynal. “No hot spot non-blocking skip list.” In Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on, pp. 196-205. IEEE, 2013.
 Mao, Yandong, Eddie Kohler, and Robert Tappan Morris. “Cache craftiness for fast multicore key-value storage.” In Proceedings of the 7th ACM european conference on Computer Systems, pp. 183-196. ACM, 2012.
 Leis, Viktor, Florian Scheibner, Alfons Kemper, and Thomas Neumann. “The ART of practical synchronization.” In Proceedings of the 12th International Workshop on Data Management on New Hardware, p. 3. ACM, 2016.
 Leis, Viktor, Alfons Kemper, and Thomas Neumann. “The adaptive radix tree: ARTful indexing for main-memory databases.” In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 38-49. IEEE, 2013.