Motivation

Recently, Im trying to build a database from scratch for my own, mainly for practicing my Rust skill. In the book I’m following, the author mentioned two types of data structure for storing data in a database: B⁺-tree and LSM-tree. I want to know the difference between them and which one is better for my database.

So I decided to write this article to help me understand the differences and keep track of knowledge and research.

WIP details

References

• Revisiting B⁺-tree vs. LSM-tree
• Understanding The Difference Between LSM Tree and B-Tree
• Designing Data-Intensive Applications
• FAST ‘22 - Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression
• Scaling Write-Intensive Key-Value Stores
• Log-Structured File Systems
• System Design: LSM Trees | Data Structure Behind Google and Facebook Storage Engine
• B-Trees, Indexing and TeraBytes of Data || System Design by @RachitJain