B-Tree 이해 데이터베이스 인덱싱의 효율성

### 데이터베이스에서 B-Tree의 효율성 이해하기
* 🌳 B-트리는 효율적인 데이터베이스 운영을 위해 필수적이며, 특히 **RAM에 완전히 들어갈 수 없는 대용량 데이터 세트**가 있는 시나리오에서 더욱 그렇습니다.
* 🕒 제공된 예는 **B-tree가 100만 개의 레코드를 검색하는 데 필요한 시간을 100초에서 단 3밀리초**로 크게 단축하는 방법을 보여줍니다.
* 💡 B-트리의 주요 장점은 **데이터베이스 성능에 중요한 데이터 액세스에 필요한 디스크 I/O 작업 횟수를 최소화**할 수 있다는 점입니다.
* 🔍 이진 검색 트리(BST)나 어레이와 달리 **B-트리는 각 I/O 작업이 인메모리 작업보다 훨씬 더 비싼 디스크 기반 스토리지를 위해 특별히 설계**되었습니다.
* B-트리의 구조는 효율적인 다단계 인덱싱을 가능하게 하며, **레코드 수에 따라 I/O 작업의 수가 대수로 유지**되도록 합니다.
* 🔄 B-트리에서는 노드가 최대 용량에 도달하면 기존 트리 구조에서처럼 잎을 향해 확장하는 것이 아니라 **뿌리를 향해 성장**합니다.
* 🔢 B-트리는 각 노드가질 수 있는 최대 자식 수를 결정하는 순서(M)가 정의되어 있어 **성능 특성을 예측**할 수 있습니다.
* 🌿 데이터베이스에서 일반적으로 사용되는 B-트리의 변형인 **B+-트리는 모든 키를 리프 노드에 저장**하고 효율적인 범위 쿼리를 위해 **연결된 목록 구조**를 유지합니다.

B-트리는 데이터 검색을 최적화하여 대규모 데이터베이스의 경우 검색 시간을 100초에서 단 3밀리초로 단축합니다.

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-Tree의 중요성

B-트리와 B+-트리는 대용량 데이터 세트를 처리하는 데 효율적이기 때문에 데이터베이스에서 선호되며, 항목 수가 증가함에 따라 성능이 크게 향상됩니다.

하드 디스크는 영구적인 데이터 저장 공간을 제공하지만 RAM에 비해 I/O 작업이 느리기 때문에 데이터 검색을 최적화하는 데 있어 B-트리가 중요합니다.

트랙과 섹터로 구성된 B-트리의 내부 구조는 디스크에서 RAM으로 전체 파일 블록을 로드하여 데이터를 효율적으로 처리할 수 있게 해줍니다.

데이터베이스에서 레코드 검색 최적화하기

각각 400바이트인 100만 개의 레코드를 읽으려면 100,000개의 블록이 필요하므로 검색에 100초가 걸립니다.

이 시간을 줄이기 위해 레코드 블록에 대한 포인터를 저장하는 새로운 테이블이 제안되어 잠재적으로 읽을 블록의 수를 최소화할 수 있습니다.

이 솔루션의 효율성은 새 테이블이 차지하는 추가 공간과 레코드 검색에서 절약되는 시간을 비교하여 평가할 것입니다.

인덱싱을 통한 데이터 검색 최적화

하나의 블록은 4,000바이트를 저장할 수 있으므로 각 항목이 10바이트인 테이블에 약 400개의 항목을 저장할 수 있습니다.

100만 개의 레코드를 저장하려면 10^5개의 블록이 필요하므로 전체 테이블을 위해 총 250개의 블록을 거쳐야 합니다.

인덱스 테이블을 사용하면 레코드를 찾는 데 걸리는 시간이 100초에서 250밀리초로 최적화됩니다.

다단계 인덱싱은 더 작은 항목을 사용하여 데이터를 저장하므로 블록당 더 많은 항목을 저장할 수 있고 필요한 총 블록 수를 줄일 수 있습니다.

이 방법은 인덱스 항목에 대한 추가 테이블을 추가함으로써 데이터 검색 시간을 100초에서 3밀리초까지 최적화할 수 있습니다.

다단계 인덱싱의 개념은 키와 하위 포인터가 추가 노드로 이어지는 B-트리의 구조와 유사합니다.

대용량 레코드를 위한 데이터 구조의 효율성

균형 잡힌 BST는 검색, 삽입, 삭제에 대수적 시간을 제공하며, 100만 개의 레코드에 대해 20개의 IO 작업이 필요합니다.

불균형 BST는 최악의 경우 1백만 개의 IO 작업이 발생하여 비효율적입니다.

정렬 배열은 이진 검색을 통해 효율적인 검색을 제공하지만 삽입과 삭제에 100만 번의 연산이 필요합니다.

노드당 여러 개의 자식이 있는 B-트리는 보다 효율적인 솔루션을 제공하며, 노드당 최대 100개의 자식이 있는 100만 개의 레코드에 대해 IO 작업 횟수를 3개까지 줄일 수 있습니다.

데이터베이스 관리에서 B-Tree의 효율성

B-Tree는 노드가 여러 개의 키를 가질 수 있도록 하여 검색, 삽입, 삭제 작업을 최적화하고 디스크 I/O 작업의 수를 줄입니다.

100의 순서를 사용하면 B-Tree는 단 세 번의 I/O 작업으로 이러한 작업을 수행할 수 있으므로 균형 또는 불균형 BST 및 정렬 배열보다 더 효율적입니다.

단일 디스크 블록에서 여러 키에 액세스할 때 발생하는 비용 절감 효과가 B-Tree의 더 많은 비교 작업의 장단점보다 크므로 데이터베이스 관리에 이상적입니다.

B-트리의 노드당 최대 키 수는 M에서 1을 뺀 값으로, 여기서 M은 최대 자식 수입니다.

루트가 아닌 노드의 최소 키 수는 M/2에서 반올림되며, 루트는 최소 1개의 키를 가질 수 있습니다.

트리의 높이는 총 키 수(n)와 분기 계수(M)에 의해 결정되며, 효율적인 검색, 삽입, 삭제 작업을 위해 중요한 로그 n 베이스 M의 높이가 됩니다.

데이터베이스에서 B-Tree 및 B+ 트리의 중요성

B 트리는 새 노드가 삽입될 때마다 루트를 향해 성장하므로 데이터 입력 번호 변경에 따라 동적인 다단계 인덱싱이 가능합니다.

반면에 B+ 트리는 모든 키를 리프 노드에 저장하고 링크된 목록으로 연결하므로 범위 쿼리에 더 효율적입니다.

B 트리와 B+ 트리의 가장 큰 차이점은 키의 위치이며, B+ 트리는 일반적인 데이터베이스 작업을 위한 보다 간단한 탐색을 제공합니다.