How Databases Store Data: B-Trees vs LSM Trees Explained

[00:00:00]Every second, millions of database rights are happening around the world.

[00:00:03]Instagram photos being saved, your online orders being recorded, messages being stored. But here is something most developers never think about when you hit save in your application. What actually happens at the physical level?

[00:00:17]How does that data go from your code to being permanently stored on a spinning disc or SSD? There are two completely different approaches to this problem and the one you choose can make your database 10 times faster or 10 times slower [music] depending on your use case. So today we're going to crack open a database and see exactly how data gets stored on desk. We'll explore B trees, the 50-year-old data structure that powers post SQL and MySQL and LSM trees, the modern approach behind Cassandra, Rox DB, and many NoSQL databases. By the end, you'll understand why Netflix uses one approach for their viewing history and completely different one for the recommendation engine. Let's dive in.

[00:01:02]Before we talk about fancy data structures, let's understand the basic problem we are trying to solve. Imagine you're building a simple key value store. Think of it like a giant Python dictionary or JavaScript object. You have keys like user 1 23 and values like user profile data. Now here is the challenge in memory. This is trivial.

[00:01:23]Dictionaries and hash tables give you 01 lookups lightning fast. But memory is expensive and volatile. Turn off the power and poof everything is gone. So we need to store data on disk. SSDs or spinning hard drives. They are cheap, they are persistent but they have one massive constraint. They are slow.

[00:01:44]Reading from RAM about 100 nconds.

[00:01:47]Reading from SSD about 100 microsconds.

[00:01:50]That's 1,000 times slower. And reading from a spinning hard drive 10 milliseconds. That's 100,000 times slower than RAM. This weight difference is everything. It's why we can't just dump our hash table to disk and call it a day. We need data structures specifically designed for disk access patterns. And here's the key insight.

[00:02:11]Desks are terrible at random access but great at sequential access. Reading one bite at a random location slow. Reading one megabyte of consecutive bytes much faster per bite. This is why database storage engines are all about minimizing random disk access. And this brings us to our two main approaches B trees and LSMS. Let's start with B tries because they are everywhere. Post SQL uses them, MySQL uses them, SQL light uses them.

[00:02:41]They have been around since the 1970s and they are still the default for most databases. You can think of a B tree as a well organized filing cabinet in a massive library. A B tree is essentially a sorted tree structure. At the top, you have root node that acts like an index.

[00:02:58]It says keys A to M go left, keys N to Z go right. You follow the pointers down each level narrowing your search until you hit a leaf node that contains the actual leader. [snorts] Here is a concrete example. Say you're looking for user_789.

[00:03:14]You read the root node from disk. It tells you keys 001 to 500 left child.

[00:03:20]Keys 5001 to 999 right child. You follow the right pointer. Read that node. It narrows it down further. Keys 501 to 750 left. key 751 to 9999 right you follow left read that node and boom there's your data for user 789 that's typically three to four disrees to find any piece of data and because this tree is balanced you are guaranteed of this logarithmic performance now B trees are brilliant for reads you want to look up a specific user fast you want to do a range query such as give me all users from ID 100 to 200 also fast because the data is sorted and stored together. And this is why B trees dominate in OLTP system or online transaction processing where you have lots of random reads and point lookups. But [snorts] here is where it gets tricky. Rights. When you insert new data, you need to find the right spot in the sorted tree and insert it there. That might mean reading several nodes to find the insertion point, splitting nodes if they are full, updating parent pointers, or rebalancing the tree.

[00:04:29]One write can trigger multiple disk reads and writes. In the worst case, inserting one record can touch dozens of pages on disk. And here's the painful part. If your disk is nearly full and you're doing random inserts, you are constantly seeking to different locations. Spinning disc hate this. SSDs handle it better while it's still inefficient. So, Bries optimized for reads, more expensive for rightes.

[00:04:55]They're basically great for read heavy workloads with occasional updates. Now let's talk about LSM trees or log structured merge trees. These are completely different philosophy and it's taking over all modern databases.

[00:05:07]Cassendra uses LSM trees. Roxb uses them. Level DB, HB, Sila DB, they are everywhere in the NoSQL world with highlight systems. Here's the core insight. What if instead of keeping everything organized on disk, we just write things down as they come in like a journal. When a right comes in, LSM trees do something beautifully simple.

[00:05:28]They write it to an in-memory structure called a mem table. Think of it as a sorted in-memory buffer. When a mem table gets full, say 64 MB, they flush it to disk as an immutable sorted file called an SS table or sorted string table. And here's the key, it's written sequentially in one go. Sequential writes are fast. We are talking 100 to 500 megabytes per second even on spinning disk. Compare that to random writes which might be only 1 to 2 megabytes per second. So writes are blazingly fast. But what about reads?

[00:06:03]Well, here is the trade-off. Now when you want to read user_789, you need to check the current mem table in memory, the most recent SS table on disk, the next SS table, and the next one. You might have to scan through multiple files before finding your data.

[00:06:18]And unlike V trees, these files aren't organized in a tree structure. They are a series of sorted files. So how do LSM trees stay fast? First, they use Bloom filters because checking each SS table, they ask the Bloom filter, does this file even contain user 789? If no, skip it entirely. This avoids tons of unnecessary discreets. Second, they use compaction. In the background, the database periodically merges SS tables together, removing data and combining duplicates. This keeps the number of files manageable. Imagine you have five SS tables. During compaction, they get merged into one or two larger, more organized SS tables. Older data gets pushed down to lower levels. And this is why they are called leveled or tiered compaction strategies. Basically, data ages and moves through all the levels.

[00:07:12]The result right stay fast always sequential reads are slower than B trees for point lookups but still reasonable thanks to bloom filters and caching and here's the beautiful part LSM trees handle high right through portut brilliantly you can write millions of records per second because you are just appending to memory and occasionally flushing to disk and this is why they are perfect for time series data logging systems message cues and any system where rightes dominate which brings me to our today's sponsor Savvada I have actually deployed fullstack applications using their platform and I want to show you how straightforward deployment can be. First you need to create an account on the seala website. Once logged in you arrive at the seala dashboard. We are going to do two things here. Create a postgra database for our app on seala and deploy our nextjs application to seala's application hosting. In the seala dashboard find the option to add a new database. Choose postgra sql. After a few seconds, Savala will provision a new Postgre database for us. It's fully managed, meaning Savala handles the setup, scaling, and maintenance. Copy the database connection URL, and we'll need to supply this to our app. Now, let's add our application. So, I have connected my GitHub account and selected the repository containing our NextJS project. We also choose the region for our app. Ideally, the same region as the database for best performance. Now, before deploying, we need to tell our app how to connect to the database. Now our app running on Savala will have access to process.env.dat database URL and can connect to the right database.

[00:08:44]We hit the deploy button. Savala will spin up a container to build our app.

[00:08:48]And here it is. Our app is on the internet. It looks the same as it did locally. All right. So let's bring this all together. When do you use B trees versus LS trees? B trees are your go-to when you have a read heavy workload. Say 80/20 or 9010 read to write ratio. You need fast point lookups and range scans.

[00:09:08]You're doing transactional workloads such as bank accounts, e-commerce orders or your data fits well in memory or you have fast SSDs. For example, you can have post SQL for your user accounts, MySQL for your product catalog, SQL light for your mobile apps local database.

[00:09:25]LSM trees shine when you have a right heavy workload, tons of inserts and updates. You're okay with slightly slow data. You're dealing with time series data such as logs, metrics, sensor data and you need to ingest massive amounts of data quickly. The best example I could think of is Cassandra for Netflix's viewing history, 300 million writes per day or Roxb for Facebook's messaging backend and influx DB for monitoring metrics.

[00:09:53]Here is a real world example. Discord they used MongoDB which uses B trees for storing messages. worked great initially but as they scaled they hit billions of messages. Reads were fine but writes were becoming a bottleneck. Random inserts into vries were causing disk fragmentation and slow insert. So they migrated to Cassandra with LSM trees.

[00:10:14]Writes became 10 times faster and they could now handle millions of messages per second with ease.

[00:10:21]But here is the nuance. It's not always black and white. Modern databases are using hybrid approaches. Roxb for instance uses LSM trees but adds clever optimization for reads. Postgress SQL primary uses B trees but has a wall write ahead log which is append only.

[00:10:38]The best storage engine depends on your specific access patterns and that's why understanding these fundamentals matters. Databases today face a fundamental challenge. Disks are still thousand to 100,000 times slower than memory. The storage engine you choose makes all the difference. Now I have barely scratched the surface. We didn't talk about right amplification in LSM trees or how B3 locking works in concurrent systems. Let me know in the comments what interests you the most.

[00:11:04]And if this help you understand something you have been confused about, hit subscribe. I break down database internals and system design like this every week. Thanks for watching and I'll see you in the next one.