As multicore architecture is becoming the new normal of today’s computers, many traditional programming paradigms for mutual exclusion has become a major source of scalability bottleneck. To counter such bottlenecks for our in-memory database prototype at Carnegie Mellon University [1], we implemented a lock-free B+Tree multimap index based on BwTree, which was originally proposed by Microsoft Research [2]. In this presentation, detailed techniques for ensuing correct concurrent updates, efficient operations, and improving scalability are discussed, with an insight into low level hardware architectures for exploiting concurrency deep inside the index structure.

References
==========
[1] CMU Database Group.Peloton Data Management System.https://github.com/cmu-db/peloton. 2015.
[2] 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.