The Bw-Tree: A B-tree for New Hardware

The Bw-Tree: A B-tree for New Hardware Platforms 1 2 3Justin J. Levandoski , David B. Lomet , Sudipta Sengupta Microsoft Research Redmond, WA 98052, USA 1 2 3justin.levandoski@microsoft.com, lomet@microsoft.com, sudipta@microsoft.com Abstract—The emergence of new hardware and platforms has operationswithoutsetting latches. Our approachalso carefully led to reconsideration of how data management systems are avoids cache line invalidations, hence leading to substantially designed. However, certain basic functions such as key indexed better caching performance as well. We describe how we use access to records remain essential. While we exploit the common our log structured storage manager at a high level, but leavearchitectural layering of prior systems, we make radically new the specifics to another paper.design decisions abouteach layer. Our newform of B-tree, called the Bw-tree achieves its very high performance via a latch-free B. The New Environmentapproach thateffectively exploitstheprocessor caches ofmodern multi-core chips. Our storage manager uses a uniqueform of log Database systems have mostly exploited the same storage structuringthatblursthedistinctionbetweenapageandarecord and CPU infrastructure since the 1970s. That infrastructure store and works well with flash storage. This paper describes the used disks for persistent storage. Disk latency is now analo- architectureandalgorithmsfortheBw-tree,focusingonthemain gous to a round trip to Pluto [4].