Algorithms Behind Modern Storage Systems

[tao]

Different uses for read-optimized B-trees and write-optimized LSM-trees

 

The amounts of data processed by applications are constantly growing. With this growth, scaling storage becomes more challenging. Every database system has its own tradeoffs. Understanding them is crucial, as it helps in selecting the right one from so many available choices.

 

Every application is different in terms of read/write workload balance, consistency requirements, latencies, and access patterns. Familiarizing yourself with database and storage internals facilitates architectural decisions, helps explain why a system behaves a certain way, helps troubleshoot problems when they arise, and fine-tunes the database for your workload.

 

It's impossible to optimize a system in all directions. In an ideal world there would be data structures guaranteeing the best read and write performance with no storage overhead but, of course, in practice that's not possible.

 

This article takes a closer look at two storage system design approaches used in a majority of modern databases—read-optimized B-trees¹ and write-optimized LSM (log-structured merge)-trees⁵—and describes their use cases and tradeoffs.

 

If interested, please, read the long article < here >.