LSM-Trees and B-Trees: The Best of Both Worlds

Jain, V; Lennon, J; Gupta, H

Jain, V (reprint author), Harvard Univ, Cambridge, MA 02138 USA.

SIGMOD '19: PROCEEDINGS OF THE 2019 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2019; (): 1829

Abstract

LSM-Trees and B-Trees are the two primary data structures used as storage engines in modern key-value (KV) stores. These two structures are optimal for different workloads; LSM-Trees perform better on update queries, and B-Trees do on short range lookups. KV stores today use one or the other. However, for modern applications with increasingly diverse workloads, utilizing only one of the two designs leads to a significant loss in performance. We propose a novel method of online transitioning a KV store from an LSM-Tree to a B-Tree and vice versa. This allows KV stores to smoothly adapt to changing workloads.

Download PDF


Full Text Link