Understanding B-Trees: Efficiency in Database Indexing

B-trees optimize data retrieval, reducing search time from 100 seconds to just 3 milliseconds for large databases.

### Understanding the Efficiency of B-Trees in Databases
* 🌳 B-trees are essential for efficient database operations, particularly in scenarios with **large datasets that cannot fit entirely in RAM**.
* 🕒 The example provided demonstrates how B-trees can significantly reduce the time required for searching through 1 million records, from **100 seconds to just 3 milliseconds**.
* 💡 The key advantage of B-trees is their ability to **minimize the number of disk I/O operations needed to access data**, which is crucial for database performance.
* 🔍 Unlike binary search trees (BSTs) or arrays, B-trees are specifically designed for disk-based storage, where each I/O operation is **much more expensive** than in-memory operations.
* The structure of B-trees allows for efficient multi-level indexing, ensuring that the **number of I/O operations remains logarithmic** with respect to the number of records.
* 🔄 In B-trees, nodes grow towards the root when they reach **maximum capacity**, rather than expanding towards the leaves as in traditional tree structures.
* 🔢 B-trees have a defined order (**M**) that determines the **maximum number of children each node can have**, leading to **predictable performance characteristics**.
* 🌿 B+-trees, a variant of B-trees commonly used in databases, store **all keys in the leaf nodes** and maintain a **linked list structure for efficient range queries**.

We have optimized from 100 seconds to 250 milliseconds to 3 milliseconds. We have seen the number of comparisons that are required for 1 million records, so you can see this is the most efficient solution. There is a huge improvement as the number of entries grows, and that is what B-tree does. Why do so many databases use B-trees and B+-trees? Are these really more efficient than, say, BSTs or arrays? And if more efficient, how much more efficient is it okay to use BSTs or arrays in case of databases, or are B-trees really, really necessary? How do B-trees even work internally? Can we do a dry run to understand it in a simple way? What is the difference between B-trees and B+-trees? Are they the same? And yes, we are going to cover all of this in this video. Welcome to another video in the free course of databases in depth by Edu Courses, where we not only discuss databases in theory but we debug their code. And yes, in the next video, we are going to be starting with one of the

most common databases, which is also one of the simplest databases in the world, which is SQLite. But before getting started, it is very important that you get your basics right, and that is why this is an extremely important video. Let's get started. Whenever we think about storage, we think of two solutions: one is RAM, and the other is hard disk. Now, you might think that this is very basic, but it is very important to get our basics right and to build up the use case, so just stay with me. So, what about RAM? RAM, as we know, is temporary. That means that if it crashes, it's gone. We lose our data, right? It is volatile, is another term, which means that it is temporary. Also, it is expensive, and because of that, we have limited space in RAM. What does that mean? That if our database is obviously growing, if we have terabytes of data, we cannot store it in RAM. RAM is very, very limited. It is expensive. So, that is where hard disk comes into the picture. Why? Because hard disk gives us persistence. We are

able to store the data permanently, right? And there's no limitation as such. We can keep adding hard disk, and we can store TBS of data. It is also very cheap. Then hard disk is the way to go. It is awesome, right? Not really, because it takes more time for every IO operation. For a simple comparison, let me just tell you that if you are doing one simple operation in RAM, it might take time in some nanoseconds. Obviously, the exact time is going to vary, but let's say 1 to 10 or max 100 NS versus in a hard disk. The same one IU operation is going to be in milliseconds. Yes, just literally one IU operation can take up to say 1, 10, 100 milliseconds. So, we know that each IU operation is expensive. It takes some time in hard disk, but it is very important for us to understand that why is it so. How does a hard disk look like? How does it operate? So, hard disk is nothing but a circular disk platter, and how it is divided is that inside it

There are some concentric circles, so these circles that you can see. These are called tracks, so each of these concentric circles. This is called a track, and then you divide this disk also into some pie-shaped pieces. So you see these pie-shaped pieces. Each of them is called a sector. So like this is one sector, okay? Now what will the intersection of a track and sector give you? So if you see, if we consider this track and if we consider this sector, what will it give us? This particular block, correct? Similarly, if we have to consider just this one block, this is what? This is the intersection of this track and this sector. Similarly, if I have to consider this block, it is the intersection of this sector and this track, correct? So the intersection of a track and a sector is giving us what? It is giving us a file block. So now typically, the file block on a disk is of the size of 4 KB. Obviously, it can vary with the disk. It can also be, say, 16 KB or like 512 bytes, but

Typically, it is 4 KB. So, what happens is that whenever we have to do an IO operation like a write or read operation, what happens is that we can always read and write in terms of file blocks. What do I mean? For example, if we have to consider some data which is over here, okay, so this is one file block, and we are considering data over here. Now, there's some data on the left, there's some data on the right, but it is not like I can take out just this particular data. It is not like that. In order to process it, in order to process that data, I have to take this entire disk block from the hard disk to RAM. So, in order to process any data, what we have to do is we have to take the entire file block from the disk to the RAM. So, whenever we have to do any processing, like suppose we have to process some data over here, we have to take out this entire file block, get it to RAM, process it, and then put it back. You cannot directly process it over here.

so the CPU can access the data that is there in RAM, and it cannot directly process the data that is stored on the hard disk, not directly. So, whenever you have to process any data, you have to take the entire block from the hard disk to the RAM, process it, if an update is required, put it back to the hard disk. So, this is how it works. But let's understand what is the impact that it has on us. Let's take the example. Suppose we have 1 million records. Suppose we're dealing with 1 million records. Now, if we are dealing with, say, SQL data, each record is going to be a row. Suppose we're dealing with NoSQL DB, like for example, MongoDB. We're going to call each record as a document. So now, each record can be a row. It can be a document. In our case, let's say that each record is an entry. Okay. So, each entry, for example, is taking 400 bytes. So, this is per entry or per record. Now, it can be a row or doc or anything. Now, what might happen is that there

might be like huge Dock, and inside that maybe some string is taking 50 bytes, there are like four or five integers, 4 bytes or 88 bytes, like that, right? So maybe the total is 400 bytes, so 1 million records and 400 bytes is per entry. So now, the first thing that we have to understand is that one block can store up to 4 KB of data, correct? One block can store up to 4 KB of data. So this is what we said, right? So that means how many entries or how many records can it store? That means 4,000 bytes divided by 400 bytes. That means one block can store 10 records or 10 entries, correct? Every single block. So it might be something like this: 1 to 10 over here, 11 to 20 over here, 21 to 30 over here, 31 to 40 over here, like this. So every single block would store 10 records or entries, correct? So I'm assuming that every file block can store up to 4 KB, and every

entry is taking 400 bytes, so this is just an example to understand. Okay, now in order to read 1 million records, let's see how much time would it take. So if we have 1 million records, that is 10^6 records, right? How many blocks would we have to read? The number of blocks to be read would be 10^6 / 10, because every block is storing 10 records. So how many blocks are required? 10^6 by 10, which is 10^5. So we have to read 10^5 blocks to go through 1 million records. In order to go through 1 million records, we are reading 10^5 blocks, and we said that in a hard disk, one I/O operation takes, say, 1 millisecond. It can also take 10 milliseconds, but let's say it is taking 1 millisecond. Okay, if it is taking 1 millisecond, that means that this is going to take 10^5

milliseconds. That means it is going to take 100 seconds to read 1 million records, which is huge. So, in order to just read 1 million records from the hard disk, we would take 100 seconds. We should obviously try to make this better. Now, that is the problem that we are trying to solve. So, what did I do? I just took some example. 1 million records is a very common thing in databases, right? 4 KB is the standard thing. Your document can be this big. So, even if not 400 bytes, maybe even 40 bytes. Even if it is taking 10 seconds, it's a lot of time. So, we want to minimize the time taken to go through the records. How can we do that? Is the problem that we are going to try to solve. Before we move ahead, I would just like to take a minute over here to tell you that if you're preparing for interviews or if you're looking to become a better software engineer, I would love to be part of your learning journey and make it easier, faster, better.

and more fun. I teach live. Plus, you also get access to the recording so you can learn at your own pace. And you get a consistent teaching style because I teach all HLD, LLD, DSA, project-based courses where we cover industry-level projects like YouTube, WhatsApp, Zeroa. We cover Monack as well as DevOps, and we also have C++. Plus, if you sign up for any of our courses, you get lifetime access to all the batches, the past, present, future, everything. You also get access to our mock interview platform. You can come practice anytime. We are going to guide you. We obviously have doubt support as well. We are putting our heart and soul into teaching. So, if interested, at least check out the site, all the detailed curriculums, the testimonials, the answers to all the general FAQ, everything is present over here. Just check it out, educourses.com is the site. Plus, if you still have any questions, feel free to reach out to us at support@thercourses.com. We will also guide you about what is better for

you at least check out the testimonials for now. The best thing that I like about edu courses is their courses are live. KY herself, the way she teaches, the way the courses are structured, are actually the best part. They live classes and the very helpful B Community. I feel very confident as compared to what it was before these courses. As a software engineer, my experience at U courses has been really great. I feel more confident as a software engineer after enrolling in ed CES. But for now, let's get back to the [Music] video. Let's consider a very simple solution. So, I have drawn a disc over here. Let's see that. Okay, here there are records. So, 1 to 10 are over here. Again, 11 to 20 are over here. 21 to 30, just how we saw. Okay, so records are over here. Now, what we are going to do is we are going to have yet another table. And what it is going to store is it is going to store, suppose, record one. It is going to say

that from record one till the next entry. So, suppose my next entry is 11, so from 1 to 10, all the entries are over here. Similarly, from 11 to, say, 20, all the entries are over here. So, we have a pointer to that particular block, so we know that if I just go through this table, I will know exactly where the entry is. So, instead of going through all the how many blocks, so there were 10 power five blocks, right? So, instead of going through all the 10 power five blocks, now let's see that how many blocks will we have to go through. Okay, now what is going to happen is obviously this table is again going to be on disk, right? So, this is also going to take some space. It is also going to take some extra file blocks, right? So, we'll have to see whether it is actually more efficient or not. So, let's do the calculation and let's see. So, approaching the problem in the similar way, so first thing that we have to see is that in one

particular block how many entries can we store. So one block can store 4,000 bytes, right? Obviously, this is all rough estimation, by the way. So when I say 10 records, it is roughly because it is 4 KB, so I'm considering it 4,000 bytes. Obviously, this is all rough estimation, okay? Just, uh, I hope you understand that much at least. So let's see that how many entries can we store. Let's say that each entry in this particular table is taking, say, 10 bytes. Good enough estimation. Maybe it would be 12 or something, but 4 and 8, so maybe we can take as 10 bytes, okay? So if each block can store up to 4,000 bytes and each entry in this table takes 10 bytes, so that means that each block can store how many entries of the table. That means 400 entries. So every block can store up to 400 entries of this table versus if we consider the data entry. How many entries was that? So per block, we were storing only 10 entries.

because that was a huge data entry, right? It was of 400 bytes. Over here, it is of only 10 bytes. So, each block in this case is going to store 400 entries of what? Of this table. Now again, how many such entries are going to be there? So, that depends on how many blocks are there, correct? Because how many do we need? How many blocks were there in the data, and how many blocks were there? 10 power five blocks, correct? So, we need the table for what? We need the table for each block. So, 10 power five entries are there in this particular table. So, 10 power five entries are there in this table. So, the next question is, in order to read this entire table, how much time are we going to take? So, we have to read through how many entries? 10 power five entries in this table. I hope you understood why we need 10 power five entries. See, what are these pointing to? These are pointing to these data blocks, right? These file blocks that are storing data. And how many blocks are

storing data. It is 10 power five blocks, so that is why the number of entries in this table is 10^5. Now we know that 400 entries of this particular table. So if this entire thing is say 10^5, we can divide into parts, say 400, then 800, then 1200, so on right. So each of that can be stored in one block. So how many blocks do we have to go through for this entire table? So the number of blocks is going to be what 10^5 divided by 400. So if I just write it in very simple terms, I'm doing the calculation also over here. So this is going to be 250. So we would have to go through 250 blocks of the disk in order to go through this one entire table. And now when we go through this one entire table, that is when we are done going through the 250 blocks, we would have found the data that we're looking for in one of the blocks. Suppose it pointed over here. Now this one data

Also, we would have to read, so this would take one extra extra 1 millisecond. Also, so don't forget that. So, we are going to the table by going through the 250 blocks, and after that, we are going to see that where is the data. Then we are going to access that one particular block. So, how much time will this take? 250 blocks, right? And every block takes 1 millisecond roughly. So, that means 250 milliseconds plus 1 milliseconds. But roughly, we can say that we are going to take 250 milliseconds to find something in 1 million records. So, we have optimized. How have we optimized from 100 seconds to 250 milliseconds, which is huge? How did we do that? By adding this one table. This table is called the index table, and you just understood what is indexing and how does it work, how is it more efficient. I am sure that calculations would have definitely overwhelmed some of you. I'm going to quickly summarize it, and it will be completely clear. Just be patient with me.

and if you still have doubts, just go back, try doing the calculations yourself. It would be just so amazing if you can understand how we were able to optimize from 100 seconds to 250 milliseconds, because this is just amazing stuff, this is real stuff that we are understanding. Okay, so let's quickly summarize. First, we saw that we have 1 million records. We said that every record is roughly taking 400 bytes, and because every file block can store 4 KBS, we can, we saw that one block is going to store 10 records. That means that the number of blocks that we are going to require to store 1 million records are going to be 10 power five blocks, which is going to require us 100 seconds. So, how many blocks are used to store all the 1 million records? That is 10 power five blocks. So, on the disk, 10 power five blocks are used to store all the data. Then we said, Let's optimize the time, and that is why we drew this index table. Now, in this index table, what did

we see, we saw that because each entry is much smaller. It's not like 400 bytes, right? Because each entry is much smaller, say 10 bytes here. We can store 400 entries in one block. Because we can store 400 entries in one block, that means these entire entries are going to go in one block. These entries are going to go in another block. These entries are going to go in another block. These entries are going to go in another block, and so on. So, we saw that 250 blocks are needed for the index entry. Firstly, if you still have the doubt how many entries are going to be there in this table, 10 power five entries. Why? See, 10 power five blocks are used to store the data. What are we pointing to? The blocks that have data, right? How many blocks of data? 10 power five. So, that is why 10 power five entries. So, first of all, this should be clear. 10 power five entries. Why? Because we are pointing to data. How many blocks are pointing to data? 10 power five blocks. I'm again and

again repeating so that you don't have any doubts. I'm sorry if you're getting annoyed by my repetition, just making sure that there are no doubts. Okay, now if you also want to do the cross calculation, you can see that see uh 400 entries and then we I'm saying 250 blocks right. So this will be 10 power 5 right. So this is 100 and then three more zeros. So 10 power 5. So that is why see this is one block on the hard disk. This is one file block on the hard disk. This is one file block on the hard disk and so on. So that is how we optimized from 100 seconds to 250 milliseconds. But now the question is can we optimize this even further. Let's see if it is possible. So what I am going to do now is I'm going to create yet another table and I'm again going to store index only in this but now this is going to be pointing to one block that is storing our index entries and not the data.

entries, so there are 2 power five blocks for data, 250 blocks for index entries, right? So, how many entries are going to be in this table? 250 entries, correct? So, this is pointing to this block, this block, this block, so on. How many blocks are there? 250 blocks. So, there are going to be 250 entries inside this, right? Let's see how much space this table is going to require. So, again, the space for each record is the same only as over here, right? What did we see? 10 bytes. So, if we come back over here, and so 10 bytes for every entry, and then there are 250 entries, right? So, how much space do we need to store this entire table? 250 entries into 10 bytes, which is just 2500 bytes, which is actually less than 4 KB, and this entire table is not even going to require one entire file block size, correct? So, now, if we have to find something, we can just take out whatever one file block is there for this one table. We will go through this.

then we will see that, okay, if we are looking for something over here, we will see that where is this particular block. Then we will get that one block over here, and then we will go through this one block, and we'll see where exactly is the data. So, how many IO operations are we doing with the dis 1, 2, and 3? So, three IO operations, each taking 1 millisecond. So, now we have optimized to what? 3 milliseconds. So, we went from 100 seconds to 250 milliseconds, and now to 3 milliseconds by just adding one more table. And this, my friend, is called multi-level indexing. And guys, we didn't just understand the concept of multi-level indexing, but we actually also do our very first P tree. And let me show you how this is going to be very interesting. So, what I'm going to do is I'm going to copy this diagram, and I am just copying it. I'm going to a new page and just going to paste it, and I am going to rotate it. And this is exactly

B3 and let me show you how. So, if you see over here, there are many keys, and there are child pointers, and child pointers are again pointing to some other nodes, and within this also again there are some pointers, right? On a higher level, this is how B3 looks like, but we are going to go into a lot of detailing. We are also going to dry run, but before that, I think it is very important that we answer a very, very important question. That is, B3 the only solution? What if we used other data structures that are commonly used? So, what we're going to do is we're going to draw a table and do proper comparison. We are going to take the example of 1 million records, and we are going to compare the time complexities. So, we are going to be comparing using three most common DB operations that we perform. That is, we usually perform search, we perform insert, and then we perform deletion, correct? So, we are going to consider these three operations, and then we are going to consider all the data.

structures one by one. The most common solution that is going to come to your head, like if you did not know about B3, would be balanced BST. Why? Because it is the most common solution, right? It offers us logarithmic time for searching, insertion, and deletion. So, if we consider 1 million records, what would be the answer? So, if we have 1 million records, log base 2 of 10^6, this roughly comes out to be 20. So, that means we would have to do 20 IO operations with the hard disk for search, insert, and delete. How it would look like is like suppose we have like a route and we know that where it is on hard disk, we get this and then we will compare and then we'll see that, okay, is it on the left or on the right? And then we're going to say that, oh, it is on the left. Then we are going to access another one again from the DB, right? So, like this, we will have to do how many IO operations? Because for every single node, we will have to do one IO operation.

right, so it is going to be 20 IO operations for 1 million records. Obviously, an unbalanced BST would be worse than this, but let's do a quick comparison for that also so that clarity is there and there's no confusion left. See what is the difference between balanced BST and unbalanced PST. Like if we are storing 1, 2, 3, right? So the correct way of storing is like this: 1, 2, 3. This is balanced. In unbalanced, we could also store like this because this is also BST, right? This is also BST, but this is not balanced. So suppose if there are 1 million records, that means that we could actually store 1 million records linearly itself, right, in an unbalanced BST is also a possibility. So how many worst-case operations would we have to do? 10^6, which is obviously not efficient. We would have to do 1 million dis IO operations just for searching through 1 million records, which just doesn't make sense. And if we consider

this worst case of unbalanced BST basically the linear structure. Then again, insertion deletion will also be 10^6, so obviously this is not the efficient approach. Now let's compare for a sorted array because now you might be thinking that KY what if we just store all the data in a sorted way one by one. So basically in a dis how we would store is 1 2 3 like for the ID we would just store like this. Let's see what would be the complexities in this case. See search would be very simple. It would be binary search like balance BST itself which would have logarithmic time. So 20 IU operations just like over here right because it is sorted. So searching becomes very efficient but now insertion and deletion is a bit tricky. Now let me tell you how. If you have blocks like this which are sorted if you want to insert a new block over here what you would have to do is you would have to make space for it and you would have to shift these blocks. You would have to

shift these elements right so in the worst case you might end up shifting all the elements. So in the worst case, you would have to actually do 10^6, which is 1 million operations for both insertion and deletion. Similarly for deletion also, right? If I'm deleting this, I would have to shift all the other elements or all the other blocks if we want to store it in sorted order. And if you want to insert in between, you would have to shift the rest of them, correct? That is how it works. So this is an interesting point to keep in mind when we talk about databases, that operations are not similar to data structure operations that we usually consider in RAM. Here we are talking about hard disk, and we have to think that every I/O operation is expensive. And finally, it's time that we talk about our star, which is the B-tree structure. Now in B-tree, what happens is that we have a minimum and maximum number of keys that it can have, that every node can have. Like over here, we saw that there are multiple keys, and then there

are child pointers right. So, B Tree is nothing but a special type of MV tree, so we will understand it in more detail. What is MV tree? How binary trees have like two children, right? M tree can have M children. So, whenever we have a lot of data, it makes sense that maybe we can have multiple children, and I will show it to you how. Now, this is a special kind of MV tree. Now, in B tree, if we say that the order is M, that means the maximum children that it can have is M. So, there are ways to prove this, but to make things easier for now, I'm just telling you that search, insertion, and deletion in a B tree, what is the complexity? Log of whatever N. So, in our case, 10^6 base M. So, M is what? The maximum children that every note can have. So, suppose we consider a B tree with maximum children 100. So, then in that case, it would become log of 10^6 base 100, which would become equal to 3. So, we would essentially need just

three IO operations for all search insertion as well as deletion, and we actually saw this in our example. We did the calculations and saw that with 1 million records, it is possible that we need only three IO operations for search. So, this is actually possible, and now the comparison is complete. If you want to draw the proper table, let me just draw it properly and show you. I created this nice table for your reference. You can either take a screenshot or you can share it on LinkedIn or anywhere where you studied something nice if you're interested. Otherwise, let's do a quick recap, a quick summary of whatever we understood so far. See, we have seen the number of comparisons that are required for 1 million records. So, in a balanced BST, everything is logarithmic. So, log base 2 of 10^6 is roughly equal to 20. It is 19 something. So, search, insert, and delete will require 20 IO comparisons on the hard disk versus an unbalanced BST. Because it is unbalanced, it can be completely skewed. So, the height of the

bstd can actually be 10^6, so the number of operations will be 10 power 6 itself, which is 1 million. In a sorted array for search, you can do binary search, but for insertion and deletion, you will need shifting of the elements. That is why it will take 1 million IU operations versus for a B-tree of order 100. What does order 100 mean? It means that any node can have a maximum of 100 children. Then we can perform search, insert, and delete in just three IO operations. So, you can see this is the most efficient solution. After this, there is definitely a balanced BST, but if you think there is a huge improvement, and that is why B is used by so many databases now, it's finally the time to understand the structure of B3 in detail. So, what happens is that unlike BST where every node can have only one key, here a node can have multiple keys. So, what happens in bstd? Suppose the root node has the key 20, so we see that if you're

searching for something less than 20. We'll have to go here; otherwise, more than 20 will go over here. Now, in databases, what happens is that even when you're searching for one key, you will anyway have to access the entire file block from the disk, correct? That is the basic that we need to understand. So, instead of doing that, why don't we store multiple keys in a particular node only? Now, how does this help, actually? We need more comparisons now. See, let me explain you it in detail. So, suppose the keys that we store in this particular route are 100, 200, 300, 400. So, what is going to happen is that what this is going to point, suppose again here, all the key values are going to be lesser than 100. Over here, it is going to be between 100 and 200. Over here, it is going to be between 200 and 300. Over here, it is going to be between 300 and 400. Over here, it is going to be more than 400. So, if I have

to see something like suppose 10, 20, 30, 40 over here. It will be 110, 150, 180, 190 like this. So here also we have to do comparisons only. In fact, for every note, we have to do more number of comparisons because earlier in BST, what happened? We just saw 20 or less than 20 or more than 20. Over here, there is one note. We have to see, Oh, is it between 100-200? Is it between 200-300? Is it between 300-400? Even though the number of comparisons are increasing, the major thing, our major problem is being solved. What was a major problem? The cost of getting this data from disk to RAM. Now this is much more expensive than the number of comparisons that you're doing in RAM. And that is why this is more efficient because even though you're storing more number of keys, all of this will fit within one block. And best would be that you know you try to maximize the number of keys that you can fit in a block. Why because

anyway, if we have to access just this, also you will have to access the entire file block anyway, so it is better to access the maximum number of keys in once, and then we can compare accordingly, right? So, there is a trade-off over here. If we had only one key in the node, then also we would have to anyway get the entire file block from the disk, but the number of comparisons would be one over here. The number of comparisons is more than one; there are multiple number of comparisons, but the cost of getting the data from the disk to RAM is saved, and that is why B-trees are so much more efficient for databases. So, I hope now the core concept is clear. Let's understand the major characteristics of a B-tree. [Music] Now, when we say that a B-tree is of order M, so I said this before also, this means that the maximum number of children that any of the nodes in the B-tree can have. The max number of children is equal to M. That means that the maximum number of keys that any of the

nodes can have is equal to M minus one. Why so? Why did this happen? We did not understand, so let's see this example here. We saw that Max children are what? Say five, right? So if the children is five, see the keys are only four, which is one less. Why? Because see here, it is pointing to all the values that are less than 100, more than 100, and in the between values, right? So even though the keys are four, the number of children are 4 + 1, which is five. So if we say maximum children can be M, then the maximum number of keys can be M minus one. Similarly, b3a property says that the minimum number of keys that any node other than the root node, other than root node, should have m by 2 c seal. That means that you round off to the next bigger integer. So you take by two and then you round off to the next bigger integer. That is what taking seal means. Now root is an exception. It can have minimum one key also. So at least one key is the is

what the properties say so root can have minimum one key but all the other nodes should have minimum M by 2 keys. So, these are the main properties. If you just see the max number of keys, the Min number of keys, you should be able to understand that this B tree will have maximum how many keys, minimum how many keys. Let's take quick examples. So, say if M value is equal to four, that means the maximum number of keys possible for every node is three, any of the nodes. Okay, maximum number of keys is three, minimum number of keys will be what, 4X 2, which is 2. If m is equal to 5, the maximum number of nodes that is possible is 5 - 1, which is 4. The minimum number of nodes, so 5 by 2 is what, 2.5, so you round it off to the bigger integer, so which is three. So, this is how you can see that the B tree of order M can have minimum how many and maximum how many notes. Now, because of these two characteristics, what happens

is that as we go down one level in a B tree with every level, the number of keys that any level can store becomes by product of M, so it becomes M. So, let me explain what I mean. So, if from the root I have M keys, so my next level will have M into M keys because M can go over here, M can go over here like this m times, right? So, M into M. Similarly, in the next level, it will again become M times, so M into M into M. So, as we go one level down, our number of keys that can be stored at that level will become M times. So, if I have to find the height of the tree because my height of the tree is going to be balanced, a very, very important characteristic of a B tree is that all the leaves are at the same level, all the leaves are at the same level. So, if I have to find the height of the tree, how can we do that? So, if I have to find height, if the total number of keys that I have to accommodate is n, if

the total number of keys that I have to accommodate is n. Then, by every level, if I go up, it is going to keep reducing by m. So, if suppose the bottommost layer, the leaf layer, suppose it had like the total is supposed to be n, right? So then, in the next layer, there will be, suppose, here, there was x. In the next layer, there will be x by m. In the next layer again, it will be x by m divided by m again. So, it will keep reducing by m till we come across one, right? So, if we keep doing this, our h will actually become order of log n base m, order of log n base m. So, there are a lot of proofs also behind this, but this is the easiest way to understand because the total number of keys are n, and with every level, the number of keys that can be stored are becoming m times. So, height becomes the number of iterations while searching or while going through the entire tree. So, that is why h becomes log.

of n base M, and that is what we used while figuring out the complexity for searching, inserting, and deleting, right? So, in our case, in the example that we had taken, it was log of 10^6, and the order that I said was 100. That means that every node can have a maximum of 100 keys, which is easily doable in a real-case scenario, right? So, this would essentially require just three IO operations, and this is from where we started. I hope now the characteristics and the main important points of B3 are completely clear. Let's discuss one more very, very interesting and cool feature about B3. Before that, just notice something about BST now. If we have some particular nodes and we have to insert a new node, what happens? We compare, and the new node is inserted below the present nodes, right? So, we are expanding the tree where? Towards the leaves, correct? So, towards the leaves is where we add the new nodes versus what happens in B-Tree is that once we have the maximum number of keys in a particular node, we are going to

split it, and a new node is going to be inserted on top of it. So, there's a new node that is inserted, and suppose the maximum that we could insert is three. And now there's one more node. Maybe the new node will be inserted on top with one more note that can move up. So, what happens in B3 is that we grow towards the root. Now, why is this so important, and why is this so interesting? Because this is very, very important when it comes to multi-level indexing in databases. How? See, now today we might have 100 entries in our database. Tomorrow we might have 1,000. The day after tomorrow we might have 1 million. And as the number of entries grows or as the number of entries reduces, we want the level of indexing to change, and we shouldn't have to manage that. And that is what R-Trees do so beautifully. See, if we have 1,000 rows or 1,000 entries, then we might need only one level of indexing. But as the number of rows will increase, as the number of entries will increase.

what it will do is it will create a new note towards where towards the root. So, that is what a new level of indexing will be created. How did we visualize multi-level indexing like this, right? That we keep adding the index tables. So, if only this index table is required, then we are going to add it. If it is not required, then we are going to remove it. And this level of indexing is enough. So, this is our dis. This is the index table for this. This is the index table for this. And when it is required, when we see that the number of data entries are increasing in the database, that is when we can add a new level of indexing. And that is how berries really makes things a lot more [Music] simpler. Coming to the final part of the video, let's quickly talk about what is the difference between B trees and plus. Obviously, I can go into a lot more detailing, but we will quickly understand the major differences. And if you want me to go into more details, let me know in

the comments. I would love to do that. I would love to create a separate video on this, but for now, just for your basic understanding. What happens in B+ trees is that there is duplicate data, and it is made sure that all the data is present in the leaf nodes. All the keys are present in the leaf nodes, and then all the leaf nodes are connected in a linked list. Now, how does this help? So, in database range queries, they are very, very common, right? So, in range queries, whenever you need a lot of range queries, B+ trees become more efficient than B trees. Why? Because you can just traverse that, okay, from 15 till 100, give me all the keys or something like that. You can basically traverse in a linked list way, in a very easy way, versus in a B tree. What would happen is that you would need multiple traversals. You would have to go up and then go down like that, right? You would need multiple traversals for range queries. It won't be as straightforward. That is why, because this is such a common operation in

databases. B+ trees came into the picture, and it is very, very famous. The major difference is that in B trees, the keys are present in the internal nodes as well, versus in B+ trees. All the keys are present in the leaf nodes. It is stored on a single file on disk. How a node of B Tree is going to look like getting the tokens. This is where my start table is going to happen. Can you see the flow that from VDB, we called a b3e function. From B2 function, we calling a pag of function. If crash happened, we would have used this Jour file list of dirty pages in lru order. This brings us to the end of the video, and I hope you like the video. Let me know in the comments, and I hope you're excited to finally get started with understanding each of the databases in a lot more detail. We will also be debugging, and we'll get started with SQ light. You will see that b trees will be used in almost all the databases. It is very, very important Basics, and I

hope you enjoy the video. Let me know in the comments, and if you think the series deserves to be shared, and if you think I deserve your like and comment, please do consider doing it. You have no idea how hard I'm working for this. Every video that I shoot, it is at night, and it is literally after 6:00 a.m. right now. I cannot tell you how I am shooting. Literally, I am very, very tired, but I hope you like the video, and see you next time. Bye.

Simplest, Most Detailed Explanation of BTrees | Why do Databases use BTrees not BSTs or Arrays?

Keerti Purswani

B-trees and B+-trees are preferred in databases due to their efficiency in handling large data sets, with a significant improvement in performance as the number of entries grows.

Hard disks provide permanent data storage but have slower I/O operations compared to RAM, making B-trees crucial for optimizing data retrieval.

The internal structure of B-trees, with their tracks and sectors, allows for efficient data processing by loading entire file blocks from the disk to RAM.

Optimizing Record Retrieval from a Database

One million records, each taking 400 bytes, require 100,000 blocks to read, resulting in 100 seconds for retrieval.

Aiming to reduce this time, a new table is proposed to store pointers to record blocks, potentially minimizing the number of blocks to be read.

The solution's efficiency will be evaluated by comparing the extra space taken by the new table with the time saved in record retrieval.

One block can store 4,000 bytes, allowing for approximately 400 entries of a table with each entry taking 10 bytes.

To store 1 million records, 10^5 blocks are needed, resulting in a total of 250 blocks to go through for the entire table.

By using an index table, the time to find a record is optimized from 100 seconds to 250 milliseconds.

Multi-Level Indexing and Its Optimization

Multi-level indexing involves using smaller entries to store data, allowing for more entries per block and reducing the total number of blocks needed.

This method can optimize data retrieval time from 100 seconds to as low as 3 milliseconds by adding an additional table for index entries.

The concept of multi-level indexing is similar to the structure of a B-tree, with keys and child pointers leading to further nodes.

The Efficiency of Data Structures for Large Records

Balanced BSTs offer logarithmic time for searching, insertion, and deletion, requiring 20 IO operations for 1 million records.

Unbalanced BSTs can result in 1 million IO operations in the worst case, making them inefficient.

Sorted arrays provide efficient searching through binary search but require 1 million operations for insertion and deletion.

B-trees, with multiple children per node, offer a more efficient solution, potentially reducing the number of IO operations to as low as 3 for 1 million records with a maximum of 100 children per node.

The Efficiency of B-Trees in Database Management

B-Trees optimize search, insertion, and deletion operations by allowing nodes to have multiple keys, reducing the number of disk I/O operations.

With an order of 100, B-Trees can perform these operations in just three I/O operations, making them more efficient than balanced or unbalanced BSTs and sorted arrays.

The trade-off of more comparisons in B-Trees is outweighed by the cost savings of accessing multiple keys from a single disk block, making them ideal for database management.

B-Trees have a maximum number of keys per node equal to M minus one, where M is the maximum number of children.

The minimum number of keys for non-root nodes is rounded up from M/2, while the root can have a minimum of one key.

The tree's height is determined by the total number of keys (n) and the branching factor (M), resulting in a height of log n base M, which is crucial for efficient searching, inserting, and deleting operations.

The Importance of B-Trees and B+ Trees in Databases

B-Trees grow towards the root as new nodes are inserted, allowing for dynamic multi-level indexing in response to changing data entry numbers.

B+ Trees, on the other hand, store all keys in the leaf nodes and connect them in a linked list, making them more efficient for range queries.

The major difference between B-Trees and B+ Trees is the location of the keys, with B+ Trees offering a more straightforward traversal for common database operations.