B-tree vs B+ tree in Database Systems

0:00 i get asked sometimes about the

0:02 importance of

0:03 data structures and algorithms and my

0:05 opinion is is very clear on these

0:08 these are very critical it really

0:10 depends why are you learning

0:12 learning them if you're learning for to

0:14 pass an interview

0:15 or to get a job then it's

0:19 they are just a burden you're gonna

0:20 memorize them you don't really

0:21 understand what they do

0:23 but if you truly go into this data

0:25 structure and really look

0:26 at the route why they will do it do they

0:29 exist

0:30 and what problems do they solve they're

0:32 gonna make you

0:33 an adept uh software engineer

0:37 you're gonna use this to your advantage

0:40 and you're gonna

0:40 nobody's gonna their way

0:44 through you at all because the you

0:47 really

0:47 know when to use this and i'm not going

0:50 to talk about development here

0:52 coding here really i'm talking about

0:54 actual

0:55 engineering working with a database

0:58 right for example and that's the topic

1:00 of today

1:01 b trees we're going to discuss all about

1:04 the concept of b

1:05 trees and how would improve to b plus 3

1:08 and what is the difference and the

1:10 advantages what problems do they solve

1:12 what are the limitations of these things

1:14 all of this stuff we're gonna discuss it

1:16 in this episode

1:18 stay tuned welcome to the backend

1:19 engineering show with your host

1:21 hussein nasser and guys if you like this

1:23 deep dive

1:24 uh discussions of our database concept

1:27 you might enjoy

1:28 my introduction to database engineering

1:31 udemy course

1:33 over 14 hours worth of exclusive content

1:36 that you won't find anywhere else

1:38 so if you're interested check out the

1:39 pinned comment

1:41 below and the show notes as well if

1:43 you're listening on the podcast it

1:44 really supports the show

1:46 thank you so much scott

1:49 all right guys so b3s

1:52 in order to discuss this data structure

1:55 why does why was it invented

1:58 we need to go back into a very

2:03 real use case you have a table in a

2:08 database it's a huge table

2:09 millions and millions of rows and you

2:12 want to

2:12 search for a particular row

2:16 by its identification let's say id

2:18 number

2:19 1007 you want to look at that

2:22 id okay and you just you don't want to

2:25 really

2:26 look at that id for the sake of looking

2:28 at the value

2:30 1007 no you want to pull more

2:33 information right so you want to get to

2:37 that row so you can pull more stuff

2:39 if you want to search for 70 you already

2:42 know 70 you're not searching for 17 for

2:44 the 17 you want more

2:46 and that's the key 17 the value is the

2:50 tuple

2:50 for the longest time what we do is

2:54 one by one let's read the table page by

2:56 page

2:57 oh one page one thousand rows another

3:00 page one thousand rows

3:02 read it nope 1007 is not any of them

3:05 so you have to read one by one until you

3:07 find it

3:08 and if you sure that this is unique so

3:10 you're gonna stop the search

3:11 right and then exit there this is called

3:14 a full table scan you're scanning the

3:16 entire table right

3:17 and if it's not unique you know there's

3:19 more to it you're gonna scan the entire

3:20 table eventually

3:22 which is very slow scanning one million

3:24 rows and worst case scenarios

3:27 two million three million very very slow

3:29 so it's slow

3:30 the trick is we're saying make it faster

3:34 make it faster that's what we want so

3:36 how do you make

3:37 searching one million stuff faster

3:40 well one way is to parallelize it let's

3:43 just split the table in

3:44 in three four five seven and then let's

3:47 distribute the jobs

3:49 on these threads or these machines and

3:51 let this search

3:52 that becomes complicated but that's

3:55 that's one way of doing it another way

3:56 of doing it is that

3:57 partition it partitioning a very very

4:00 important concept

4:01 we break the table into chunks based on

4:04 key

4:04 sizes so okay values from one to one

4:07 thousand

4:08 and this partition values from two one

4:10 thousand to two thousand is in this

4:12 partition on this table so it's just

4:13 essentially

4:14 break it down to multiple tables right

4:16 another

4:18 solution we're doing is create an index

4:20 so we search

4:22 on the index this small data structure

4:24 and then once we find it we jump into

4:25 the exact page

4:27 that we need in all these scenarios and

4:30 many many other scenarios we always

4:33 reduce the search space that is

4:36 it we're not doing anything magic really

4:40 if we want we do i made a video

4:43 so like how to work with a billion row

4:45 table okay it's it's a it's exclusive

4:47 for members

4:48 in this channel and the and the takeaway

4:50 from that video was in order to work

4:52 with a billion row table you need to

4:56 avoid working with a billion rows

4:59 yes it's not really rocket science don't

5:03 search one billion rules

5:04 find any sneaky way to avoid working

5:07 with large datasets

5:08 and then and and it's try to segment and

5:12 eliminate things that you know is not

5:14 it's not going to give you the results

5:15 that's the trick and here's where this

5:18 topic is indexes

5:20 the indexing i made a video about

5:22 indexing check it out but the idea of

5:25 having this index so that i can search

5:28 only the things that i am absolutely

5:30 sure

5:31 that the row that i'm looking at the

5:33 value of look at is in that space

5:36 right and when you've when you

5:39 design and structure your index that way

5:44 you're going to get a smaller set you're

5:46 going to search

5:47 fewer search space

5:51 and that the fewer the the search space

5:54 the smaller the search space the faster

5:56 the results

5:58 rocket science i know okay

6:02 so what's saying how do we build these

6:07 structures these trees came into

6:10 the equation so okay how about we build

6:12 trees so how do we build these trees

6:14 for the longest time we had this idea of

6:16 a binary tree which is a very very

6:18 simple beautiful

6:20 structure that says okay you put a value

6:22 on the top

6:23 and then larger values go

6:26 to the right smaller values of this node

6:29 go to the left

6:30 very simple data structure okay so if we

6:33 put a value of 100 here

6:35 okay anything above 100 goes to the

6:38 right of the tree

6:39 right and i'm doing right here it's my

6:41 right i don't know if it's you right

6:42 and anything to the left of the three is

6:45 less than 100.

6:46 so if you're searching for the value of

6:49 i don't know

6:50 200 then you always go to the root

6:53 so that's one cost jumping to the root

6:57 you say okay i'm looking for 200 you

6:59 know what you're looking at

7:01 is 200 greater or less than 100

7:05 this is a cheap check that gives you

7:07 almost

7:08 no cost at all but that check

7:12 eliminates almost half if you're lucky

7:17 half the search space because just like

7:19 that you're now searching

7:21 the right hand side because ah you know

7:23 that 200 is going to be in that area

7:26 and as a result you only going to search

7:28 100

7:29 and above so you're searching less

7:32 results

7:33 and this is a very simple example but

7:36 the problem with binary three are by

7:38 default they are not really balanced

7:40 what does that mean take this example

7:42 let's assume the root is one

7:46 okay and then any value that

7:50 puts uh that you add is greater than one

7:53 what will happen

7:54 two three four five six seven with

7:57 you're gonna end up with a linear search

7:59 space that you didn't really

8:02 that is as absolutely useless because

8:04 this is called an unbalanced tree

8:07 you're gonna end up almost like if it's

8:09 not even slower

8:10 than a full table scan you're going to

8:12 jump into multiple pages to get into the

8:15 value of

8:16 the 200 but you end up

8:19 doing more work effectively to search

8:21 that so binary trees

8:22 didn't really satisfy database workload

8:25 because of this

8:26 lack of balancing okay so we need a

8:29 self-healing self-balancing tree this is

8:32 where b3 came into the situation

8:34 and b3's guys stands for

8:37 really doesn't have it the paper doesn't

8:39 really say what it stands for it could

8:41 be balanced

8:43 could be boeing which is the company

8:45 that uh

8:46 the the research lab that this paper

8:48 came from or could be bayer

8:50 one of the creators of this uh the

8:52 researchers

8:53 well yeah it could be anything really

8:55 and the beauty of this is

8:57 it's really truly balanced so if you

9:00 think about it

9:01 what does really balance really mean

9:03 that means

9:05 as you insert the tree balances itself

9:09 and if you're an engineer almost like

9:12 wait a second

9:14 you're balancing as i'm inserting stuff

9:18 the moment you hear that if you really

9:21 pay attention

9:22 then there's a cost at all the cost

9:26 and that is where you need to look

9:29 so there is a cost on rights

9:34 which is this constant rebalancing

9:38 that needs to happen to balance itself

9:40 so it's

9:41 the left is equal to the right but at

9:44 the cost of this

9:45 as i'm writing i'm continually balancing

9:48 my tree

9:50 the reads my reads are gonna be very

9:53 very

9:53 quick quick as a result so b3s are

9:56 nothing but a generalized binary tree

9:59 you can have any number of children not

10:01 just two

10:02 you can have seven you can have

10:07 a thousand really the databases actually

10:11 calculate that on on the fly let's take

10:13 an example

10:14 all right so this is one of the most

10:16 popular

10:17 websites that demonstrates b trees and

10:20 it comes from university of san

10:22 francisco fantastic

10:25 website really very simple right no

10:28 fancy stuff

10:29 just to the point so we're going to

10:31 explain b trees here with

10:32 in this website so effectively so let's

10:35 say my b3 has a maximum

10:38 uh chill uh number of child the degree

10:41 of the order is three

10:42 that means it can have up to three nodes

10:46 okay so i'll go ahead and insert a bunch

10:48 of values that's gonna insert a value of

10:49 one

10:50 so this is this is going to become the

10:51 root which is one here

10:53 if i insert the value of two right

10:57 then when i want to insert a value of 2

10:59 we're going to look

11:00 is 2 greater than 1 well yes but i'm not

11:04 going to add it as a children

11:05 because i can actually put the value 2

11:08 inside the note itself

11:10 as an element okay so if i get an insert

11:13 now

11:14 i can have another value and here's the

11:16 thing you might say jose

11:17 how many elements or keys can you add

11:21 in the node itself it is the value which

11:24 is the maximum degree

11:25 minus one as effectively it's always

11:27 like that so three minus one so

11:29 two is the maximum you can get so now if

11:31 i want to insert three

11:33 what will happen here is okay i'm going

11:34 to insert three here but i'm gonna

11:36 exceed my

11:37 my coda in this node because i'm just

11:39 exceeded by that

11:40 so i'm going to split this note and that

11:43 split

11:45 hurts that split sometimes

11:48 really hurts specifically if you're

11:50 doing a lot of stuff the splitting of

11:52 the page and

11:53 doing this work that's all database io

11:57 right think about it this way as i go

11:59 through this

12:00 so if i insert into the value of three

12:02 it's gonna insert that

12:04 but what will happen is two is gonna be

12:06 promoted as root

12:07 and one is gonna be to the left and

12:09 three is going to be to the right let's

12:10 go ahead and do this

12:12 boom as we can see again this now

12:16 i still if i now answer the value of

12:18 four

12:19 what will happen here so if i come to

12:21 here and i say okay

12:23 four i'm going to add four four is

12:26 greater than two so it has really too

12:28 nearly to go to the right of the tree

12:30 right not to the left

12:32 so what will happen here is as i insert

12:35 this it will go to the four it will go

12:38 to the add

12:39 and then it will add it as another

12:41 element in this right

12:43 three and then you can see that now the

12:46 three has

12:46 three and four okay so how do you read

12:49 this tree let's continue reading it

12:51 so the value is 2 which is the key here

12:54 there is something that is hidden here

12:55 that is not shown which is the actual

12:58 value of that point the pointer where

13:01 this value points to

13:02 so to the left we have the value of one

13:06 to the right of the tree anything that

13:08 is greater than two

13:09 we have this node now you go to this

13:12 node and you find

13:13 three and four are elements in this node

13:17 so let's add five what will happen what

13:19 do you guys think what will happen

13:20 when you add five well five is greater

13:23 so it

13:24 needs to go here right and if i add it

13:27 right here

13:28 it's gonna go to the node but we just

13:30 decree exceeded the number of elements

13:32 it should be just two we shouldn't go

13:34 beyond two

13:35 so now four is gonna be promoted

13:38 as a node three is gonna go to the left

13:40 and five is gonna to the right but

13:42 since we want to keep the levels four

13:45 are gonna be

13:46 pushed so we're going to be 204 and

13:49 let's go let's add it so we can explain

13:51 this add it

13:54 we'll get added and then promote that

13:56 four and here's here's how you read this

13:59 let's read this this is a little bit

14:00 different than a binary tree

14:02 so this node has the value of element of

14:05 two an element of four

14:06 okay the key is two and four to the left

14:10 any values that are less than two are

14:12 here

14:13 any values that are between two and four

14:16 are

14:17 in this pointer you go here and you

14:19 search there could be one element could

14:20 be 700

14:21 depends on the degree of the tree and

14:24 then any values that are greater than

14:25 four goes to the left so it's a

14:27 full balanced tree but look at the work

14:30 that we're doing as we insert and

14:33 we're just balancing and undoing all

14:34 that stuff

14:36 uh so and that's because we we have a

14:39 very small

14:41 uh element degree of the size which

14:43 databases shouldn't use

14:45 a value of three you should have a huge

14:48 as

14:48 as big as your page size

14:51 all right so talking about the b3s let's

14:56 talk about

14:56 the the the benefits of this if i want

15:00 to search

15:00 let's find the value find value of three

15:04 very simple right before we go through

15:07 it

15:08 three three well three is between two

15:11 and four

15:11 first of all i need to go jump to the

15:13 root and say okay where's three

15:14 three is between two and three two two

15:16 and four so

15:18 i mean i need to jump to this pointer so

15:20 i follow this pointer

15:22 to whatever note it points me we are

15:24 seeing an actual node but

15:26 in databases this is a page mostly

15:29 at least the postgres implementation

15:31 this is a page itself

15:33 this is a page this is a page and there

15:35 is

15:36 thousands and thousands of elements in

15:38 that page right so this is an i o

15:40 this is an i o so now i go to three and

15:43 then i found three this is a

15:44 very very short three essentially

15:47 and you just found it the value three

15:49 i'm not really interested in the value

15:51 three

15:51 i'm interested is what is the content of

15:54 the value three

15:55 and that is the value here

15:58 there is something that is not shown in

16:00 this diagram i wish they they actually

16:02 showed them but

16:03 there is a there is a value there's not

16:04 this this is not just the tree

16:06 we're not looking at just the numbers

16:08 here there is some

16:09 content that associates with the key

16:13 it's almost like a key value right

16:16 so the 2 has a value next to it

16:20 in b3s every element

16:23 has a value attached to it so two could

16:26 have

16:27 any value it could point postgres

16:30 implementation pointed

16:31 directly to the tuple id right my sql

16:34 implementation pointed directly

16:36 to the primary key

16:39 right in that case and that's why

16:42 if you use a primary key in in my sequel

16:45 that is like a

16:46 good then your indexes are going to be a

16:50 huge

16:51 very huge right so be careful what

16:54 primary key you use in my sequel

16:55 right and and and post because they

16:57 don't have that problem effectively

17:00 because everything is a secondary key

17:02 and they always point to the tuple

17:05 all right so that that's that's what

17:06 we're looking at so

17:08 who's saying why are you telling us that

17:09 there's values here because that is the

17:11 difference in the other data structure

17:14 that is called

17:15 b plus three and what problems it is

17:16 solved so now when i when i'm

17:18 searching here i

17:21 this is a page right this is a whole

17:23 page

17:25 so if there is two and the value of it

17:29 whatever that value is if if if you if

17:31 you're in my sequel then

17:32 it's the pointer to the primary key so

17:35 the primary key data type

17:37 goes there if it's postgres is the tuple

17:39 i believe it's i don't know if there's

17:41 two bits maybe

17:42 forgot what's the table id value size

17:45 so that that is the tuple id in that

17:47 case so you

17:48 you put more bits here so

17:52 this page is gonna be

17:56 is gonna fit fewer elements

18:01 because we are carrying also values

18:04 right if i only had the keys

18:06 i could fit more elements in my page

18:10 which is let's say in pos because it's

18:12 8k i can fit

18:13 more elements there and as a result i

18:16 can search

18:16 i can i can traverse through much more

18:19 elements

18:20 in a single io compared to this data

18:23 structure

18:23 which has the values which let's be

18:26 honest

18:27 the values are out of burden

18:31 if you think about it another thing here

18:32 is what if i

18:35 am searching for one three

18:38 and five at the same time how do i do

18:40 that

18:41 well oh let's search for one oh one is

18:43 here so i'm gonna read here

18:45 okay we found it okay now now i want to

18:48 search for three

18:49 oh so let's do it again go here and then

18:52 three

18:53 so you did a double jump to get to the

18:56 value of three okay

18:57 i wanna search for five well let's do it

18:59 again here five

19:01 so you did three ios to get to five

19:05 and this is not uh a great example but

19:08 you you you see that the work you did

19:10 it's like three

19:11 jumps three hops what if you're reading

19:13 100 you're gonna go all over the place

19:16 to find these values because they are

19:19 although

19:19 they are ordered in the tree but

19:23 the they are they cannot be they are not

19:26 sequential

19:28 once you find a value it has nothing to

19:31 do with the value 5

19:32 despite them being next to each other in

19:35 logical view so now we're looking at a b

19:37 plus three and the difference between a

19:39 b plus three and a b

19:40 three is really just the

19:44 realization that we're wasting

19:47 uh space we're wasting space by

19:52 putting the values in next to the key in

19:55 the elements

19:56 it says okay what if i don't put the

19:58 value here

20:01 so okay you have to put the value

20:02 eventually right no

20:04 i'm going to put the values at the at

20:06 the leaf nodes only

20:08 so now that oh saying that means you

20:11 have to duplicate your keys

20:12 as we're seeing the value three here

20:15 also appear

20:16 at the leaf but that is

20:19 a very small cost compared to the

20:22 benefits that we're getting

20:23 all of a sudden now these intermediate

20:27 nodes that we're searching

20:28 are so tiny we're only searching keys

20:32 here they effectively can fit entirely

20:35 in the memory

20:36 so i can traverse this stuff without

20:38 actually having to worry about the value

20:41 of them

20:42 but once i find something here's another

20:45 benefit of a b plus 3. once you find

20:48 something there is a pointer to the next

20:50 actual key so technically once you find

20:54 something you can find pretty much

20:55 everything

20:56 range queries in this case and a b plus

20:58 three are

20:59 much more effective than an mb3

21:02 because if i give you hey find me all

21:04 values between

21:05 one and five in a b3

21:10 if you go to a b3 between one and five

21:12 you have to search one

21:13 and again you have to find obviously

21:16 two you have to find three you have to

21:18 have four i have to five

21:19 because you have to find every one of

21:22 them

21:23 the values itself right so you have to

21:25 traverse go

21:26 back and forth the tree to find the

21:29 stuff however

21:30 in a b plus three just go and find one

21:35 we found one once you found one

21:38 just go because you know everything is

21:40 sequential right if

21:42 index are always sorted by default so if

21:44 it's sorted then okay

21:45 where's the next value oh there's two

21:47 there's a point a nice beautiful pointer

21:49 now you might say hussein isn't the

21:51 pointer adding the pointer is a cost of

21:54 course there's always the cost to

21:55 everything

21:56 so people studies okay the addition of

21:58 that pointer really doesn't really

22:00 affect much but the value of having this

22:04 beautiful range queries where i can

22:05 search and then immediately find two

22:08 and three and four and five these might

22:10 fit into a single page

22:12 if it's like five but let's say you're

22:14 searching for i don't know

22:16 two thousand or three thousand right you

22:18 might read

22:19 it really depends again on the data size

22:21 and the values and all that stuff you

22:22 might read maybe three or four pages

22:24 right depends on the on the size and all

22:26 that stuff right

22:28 but yeah that is the benefits of the

22:30 difference between b

22:32 trees and b plus trees almost b3s are

22:35 never used

22:37 in databases right although i see some

22:40 value

22:40 to the simplicity of the b3 right

22:44 but studies shows that the cost the

22:46 addition cost of the b3 which is b

22:49 which is the duplication because you

22:50 have to duplicate the key itself

22:53 in the intermediate node and in the leaf

22:55 node plus

22:57 the addition of the pointers to to

23:00 l to to to do a linked list at the

23:03 leaflet

23:04 is is almost negligible to the

23:08 to the cost of the b3 right itself

23:12 but if you like i mean if you're for

23:15 instance

23:16 if you absolutely know that your

23:19 workload is gonna always gonna be okay i

23:21 don't know key value store where you're

23:23 always searching by one value

23:24 you're never never gonna search by

23:26 multiple values

23:27 then you can use a b3 right

23:31 but i still think that it's very hard

23:35 it's harder to fit a b3

23:37 in memory fully compared to a b

23:40 plus three right why

23:44 a b3 is is you have to put it all or

23:47 nothing really so a b3 is really it's

23:49 it's all or nothing you can

23:51 you can you have to put it all in memory

23:53 i mean you can play tricks with paging

23:55 it's like okay let's page some part of

23:57 the tree but not all of it but

23:59 yeah it's it's really unpredictable

24:02 right

24:02 but b plus three i've got reference post

24:05 case because that

24:06 that's the database i try to focus on

24:09 according to postgres when they

24:10 implemented their

24:11 b plus trees 99 of the cost and storage

24:15 of b trees

24:17 is in the leaf this is

24:20 just one percent all this nodes that

24:23 helps the reverser just to

24:25 get to one leaf is one percent

24:28 so definitely you can fit a one percent

24:33 in it's right in in memory let's say

24:35 your index

24:36 is 100 gig that's a huge index by the

24:39 way if you think about it right

24:41 then you can fit if you have enough

24:43 memory if you can fit one gigabyte

24:46 in memory that is fine

24:50 then the traversal are so fast to get to

24:53 one leaf

24:54 and then you're gonna start doing some

24:56 io once you get

24:58 to the actual leaf value right

25:01 and i i think that's still i'm still

25:03 actually

25:04 thinking about this stuff like is there

25:06 benefits to using just pure b3 versus b

25:08 plus three but always to me

25:10 it looks like always b b plus three

25:12 always wins over b3

25:14 right that's what i what i noticed i

25:16 noticed like mongodb

25:17 even being a key value store they they

25:19 use b plus 3 they don't use b3

25:21 and maybe that that's uh that's a that's

25:24 sort of actually

25:24 let's check oh i take that back

25:28 look at that mongodb uses b3 data

25:31 structure uh

25:32 they did not specify except the b plus

25:34 three it looks like they are using just

25:36 a b3

25:38 you know what i think that's enough uh

25:40 showing off the the

25:42 screen let's discuss this part a little

25:44 bit

25:45 you know this this reminds me of what

25:49 it's like this whole thing with mongodb

25:52 and just b3

25:53 according to their dock they don't not

25:55 they're not using b plus three

25:57 okay they're using a pure b3 so

26:00 my guess is they're gonna have trouble

26:03 fitting that tree

26:04 in completely in memory as a result

26:07 because the search

26:08 you you cannot search through it

26:11 effectively

26:12 right just to get it to a leaf it's all

26:15 or nothing

26:16 if it's a b3 because the values are with

26:18 the keys so you're burdened with that

26:22 that made me remember discord remember

26:25 the video we did on discord because i

26:27 remember covering this

26:29 mongodb the discord moved from mongodb

26:31 to i believe cassandra

26:33 and then later they moved to cellar db

26:37 because of this exact thing let me read

26:39 this

26:40 the messages were stored in a mongodb

26:43 collection with a single compound index

26:45 on channel id and created app

26:47 around november 2015 we reached 100

26:50 million stored messages

26:52 and at this time we started to see the

26:54 expected issues appearing

26:56 the data and the index could no longer

27:00 fit in ram and latency started to become

27:04 unpredictable it was time to migrate to

27:07 database more suited for the tax

27:11 again i'm just putting two and two

27:13 together here

27:15 my guess is maybe

27:18 because of the choice mongodb

27:22 used a b3 for their indexes

27:26 they can't fit the indexes efficiently

27:29 in ram compared to if it was

27:33 a pure b plus 3 where you can fit

27:38 the actual traversal part of things

27:42 in memory right and you can

27:46 you can put some of the leaves which

27:48 contains the keys and the data itself

27:51 right which which points either point to

27:53 the row

27:54 tuple or the actual value and

27:58 if you do that maybe that was it that

28:01 was

28:02 caused mongodb to not

28:05 fit could not fit the b the b3 structure

28:08 in

28:08 entirely fully memory because think

28:11 about this way

28:11 if you can't fit in memory entirely

28:15 then you have to go to this but how do

28:17 you know what part to put in the disk

28:18 and what not

28:19 you can't have the choice unfortunately

28:21 you have to put

28:23 you you would decide okay i'm going to

28:24 put half of it on memory and half of it

28:26 but

28:27 how do you know you might be unlucky

28:29 that the queries that

28:31 needs to traverse the tree or in this

28:34 that you will

28:34 you you'll end up hitting the the uh the

28:37 desk

28:38 constantly to retrieve pages just to

28:41 traverse

28:42 bad stuff so to me i still think b

28:46 plus 3 is the superior structure

28:49 regardless of your

28:50 uh really use case if you think about it

28:55 because like that's what i thought it's

28:56 like okay i want a simpler data session

28:58 i'm going to use a

28:59 beautiful simple b tree i don't need to

29:01 pay plus 3 because

29:02 i'm just it's a key value store i'm just

29:04 searching for a key

29:06 and then give me my value and that's why

29:09 was my initial response as it was in the

29:11 video

29:12 right like i started changing my mind

29:14 while making this video

29:16 then it was like wait a second that's

29:19 fine and all if i have a small index but

29:21 if it's a huge index with a lot of stuff

29:25 then if i can't fit all of this stuff in

29:28 memory

29:29 it's gonna spill to disk then i'll end

29:32 up searching all of that stuff

29:34 in disk you might argue hussain

29:37 if your b plus 3 is so large i don't

29:40 know one terabyte

29:42 then you're what is one percent of

29:45 one terabyte it is 10 gig yeah it's

29:47 around 10 gig

29:48 so i mean do you have 10 gig war for ram

29:51 well if you're managing a thousand

29:53 was a petabyte worth of content please

29:57 invest in a better memory you should

30:00 have at least 256 or

30:03 512 ram to fit your 10 gigabit of index

30:07 but think about it this way right it is

30:10 it looks like bps3

30:12 always wins regardless and that's the

30:14 discussion i wanted to have guys

30:15 it says very interesting as like as i

30:18 make these videos

30:19 i keep i keep remembering old videos

30:22 that we covered and i can

30:23 we put things and we links together is

30:25 fascinating i'm gonna reference the

30:26 discord video that i made

30:28 obviously in the description if you're

30:29 interested in that stuff and uh

30:31 that's it for me guys so what did we

30:33 discuss we discussed the beauty of the

30:35 data structure algorithms very important

30:38 to understand not memorize for an

30:41 interview

30:42 actually understand so it helps you once

30:44 you understand

30:45 what things together you can put one two

30:47 and two together and these are oh wait a

30:49 second this doesn't make sense

30:51 and that the power that's the that's

30:53 where the power of the engineer comes

30:55 comes in beauty then we talked about b

30:58 trees and we talked about b

30:59 plus trees and the differences between

31:01 them and how do we

31:03 how do they actually uh

31:06 um how do they actually thrive in an

31:09 actual database production we've seen an

31:11 example of mongodb again that's what

31:12 they say they say

31:13 b3 they didn't say b plus three honest

31:16 uh

31:16 again i'm gonna i might make another

31:18 video about b3s and then how postgres

31:21 effectively determined that the degree

31:24 of b trees because if you think about it

31:27 like

31:30 postgres or other database they don't

31:31 say okay oh we're going to use i don't

31:33 know

31:33 a 2000 degree b3 no

31:36 no they don't do that they derive that

31:40 based on your data type of the index

31:42 you're trying to create

31:43 i'm going to make another video

31:44 discussing that hopefully

31:47 stay awesome goodbye this guy

0:00 Thỉnh thoảng có người hỏi tôi về tầm quan trọng của cấu trúc dữ liệu và thuật toán, và quan điểm của tôi về vấn đề này rất rõ ràng: chúng cực kỳ quan trọng. Nhưng nó còn tùy thuộc vào mục đích bạn học chúng. Nếu bạn chỉ học để vượt qua phỏng vấn hoặc kiếm việc làm, thì chúng chỉ là gánh nặng. Bạn sẽ học thuộc lòng mà không thực sự hiểu chúng để làm gì.

0:23 Nhưng nếu bạn thực sự đào sâu vào cấu trúc dữ liệu, tìm hiểu nguồn gốc, lý do chúng tồn tại và những vấn đề chúng giải quyết, chúng sẽ giúp bạn trở thành một kỹ sư phần mềm giỏi. Bạn sẽ sử dụng chúng để có lợi thế, và không ai có thể vượt mặt bạn vì bạn thực sự biết khi nào nên sử dụng cái gì. Hôm nay tôi sẽ không nói về phát triển hay viết code, mà là về kỹ thuật thực tế, làm việc với cơ sở dữ liệu. Và đó là chủ đề của ngày hôm nay.

1:01 Cây B. Chúng ta sẽ thảo luận tất tần tật về khái niệm cây B, cách nó được cải tiến thành B+ Tree, sự khác biệt, ưu điểm, những vấn đề chúng giải quyết và hạn chế của chúng. Tất cả sẽ có trong tập này. Hãy cùng theo dõi chương trình kỹ thuật backend với người dẫn chương trình Hussein Nasser. Và nếu các bạn thích những cuộc thảo luận chuyên sâu về khái niệm cơ sở dữ liệu của chúng tôi, các bạn có thể tham khảo khóa học giới thiệu về kỹ thuật cơ sở dữ liệu Udemy của tôi, với hơn 14 giờ nội dung độc quyền mà bạn sẽ không tìm thấy ở bất kỳ đâu khác. Nếu bạn quan tâm, hãy xem bình luận được ghim bên dưới và cả phần ghi chú chương trình nếu bạn đang nghe podcast. Nó thực sự hỗ trợ chương trình. Cảm ơn bạn rất nhiều, Scott.

1:49 Được rồi các bạn, vậy là B-Tree. Để thảo luận về cấu trúc dữ liệu này, tại sao nó được phát minh, chúng ta cần quay lại một trường hợp sử dụng rất thực tế. Bạn có một bảng trong cơ sở dữ liệu, một bảng rất lớn với hàng triệu hàng, và bạn muốn tìm kiếm một hàng cụ thể theo ID của nó, ví dụ ID số 1007. Bạn muốn xem ID đó, đúng không? Và bạn không chỉ muốn xem giá trị 1007, mà muốn lấy thêm thông tin từ hàng đó. Nếu bạn muốn tìm kiếm 70, bạn đã biết 70 rồi, bạn không tìm kiếm 17 chỉ để biết nó là 17, bạn muốn nhiều hơn thế, và đó là chìa khóa. 17 là giá trị trong một tập hợp.

2:50 Trước đây, chúng ta thường đọc bảng từng trang một. Một trang có một nghìn hàng, trang khác lại một nghìn hàng, cứ thế đọc. "Không, 1007 không có trong trang nào cả." Vậy là bạn phải đọc từng trang một cho đến khi tìm thấy. Nếu bạn chắc chắn rằng ID này là duy nhất, bạn sẽ dừng tìm kiếm, đúng không? Và thoát ra. Cách này gọi là quét toàn bộ bảng. Bạn đang quét toàn bộ bảng, và nếu nó không phải là duy nhất, bạn biết là còn nhiều hơn thế, cuối cùng bạn sẽ quét toàn bộ bảng. Cách này rất chậm, quét một triệu hàng, hoặc trong trường hợp xấu nhất là hai, ba triệu hàng, rất rất chậm. Tóm lại là nó chậm.

3:30 Vấn đề là chúng ta muốn nó nhanh hơn, đó là mục tiêu của chúng ta. Vậy làm thế nào để tìm kiếm một triệu thứ nhanh hơn? Một cách là song song hóa nó. Chia bảng thành ba, bốn, năm, bảy phần, rồi phân phối công việc cho các luồng hoặc các máy khác nhau để chúng tìm kiếm. Cách này khá phức tạp, nhưng đó là một giải pháp. Một cách khác là phân vùng nó. Phân vùng là một khái niệm rất quan trọng.

4:01 Chúng ta chia bảng thành các phần dựa trên kích thước khóa. Ví dụ, các giá trị từ một đến một nghìn nằm trong phân vùng này, các giá trị từ một nghìn lẻ một đến hai nghìn nằm trong phân vùng khác. Về cơ bản, nó giống như chia nhỏ thành nhiều bảng, đúng không? Một giải pháp khác là tạo một chỉ mục. Chúng ta tìm kiếm trên chỉ mục, một cấu trúc dữ liệu nhỏ, và sau khi tìm thấy, chúng ta nhảy đến trang chính xác cần tìm. Trong tất cả các kịch bản này và nhiều kịch bản khác, chúng ta luôn giảm không gian tìm kiếm. Chỉ vậy thôi. Chúng ta không làm bất kỳ điều kỳ diệu nào cả.

4:40 Tôi đã làm một video về cách làm việc với một bảng một tỷ hàng, dành riêng cho các thành viên của kênh này. Bài học rút ra từ video đó là để làm việc với một bảng một tỷ hàng, bạn cần tránh làm việc với một tỷ hàng. Nghe có vẻ hiển nhiên, nhưng đừng tìm kiếm trong một tỷ bản ghi. Hãy tìm mọi cách để tránh làm việc với các tập dữ liệu lớn, cố gắng phân đoạn và loại bỏ những thứ mà bạn biết chắc chắn sẽ không mang lại kết quả. Đó là bí quyết. Và đây là lúc chủ đề chỉ mục phát huy tác dụng.

5:18 Tôi đã làm một video về lập chỉ mục, các bạn có thể xem lại. Ý tưởng là có một chỉ mục để tôi chỉ có thể tìm kiếm những thứ mà tôi hoàn toàn chắc chắn rằng hàng tôi đang xem, giá trị tôi đang tìm kiếm nằm trong không gian đó, đúng không? Khi bạn thiết kế và cấu trúc chỉ mục của mình theo cách đó, bạn sẽ có một tập hợp nhỏ hơn, bạn sẽ tìm kiếm trong một không gian tìm kiếm nhỏ hơn. Không gian tìm kiếm càng nhỏ, kết quả càng nhanh. Đơn giản như vậy thôi.

6:02 Vậy làm thế nào để chúng ta xây dựng những cấu trúc này? Những cây này đóng vai trò gì? Làm thế nào để chúng ta xây dựng chúng? Trước đây, chúng ta có ý tưởng về

6:16 cây nhị phân, một cấu trúc rất đơn giản và đẹp mắt. Bạn đặt một giá trị lên trên, các giá trị lớn hơn đi sang bên phải, các giá trị nhỏ hơn đi sang bên trái. Cấu trúc dữ liệu rất đơn giản. Ví dụ, nếu chúng ta đặt giá trị 100 ở đây, bất kỳ thứ gì lớn hơn 100 đều đi sang bên phải của cây, đúng không? Và tôi đang chỉ bên phải của tôi, không biết có phải bên phải của bạn không. Bất cứ thứ gì bên trái là nhỏ hơn 100.

6:46 Nếu bạn đang tìm kiếm giá trị, ví dụ 200, bạn luôn bắt đầu từ gốc. Đó là một chi phí, phải nhảy đến gốc. Bạn nói, "Tôi đang tìm kiếm 200." Bạn biết mình đang tìm kiếm gì. 200 lớn hơn hay nhỏ hơn 100? Đây là một phép kiểm tra đơn giản, hầu như không tốn chi phí nào, nhưng nó loại bỏ gần một nửa không gian tìm kiếm, nếu bạn may mắn. Bây giờ bạn chỉ tìm kiếm phía bên tay phải, vì bạn biết rằng 200 sẽ ở trong khu vực đó. Bạn chỉ tìm kiếm từ 100 trở lên, vì vậy bạn đang tìm kiếm ít kết quả hơn. Đây là một ví dụ rất đơn giản, nhưng vấn đề với cây nhị phân là chúng không thực sự cân bằng.

7:40 Điều đó có nghĩa là gì? Lấy ví dụ này. Giả sử gốc là một, và sau đó bất kỳ giá trị nào bạn thêm vào lớn hơn một, điều gì sẽ xảy ra? Hai, ba, bốn, năm, sáu, bảy... Bạn sẽ kết thúc với một không gian tìm kiếm tuyến tính, điều này thực sự vô dụng. Nó được gọi là một cây không cân bằng. Nó gần như chậm hơn cả quét toàn bộ bảng. Bạn sẽ phải nhảy vào nhiều trang để có được giá trị 200, và cuối cùng bạn làm nhiều việc hơn một cách hiệu quả để tìm kiếm nó. Vì vậy, cây nhị phân không thực sự phù hợp với khối lượng công việc của cơ sở dữ liệu vì sự thiếu cân bằng này. Chúng ta cần một cây tự phục hồi, tự cân bằng. Đây là lúc B-Tree xuất hiện.

8:34 Và B-Tree, các bạn biết đấy, chữ "B" thực ra không có nghĩa gì cả. Bài báo gốc không hề nói nó là viết tắt của cái gì. Có thể là "Balanced" (cân bằng), có thể là "Boeing", tên công ty mà phòng thí nghiệm nghiên cứu đã tạo ra bài báo này, hoặc có thể là "Bayer", tên một trong những nhà nghiên cứu. Thực ra nó có thể là bất cứ thứ gì. Và điểm hay của nó là nó thực sự cân bằng. Vậy cân bằng có nghĩa là gì? Nó có nghĩa là khi bạn chèn dữ liệu, cây sẽ tự cân bằng.

9:09 Nếu bạn là một kỹ sư, bạn sẽ tự hỏi: "Chờ đã, nó cân bằng ngay cả khi tôi chèn dữ liệu ư?". Ngay khi bạn nghe thấy điều đó, nếu bạn thực sự chú ý, bạn sẽ biết rằng có một cái giá phải trả, và đó là điều bạn cần xem xét. Có một chi phí cho việc đó, đó là sự tái cân bằng liên tục để tự cân bằng. Vì vậy, bên trái bằng bên phải, nhưng với chi phí là khi tôi viết dữ liệu, tôi liên tục cân bằng cây của mình. Do đó, các thao tác đọc sẽ rất nhanh. B-Tree không là gì ngoài một cây nhị phân tổng quát. Bạn có thể có bất kỳ số lượng con nào, không chỉ hai. Bạn có thể có bảy, thậm chí một nghìn. Các cơ sở dữ liệu thực tế sẽ tính toán điều đó một cách nhanh chóng. Hãy xem một ví dụ.

10:14 Đây là một trong những trang web phổ biến nhất trình bày về cây B, đến từ Đại học San Francisco. Trang web tuyệt vời, thực sự rất đơn giản, đi thẳng vào vấn đề. Chúng ta sẽ giải thích về cây B ở đây. Giả sử B-Tree của tôi có số lượng con tối đa, bậc của cây là ba. Điều đó có nghĩa là nó có thể có tối đa ba nút con. Tôi sẽ chèn một loạt các giá trị. Đầu tiên là giá trị một. Vậy đây sẽ là gốc, là một ở đây.

10:53 Nếu tôi chèn giá trị hai, khi tôi muốn chèn giá trị 2, chúng ta sẽ xem xét: 2 có lớn hơn 1 không? Có, nhưng tôi sẽ không thêm nó làm con vì tôi có thể đặt giá trị 2 vào chính nút đó như một phần tử. Nếu tôi nhận được một yêu cầu chèn nữa, tôi có thể có một giá trị khác. Bạn có thể hỏi: "Jose, bạn có thể thêm bao nhiêu phần tử hoặc khóa vào chính nút đó?". Câu trả lời là bậc tối đa trừ một. Vì vậy, ba trừ một, tối đa là hai. Nếu bây giờ tôi muốn chèn ba, điều gì sẽ xảy ra? Tôi sẽ chèn ba vào đây, nhưng tôi sẽ vượt quá giới hạn của nút này. Vì vậy, tôi sẽ chia nút này, và việc chia nút này gây tốn kém. Đôi khi nó thực sự gây tốn kém, đặc biệt nếu bạn đang thực hiện nhiều thao tác. Việc phân chia trang và thực hiện công việc này là tất cả các thao tác I/O cơ sở dữ liệu. Hãy nghĩ về nó theo cách này khi tôi giải thích.

11:59 Nếu tôi chèn giá trị ba, nó sẽ chèn, nhưng điều gì sẽ xảy ra là hai sẽ được thăng cấp làm gốc, một sẽ ở bên trái và ba sẽ ở bên phải. Hãy tiếp tục và làm điều này. Như chúng ta có thể thấy, bây giờ nếu tôi chèn giá trị bốn, điều gì sẽ xảy ra? Nếu tôi đến đây và nói: "Được rồi, bốn", tôi sẽ thêm bốn. Bốn lớn hơn hai, vì vậy nó sẽ đi sang bên phải của cây, không phải sang bên trái. Khi tôi chèn cái này, nó sẽ đến bốn, nó sẽ thêm

12:38 và sau đó nó sẽ thêm nó như một phần tử khác trong nút bên phải này. Bạn có thể thấy rằng bây giờ nút này có ba và bốn. Vậy làm thế nào để bạn đọc cây này? Hãy tiếp tục đọc nó. Giá trị là 2, là khóa ở đây. Có một thứ ẩn ở đây mà không được hiển thị, đó là giá trị thực tế của điểm đó, con trỏ mà giá trị này trỏ đến. Ở bên trái, chúng ta có giá trị một. Ở bên phải của cây, bất cứ thứ gì lớn hơn hai, chúng ta có nút này. Bây giờ bạn đi đến nút này và bạn tìm thấy ba và bốn là các phần tử trong nút này.

13:17 Hãy thêm năm. Các bạn nghĩ gì sẽ xảy ra khi bạn thêm năm? Năm lớn hơn, vì vậy nó cần phải đi ở đây, đúng không? Nếu tôi thêm nó ngay tại đây, nó sẽ đến nút, nhưng chúng ta vừa vượt quá số lượng phần tử cho phép. Nó chỉ nên là hai. Chúng ta không nên vượt quá hai. Vì vậy, bây giờ bốn sẽ được thăng cấp làm một nút, ba sẽ đi sang bên trái và năm sẽ đi sang bên phải. Vì chúng ta muốn giữ các cấp độ, bốn sẽ được đẩy lên. Chúng ta sẽ có 2 và 4. Hãy thêm nó để chúng ta có thể giải thích điều này. Chúng ta sẽ thêm vào và sau đó thăng cấp bốn đó. Đây là cách bạn đọc điều này.

13:59 Hãy đọc điều này. Điều này hơi khác so với một cây nhị phân. Nút này có giá trị phần tử là hai, một phần tử là bốn. Khóa là hai và bốn. Ở bên trái, bất kỳ giá trị nào nhỏ hơn hai đều ở đây. Bất kỳ giá trị nào nằm giữa hai và bốn đều nằm trong con trỏ này. Bạn đi đến đây và bạn tìm kiếm. Có thể có một phần tử, có thể là 700, tùy thuộc vào bậc của cây. Bất kỳ giá trị nào lớn hơn bốn đều đi sang bên trái. Vì vậy, nó là một cây cân bằng đầy đủ, nhưng hãy nhìn vào công việc mà chúng ta đang làm khi chúng ta chèn và chúng ta chỉ cân bằng và hoàn tác tất cả những thứ đó. Đó là bởi vì chúng ta có một bậc phần tử rất nhỏ về kích thước. Cơ sở dữ liệu không nên sử dụng giá trị ba. Bạn nên có một giá trị lớn như kích thước trang của bạn.

14:51 Nói về B-Tree, hãy nói về những lợi ích của nó. Nếu tôi muốn tìm kiếm giá trị ba, rất đơn giản, đúng không? Trước khi chúng ta đi qua nó, ba nằm giữa hai và bốn. Trước hết, tôi cần phải nhảy đến gốc và nói: "Được rồi, ba ở đâu?". Ba nằm giữa hai và bốn. Vì vậy, tôi cần phải nhảy đến con trỏ này. Tôi theo con trỏ này đến bất kỳ ghi chú nào nó chỉ cho tôi. Chúng ta đang thấy một nút thực tế, nhưng trong cơ sở dữ liệu, đây chủ yếu là một trang. Ít nhất là trong triển khai Postgres, đây là chính trang đó. Đây là một trang, đây là một trang và có hàng ngàn và hàng ngàn phần tử trong trang đó. Đây là một thao tác I/O, đây là một thao tác I/O. Bây giờ tôi đi đến ba và sau đó tôi tìm thấy ba. Về cơ bản, đây là một B-Tree rất ngắn và bạn vừa tìm thấy giá trị ba.

15:49 Tôi không thực sự quan tâm đến giá trị ba. Tôi quan tâm là nội dung của giá trị ba là gì, và đó là giá trị ở đây. Có một cái gì đó không được hiển thị trong sơ đồ này. Tôi ước họ thực sự hiển thị chúng, nhưng có một giá trị, không phải đây chỉ là cây. Chúng ta không chỉ nhìn vào các con số ở đây. Có một số nội dung liên kết với khóa. Nó gần giống như một giá trị khóa, đúng không? Vì vậy, 2 có một giá trị bên cạnh nó.

16:20 Trong B-Tree, mọi phần tử đều có một giá trị gắn liền với nó. Hai có thể có bất kỳ giá trị nào. Trong triển khai Postgres, nó có thể trỏ trực tiếp đến ID bộ. Trong triển khai MySQL, nó trỏ trực tiếp đến khóa chính. Đó là lý do tại sao nếu bạn sử dụng khóa chính trong MySQL như một khóa tốt, thì các chỉ mục của bạn sẽ rất lớn. Hãy cẩn thận với khóa chính bạn sử dụng trong MySQL. Postgres không có vấn đề đó vì mọi thứ đều là khóa phụ và chúng luôn trỏ đến bộ.

17:05 Vậy đó là những gì chúng ta đang xem xét. Tại sao tôi lại nói với bạn rằng có các giá trị ở đây? Bởi vì đó là sự khác biệt so với cấu trúc dữ liệu khác được gọi là B+Tree và những vấn đề nó đã giải quyết. Bây giờ khi tôi tìm kiếm ở đây, đây là một trang, đúng không? Đây là toàn bộ trang. Nếu có hai và giá trị của nó, bất kể giá trị đó là gì, nếu bạn ở trong MySQL thì đó là con trỏ đến khóa chính, vì vậy kiểu dữ liệu khóa chính sẽ đi đến đó. Nếu đó là Postgres là bộ, tôi không biết nếu có hai bit có thể quên kích thước giá trị ID bảng là gì. Đó là ID bộ trong trường hợp đó. Bạn đặt nhiều bit hơn ở đây.

17:52 Trang này sẽ chứa ít phần tử hơn vì chúng ta cũng đang mang theo các giá trị, đúng không? Nếu tôi chỉ có các khóa, tôi có thể chứa nhiều phần tử hơn trong trang của mình. Giả sử trong Postgres, vì nó là 8k, tôi có thể chứa nhiều phần tử hơn ở đó. Kết quả là, tôi có thể tìm kiếm, tôi có thể đi qua nhiều phần tử hơn trong một thao tác I/O so với cấu trúc dữ liệu này có các giá trị. Thành thật mà nói, các giá trị là một gánh nặng. Nếu bạn nghĩ về nó, một điều khác ở đây là nếu tôi đang tìm kiếm ba và năm cùng một lúc thì sao? Làm thế nào để tôi làm điều đó? Hãy tìm kiếm một. Một ở đây, vì vậy tôi sẽ đọc ở đây. Chúng ta đã tìm thấy nó. Bây giờ tôi muốn tìm kiếm ba. Hãy làm lại. Đi đến đây và sau đó ba. Bạn đã thực hiện một cú nhảy đôi để có được giá trị của ba. Tôi muốn tìm kiếm năm. Hãy làm lại. Ở đây, năm. Bạn đã thực hiện ba thao tác I/O để đến năm. Đây không phải là một ví dụ tuyệt vời, nhưng bạn thấy công việc bạn đã làm, nó giống như ba lần nhảy, ba bước nhảy. Điều gì sẽ xảy ra nếu bạn đang đọc 100 giá trị? Bạn sẽ đi khắp nơi để tìm những giá trị này vì mặc dù chúng được sắp xếp theo thứ tự trong cây, nhưng chúng không tuần tự.

19:28 Khi bạn tìm thấy một giá trị, nó không liên quan gì đến giá trị 5, mặc dù chúng ở cạnh nhau trong chế độ xem logic. Bây giờ chúng ta đang xem xét một B+Tree và sự khác biệt giữa B+Tree và B-Tree thực sự chỉ là nhận ra rằng chúng ta đang lãng phí không gian. Chúng ta đang lãng phí không gian bằng cách đặt các giá trị bên cạnh khóa trong các phần tử. Nếu tôi không đặt giá trị ở đây thì sao? Cuối cùng bạn phải đặt giá trị, đúng không? Không, tôi sẽ chỉ đặt các giá trị ở các nút lá. Bây giờ điều đó có nghĩa là bạn phải sao chép các khóa của mình. Như chúng ta đang thấy giá trị ba ở đây cũng xuất hiện ở lá, nhưng đó là một chi phí rất nhỏ so với những lợi ích mà chúng ta đang nhận được.

20:23 Đột nhiên bây giờ những nút trung gian mà chúng ta đang tìm kiếm rất nhỏ, chúng ta chỉ tìm kiếm các khóa ở đây. Chúng có thể phù hợp hoàn toàn trong bộ nhớ một cách hiệu quả. Tôi có thể đi qua những thứ này mà không thực sự phải lo lắng về giá trị của chúng. Nhưng một khi tôi tìm thấy một cái gì đó, đây là một lợi ích khác của B+Tree. Khi bạn tìm thấy một cái gì đó, có một con trỏ đến khóa thực tế tiếp theo. Về mặt kỹ thuật, khi bạn tìm thấy một cái gì đó, bạn có thể tìm thấy hầu hết mọi thứ. Các truy vấn phạm vi trong trường hợp này và B+Tree hiệu quả hơn nhiều so với B-Tree. Nếu tôi yêu cầu bạn tìm cho tôi tất cả các giá trị từ một đến năm trong B-Tree, bạn phải tìm kiếm một và một lần nữa, bạn phải tìm hai, bạn phải tìm ba, bạn phải tìm bốn, bạn phải tìm năm vì bạn phải tìm mọi giá trị của chúng. Bạn phải đi qua lại cây để tìm những thứ đó.

21:30 Tuy nhiên, trong B+Tree, chỉ cần đi và tìm một. Chúng ta đã tìm thấy một. Khi bạn tìm thấy một, chỉ cần đi tiếp vì bạn biết mọi thứ đều tuần tự. Nếu chỉ mục luôn được sắp xếp theo mặc định, thì giá trị tiếp theo ở đâu? Có hai. Có một con trỏ đẹp. Bạn có thể nói: "Hussein, không phải con trỏ thêm con trỏ là một chi phí sao?". Tất nhiên, luôn có chi phí cho mọi thứ. Mọi người nghiên cứu và thấy rằng việc bổ sung con trỏ đó thực sự không ảnh hưởng nhiều, nhưng giá trị của việc có các truy vấn phạm vi đẹp này, nơi tôi có thể tìm kiếm và sau đó ngay lập tức tìm thấy hai và ba và bốn và năm, những điều này có thể phù hợp với một trang duy nhất. Nếu nó giống như năm, nhưng giả sử bạn đang tìm kiếm hai nghìn hoặc ba nghìn, bạn có thể đọc, nó thực sự phụ thuộc vào kích thước dữ liệu và các giá trị và tất cả những thứ đó. Bạn có thể đọc có lẽ ba hoặc bốn trang. Tùy thuộc vào kích thước và tất cả những thứ đó.

22:28 Đó là những lợi ích của sự khác biệt giữa cây B và cây B+. Hầu như B-Tree không bao giờ được sử dụng trong cơ sở dữ liệu. Mặc dù tôi thấy một số giá trị cho sự đơn giản của B-Tree. Nhưng các nghiên cứu cho thấy chi phí bổ sung của B+Tree, là sự trùng lặp vì bạn phải sao chép chính khóa đó trong nút trung gian và trong nút lá cộng với việc bổ sung các con trỏ để thực hiện một danh sách liên kết tại tờ rơi gần như không đáng kể so với chi phí của B-Tree. Nếu bạn hoàn toàn biết rằng khối lượng công việc của bạn sẽ luôn luôn là một cửa hàng giá trị khóa nơi bạn luôn tìm kiếm theo một giá trị, bạn sẽ không bao giờ tìm kiếm theo nhiều giá trị, thì bạn có thể sử dụng B-Tree.

23:31 Nhưng tôi vẫn nghĩ rằng nó rất khó. Khó hơn để phù hợp với B-Tree trong bộ nhớ hoàn toàn so với B+Tree. Tại sao? B-Tree là bạn phải đặt tất cả hoặc không có gì thực sự. B-Tree thực sự là tất cả hoặc không có gì. Bạn phải đặt tất cả vào bộ nhớ. Bạn có thể chơi các thủ thuật với việc phân trang. Nó giống như phân trang một phần của cây, nhưng không phải tất cả. Nó thực sự không thể đoán trước. Nhưng B+Tree, tôi đã có trường hợp tham khảo bài đăng vì đó là cơ sở dữ liệu tôi cố gắng tập trung vào. Theo Postgres, khi họ triển khai cây B+ của họ, 99 chi phí và lưu trữ của cây B nằm ở lá. Chỉ một phần trăm tất cả các nút này giúp người đảo ngược chỉ để đến một lá là một phần trăm. Chắc chắn bạn có thể phù hợp với một phần trăm trong đó ngay trong bộ nhớ. Giả sử chỉ mục của bạn là 100 gig, đó là một chỉ mục rất lớn. Sau đó, bạn có thể phù hợp nếu bạn có đủ bộ nhớ, nếu bạn có thể phù hợp với một gigabyte trong bộ nhớ, điều đó là tốt. Việc đi qua rất nhanh để đến một lá và sau đó bạn sẽ bắt đầu thực hiện một số I/O khi bạn đến

24:58 đến giá trị lá thực tế. Tôi vẫn đang thực sự suy nghĩ về những thứ này như có lợi ích gì khi chỉ sử dụng B-Tree thuần túy so với B+Tree, nhưng luôn luôn đối với tôi, có vẻ như B+Tree luôn thắng B-Tree. Đó là những gì tôi nhận thấy. Tôi nhận thấy như MongoDB, ngay cả khi là một cửa hàng giá trị khóa, họ sử dụng B+Tree. Họ không sử dụng B-Tree và có lẽ đó là một điều đó là một loại thực sự hãy kiểm tra. Ồ, tôi rút lại lời đó. Hãy nhìn vào đó. MongoDB sử dụng cấu trúc dữ liệu B-Tree. Họ đã không chỉ định ngoại trừ B+Tree. Có vẻ như họ chỉ sử dụng B-Tree.

25:38 Bạn biết gì không? Tôi nghĩ thế là đủ để khoe màn hình. Hãy thảo luận phần này một chút. Điều này khiến tôi nhớ đến những gì nó giống như toàn bộ điều này với MongoDB và chỉ B-Tree. Theo tài liệu của họ, họ không sử dụng B+Tree. Họ đang sử dụng một B-Tree thuần túy. Tôi đoán là họ sẽ gặp khó khăn trong việc phù hợp với cây đó hoàn toàn trong bộ nhớ do đó vì việc tìm kiếm bạn không thể tìm kiếm nó một cách hiệu quả. Chỉ để đến một lá, nó là tất cả hoặc không có gì nếu nó là B-Tree vì các giá trị nằm với các khóa, vì vậy bạn bị gánh nặng với điều đó.

26:22 Điều đó khiến tôi nhớ đến Discord. Hãy nhớ video chúng ta đã thực hiện trên Discord vì tôi nhớ đã đề cập đến điều này. MongoDB, Discord đã chuyển từ MongoDB sang tôi tin là Cassandra và sau đó họ chuyển sang cellar DB vì chính điều này. Hãy để tôi đọc điều này. Các tin nhắn được lưu trữ trong một bộ sưu tập MongoDB với một chỉ mục tổng hợp duy nhất trên ID kênh và ứng dụng đã tạo. Vào khoảng tháng 11 năm 2015, chúng tôi đã đạt 100 triệu tin nhắn được lưu trữ và vào thời điểm này, chúng tôi bắt đầu thấy các vấn đề dự kiến xuất hiện. Dữ liệu và chỉ mục không còn có thể phù hợp với RAM và độ trễ bắt đầu trở nên khó đoán. Đã đến lúc di chuyển sang cơ sở dữ liệu phù hợp hơn cho thuế.

27:11 Một lần nữa, tôi chỉ đang xâu chuỗi các sự kiện lại với nhau ở đây. Tôi đoán có lẽ vì MongoDB đã chọn sử dụng B-Tree cho các chỉ mục của họ, họ không thể phù hợp với các chỉ mục một cách hiệu quả trong RAM so với nếu đó là B+Tree thuần túy, nơi bạn có thể phù hợp với phần đi qua thực tế của mọi thứ trong bộ nhớ. Bạn có thể đặt một số lá có chứa các khóa và chính dữ liệu, cái nào chỉ hoặc trỏ đến bộ hàng hoặc giá trị thực tế. Nếu bạn làm điều đó, có lẽ đó là điều đó đã khiến MongoDB không phù hợp, không thể phù hợp với cấu trúc B-Tree hoàn toàn trong bộ nhớ. Hãy nghĩ theo cách này, nếu bạn không thể phù hợp hoàn toàn trong bộ nhớ, thì bạn phải đi đến điều này, nhưng làm thế nào để bạn biết phần nào để đặt trong đĩa và phần nào không? Thật không may, bạn không thể có sự lựa chọn. Bạn phải quyết định, tôi sẽ đặt một nửa trong bộ nhớ và một nửa, nhưng làm thế nào để bạn biết bạn có thể không may mắn rằng các truy vấn cần đi qua cây hoặc trong đó bạn sẽ kết thúc việc nhấn liên tục vào bàn để truy xuất các trang chỉ để đi qua những thứ tồi tệ.

28:42 Đối với tôi, tôi vẫn nghĩ B+Tree là cấu trúc vượt trội bất kể trường hợp sử dụng thực sự của bạn. Tôi muốn một phiên dữ liệu đơn giản hơn, tôi sẽ sử dụng một cây B đơn giản đẹp. Tôi không cần phải trả thêm chi phí của B+Tree vì tôi chỉ là một cửa hàng giá trị khóa, tôi chỉ tìm kiếm một khóa và sau đó cho tôi giá trị của tôi. Đó là lý do tại sao phản ứng ban đầu của tôi như trong video. Tôi bắt đầu thay đổi suy nghĩ của mình khi thực hiện video này, nó giống như chờ một chút, điều đó là tốt và tất cả nếu tôi có một chỉ mục nhỏ, nhưng nếu đó là một chỉ mục lớn với rất nhiều thứ, thì nếu tôi không thể phù hợp với tất cả những thứ này trong bộ nhớ, nó sẽ tràn vào đĩa, thì cuối cùng tôi sẽ tìm kiếm tất cả những thứ đó trong đĩa. Bạn có thể tranh luận: "Hussein, nếu B+Tree của bạn quá lớn, một terabyte, thì một phần trăm của một terabyte là gì? Nó là 10 gig." Vâng, nó vào khoảng 10 gig. Bạn có 10 gig RAM không? Nếu bạn đang quản lý một petabyte nội dung, vui lòng đầu tư vào một bộ nhớ tốt hơn. Bạn nên có ít nhất 256 hoặc 512 RAM để phù hợp với 10 gigabit chỉ mục của bạn.

30:07 Hãy nghĩ về nó theo cách này. Có vẻ như B+Tree luôn thắng bất kể và đó là cuộc thảo luận tôi muốn có với các bạn. Rất thú vị như khi tôi thực hiện những video này, tôi cứ nhớ những video cũ mà chúng ta đã đề cập và chúng ta đặt mọi thứ và chúng ta liên kết với nhau thật hấp dẫn. Tôi sẽ tham khảo video Discord mà tôi đã thực hiện rõ ràng trong phần mô tả nếu bạn quan tâm đến những thứ đó và đó là tất cả đối với tôi các bạn. Vậy chúng ta đã thảo luận gì? Chúng ta đã thảo luận về vẻ đẹp của các thuật toán cấu trúc dữ liệu rất quan trọng để hiểu không ghi nhớ cho một cuộc phỏng vấn thực sự hiểu để nó giúp bạn một khi bạn hiểu những điều với nhau, bạn có thể đặt một hai và hai lại với nhau và đây là điều này không có ý nghĩa và đó là sức mạnh đó là nơi sức mạnh của kỹ sư đến vẻ đẹp sau đó chúng ta đã nói về cây B và chúng ta đã nói về cây B+ và sự khác biệt giữa chúng và làm thế nào để chúng ta thực sự phát triển trong một sản xuất cơ sở dữ liệu thực tế. Chúng ta đã thấy một

31:11 ví dụ về MongoDB. Một lần nữa, đó là những gì họ nói. Họ nói B-Tree, họ đã không nói B+Tree trung thực. Một lần nữa, tôi sẽ có thể thực hiện một video khác về B-Tree và sau đó Postgres đã xác định hiệu quả bậc của cây B như thế nào vì nếu bạn nghĩ về nó như Postgres hoặc cơ sở dữ liệu khác, họ không nói, được rồi, chúng ta sẽ sử dụng một cây B bậc 2000. Không, không, họ không làm điều đó. Họ suy ra điều đó dựa trên kiểu dữ liệu của chỉ mục bạn đang cố gắng tạo. Tôi sẽ thực hiện một video khác thảo luận về điều đó hy vọng. Luôn tuyệt vời. Tạm biệt anh chàng này.