Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
All right, a round of applause for DJ Cash, thank you. A lot to cover. People have comments and feedback for you, so we'll get to that in a second.
Được rồi, xin một tràng pháo tay cho DJ Cash, cảm ơn bạn. Hôm nay có rất nhiều nội dung. Mọi người có một số nhận xét và phản hồi dành cho các bạn, lát nữa chúng ta sẽ nói đến.
But this is the first time we've started on time all semester, so yay, awesome.
Nhưng đây là lần đầu tiên trong cả học kỳ chúng ta bắt đầu đúng giờ, hoan hô, tuyệt vời.
And it's also the most important lecture, because it's maybe the most important data structure in all computer science, in all the world, is maybe B+trees, and so hopefully today I'll convey to you why that's the case.
Và đây cũng là bài giảng quan trọng nhất, vì có lẽ đây là cấu trúc dữ liệu quan trọng nhất trong toàn bộ khoa học máy tính, trên toàn thế giới, đó có thể là B+tree, và hy vọng hôm nay tôi sẽ truyền đạt cho các bạn lý do vì sao như vậy.
I don't care about any of the data, I mean, you care about them because you need them, but it's all about the B+tree, that's the most important thing.
Tôi không quan tâm đến dữ liệu, ý tôi là, các bạn quan tâm đến chúng vì các bạn cần chúng, nhưng tất cả là về B+tree, đó là điều quan trọng nhất.
All right, so again, reminder, project one is due this Sunday coming up. We had a recitation last week, the video is on Piazza, go to that post there along with the slides.
Được rồi, nhắc lại một lần nữa, project một đến hạn vào Chủ nhật này. Tuần trước chúng ta có một buổi thảo luận, video có trên Piazza, hãy vào bài đăng đó, cùng với các slide.
And then, as I said at the beginning of the semester, for every project, since they're all due on Sundays and we don't have office hours on Saturdays and Sundays normally, but the day before the project is due, we have a special Saturday office hours with multiple TAs for multiple hours on campus, so you can come and ask, hopefully, what aren't last minute questions, like how to get started, like more deeper things to help you try to debug things.
Và như tôi đã nói đầu học kỳ, với mỗi project, vì tất cả đều đến hạn vào Chủ nhật và bình thường chúng ta không có giờ hỏi đáp vào thứ Bảy và Chủ nhật, nhưng vào ngày trước hạn nộp project, chúng ta có buổi giờ hỏi đáp đặc biệt vào thứ Bảy với nhiều trợ giảng trong nhiều giờ ngay tại trường, để các bạn có thể đến và hỏi, hy vọng là không phải những câu hỏi phút chót, như cách bắt đầu làm, mà là những vấn đề sâu hơn để giúp các bạn gỡ lỗi.
Okay, then homework three will be released on Wednesday, and that'll be due on October 5th.
Được rồi, bài tập về nhà ba sẽ được đăng vào thứ Tư, và hạn nộp là ngày 5 tháng 10.
And then just to put this on your radar, the midterm exam will be in this room on Wednesday, October 8th, and it's going to cover lecture one to 11 inclusive, all that material up to, including but not the week of the exam, so the week before the exam, all of that will be on there.
Và để các bạn lưu ý trước, kỳ thi giữa kỳ sẽ diễn ra tại phòng này vào thứ Tư, ngày 8 tháng 10, và sẽ bao gồm từ bài giảng một đến bài 11, tính cả bài 11, toàn bộ nội dung đến hết, nhưng không bao gồm tuần diễn ra kỳ thi, tức là tuần trước kỳ thi, tất cả nội dung đó sẽ có trong đề.
And then I'll release a study guide with a practice exam next week. Okay, any questions about any of these things?
Và tuần sau tôi sẽ đăng hướng dẫn ôn tập cùng một đề thi thử. Được rồi, có câu hỏi nào về những điều này không?
All Right, so also starting today is we're kicking off the beginning of our seminar series this semester.
Được rồi, hôm nay chúng ta cũng bắt đầu chuỗi seminar của học kỳ này.
So a bunch of you emailed and reached out and said, "I love databases, maybe not as obsessively as much as I am, but like I do.
Nhiều bạn đã gửi email và nói: "Em yêu cơ sở dữ liệu, có thể không đến mức ám ảnh như thầy, nhưng em cũng yêu.
But like, how can I get more databases in my life and go beyond the course?" So again, we have these optional seminars starting today, every Monday.
Vậy làm sao để có thêm cơ sở dữ liệu trong cuộc sống và đi xa hơn khóa học ạ?" Vì vậy, chúng ta có các seminar tùy chọn này bắt đầu từ hôm nay, vào mỗi thứ Hai.
And the theme this semester will be on Iceberg.
Và chủ đề của học kỳ này sẽ là Iceberg.
If you don't know what Iceberg is, it's one of the most important pieces of database technology that's come around the last three or four or five years.
Nếu các bạn chưa biết Iceberg là gì, thì đó là một trong những công nghệ cơ sở dữ liệu quan trọng nhất xuất hiện trong ba, bốn hay năm năm qua.
There's a reason why Databricks paid, I think, $2 billion for it, billing with a B. Snowflake tried to buy them for $600 million.
Có lý do để Databricks đã trả, tôi nhớ là 2 tỉ đô la cho nó, tỉ với chữ B. Snowflake đã cố mua họ với giá 600 triệu đô la.
Databricks came in and kneecapped them and took it for $2 billion. So today will be introduction to Iceberg. And then next week will be Hudi, which is the alternative to Iceberg.
Databricks nhảy vào, chặn đường họ và mua với giá 2 tỉ đô la. Vậy hôm nay sẽ là phần giới thiệu về Iceberg. Và tuần sau sẽ là Hudi, giải pháp thay thế cho Iceberg.
But these sort of technology or systems were built at the same time. Iceberg came out of Netflix. Hudi came out of Uber. Iceberg is the dominant one.
Những công nghệ hay hệ thống này được xây dựng cùng thời điểm. Iceberg ra đời từ Netflix. Hudi ra đời từ Uber. Iceberg là bên chiếm ưu thế.
And then following up to that, we'll have MotherDuck give a talk about the DuckLake system, which is another alternative to Iceberg. Okay. Again, this is optional. All right.
Và tiếp theo đó, MotherDuck sẽ có một buổi nói chuyện về hệ thống DuckLake, một giải pháp thay thế khác cho Iceberg. Được rồi. Nhắc lại, phần này là tùy chọn. Được chứ.
So what I do want to cover is the feedback we've gotten through the course. Believe it or not, we get emails and we get messages on YouTube, and we do read them.
Điều mình muốn điểm qua là các phản hồi mà chúng ta nhận được trong suốt khóa học. Tin hay không tùy bạn, chúng mình nhận email và tin nhắn trên YouTube, và chúng mình có đọc chúng.
So the first feedback we got is actually for DJ Cash. So the first guy says he heard your radio show, which I heard went really, really well, from what I heard.
Phản hồi đầu tiên thực ra dành cho DJ Cash. Anh chàng đầu tiên nói anh ấy đã nghe chương trình radio của bạn, mà theo mình nghe nói thì diễn ra rất, rất tốt.
He's basically saying, like, you need to get more money. Not me, you. Just get more money.
Về cơ bản anh ta nói là, bạn cần kiếm thêm tiền. Không phải mình, mà là bạn. Cứ kiếm thêm tiền đi.
This guy, sweating the glove, says they got the best beats and that he wants to buy your merch. So you're doing that, right? You're releasing something? We're working on it right now.
Anh chàng này, sweating the glove, nói là các bạn có những beat hay nhất và anh ấy muốn mua đồ lưu niệm của bạn. Vậy bạn đang làm vậy phải không? Bạn sắp phát hành thứ gì đó chứ? Chúng mình đang làm đây.
You're releasing, like, stickers and shirts or something? T-shirts, yeah. Okay. All right. Awesome. So that'll be available for DJ Cash coming up.
Bạn sẽ phát hành sticker và áo gì đó à? Áo thun, đúng rồi. Được. Tuyệt vời. Vậy là sắp tới sẽ có đồ của DJ Cash.
For me, somebody said in the first lecture that I wasn't hyped up enough. I wasn't speaking fast enough so that you could still watch me at 1.25x. So that was surprising.
Còn với mình, có người nói ở bài giảng đầu tiên là mình chưa đủ hứng khởi. Mình nói chưa đủ nhanh nên họ vẫn có thể xem mình ở tốc độ 1.25x. Điều đó làm mình bất ngờ.
Again, maybe I was down that day, but I get excited and I start speaking really fast. I'm surprised this guy's complaining that I was too slow.
Có thể hôm đó mình hơi xuống tinh thần, nhưng mình hay phấn khích rồi bắt đầu nói rất nhanh. Mình ngạc nhiên là anh chàng này lại phàn nàn rằng mình nói quá chậm.
And then this guy says that you can't be a nerd or a gangster. You can be either a nerd or a gangster, but you can't be both.
Và anh chàng này nói rằng bạn không thể vừa là mọt sách vừa là dân anh chị. Bạn có thể là mọt sách hoặc là dân anh chị, nhưng không thể là cả hai.
And I don't want to comment about my past, but, like, was I arrested? Yes. Am I here teaching you guys? Yes. Databases? Yes.
Mình không muốn bình luận về quá khứ của mình, nhưng mình có bị bắt không? Có. Mình có đứng đây dạy các bạn không? Có. Dạy cơ sở dữ liệu? Có.
So I'm not saying I was doing something really malicious, but, like, whatever. I know a lot of people that have gotten in a lot of trouble in life and they end up doing databases.
Mình không nói là mình đã làm điều gì thật sự xấu xa, nhưng thôi kệ. Mình biết rất nhiều người từng gặp rắc rối lớn trong đời và cuối cùng họ lại làm về cơ sở dữ liệu.
So this guy doesn't know what he's talking about. Plus, he's got a phone with his kid. So that's his problem. All right. But one feedback that is actually correct.
Nên anh chàng này không biết mình đang nói gì. Hơn nữa, anh ta còn có điện thoại với con mình. Đó là vấn đề của anh ta. Được rồi. Nhưng có một phản hồi thực sự đúng.
This guy here pointed out that I made a mistake in, I think, lecture six, where I talked about how there's a distinction between OLTP and OLAP.
Anh chàng này chỉ ra rằng mình đã nhầm ở bài giảng sáu, mình nghĩ vậy, khi mình nói về sự khác biệt giữa OLTP và OLAP.
And I made the claim that OLAP was coined by Jim Gray. And this guy points out, and he's absolutely correct, that it actually wasn't Jim Gray.
Và mình đã khẳng định rằng thuật ngữ OLAP do Jim Gray đặt ra. Và anh chàng này chỉ ra, và anh ấy hoàn toàn đúng, rằng thật ra không phải Jim Gray.
It was the other Turing Award winner in databases, although there's four of them. It was one of the other ones. Ted Codd, the guy that invented the relational model.
Đó là một người đoạt giải Turing khác về cơ sở dữ liệu, dù có tất cả bốn người. Đó là một trong số những người còn lại. Ted Codd, người đã phát minh ra mô hình quan hệ.
He was the one that was getting paid to write an article about, like, hey, here's what OLAP is. And then the article got retracted once they found out it was.
Ông ấy là người được trả tiền để viết một bài báo về chuyện kiểu như, này, OLAP là thế này. Rồi bài báo bị rút lại khi người ta phát hiện ra chuyện đó.
He was basically kind of shilling for this company called S-Base, which is a data cube. You don't know where the data cube is. It's another way to do analytical column stores.
Về cơ bản ông ấy đã quảng cáo giúp một công ty tên là S-Base, công ty làm về data cube. Bạn không biết data cube là gì đâu. Đó là một cách khác để làm column store phục vụ phân tích.
But this is how people did things in the 90s. And so he's right that in this lecture here, when I show this picture, it wasn't Jim Gray.
Nhưng đó là cách người ta làm việc vào những năm 90. Và bạn ấy nói đúng, trong bài giảng này, khi tôi chiếu bức hình này, đó không phải là Jim Gray.
It was Ted Codd. OK? So again, feedback like that is super useful. Maybe not be, you know, complaining about me, but feedback for Cash and feedback for the course material is always appreciated.
Đó là Ted Codd. OK? Nên những phản hồi như vậy rất hữu ích. Có thể không phải là phàn nàn về tôi, nhưng phản hồi cho Cash và phản hồi về tài liệu của khóa học thì lúc nào cũng được trân trọng.
OK. The last class, we were talking about hash tables. We said these are an important data structure you need in your database system to support various functionalities, various parts of the system.
OK. Buổi trước, chúng ta đã nói về bảng băm. Chúng ta nói đây là một cấu trúc dữ liệu quan trọng mà bạn cần trong hệ cơ sở dữ liệu để hỗ trợ nhiều chức năng khác nhau, nhiều phần khác nhau của hệ thống.
And we spent a lot of time talking about static hash tables. We kind of rushed at the end on dynamic hash tables.
Và chúng ta đã dành nhiều thời gian nói về bảng băm tĩnh. Ở cuối buổi, chúng ta hơi vội với bảng băm động.
So I'll pick that up again and go over that one more time.
Nên tôi sẽ nhắc lại và đi qua phần đó thêm một lần nữa.
But most of the time, these hash tables that we're talking about will be used as, again, for internal data structures, like things to keep track of, like your page table and so forth.
Nhưng phần lớn các bảng băm mà chúng ta đang nói đến sẽ được dùng làm các cấu trúc dữ liệu nội bộ, như những thứ để theo dõi, ví dụ bảng trang (page table) và các thứ tương tự.
Right? Not so much for indexes, which we'll see mostly how they're going to be used in B+trees today. Right?
Đúng không? Không phải để làm chỉ mục, mà hôm nay chúng ta sẽ thấy chỉ mục chủ yếu được dùng trong B+tree như thế nào. Đúng không?
So again, remember last class, when we finished off with dynamic hashing, there was essentially, there was three schemes. There was chained hashing, where you just keep adding things to this long chain.
Vậy nên hãy nhớ lại buổi trước, khi chúng ta kết thúc với băm động, về cơ bản có ba lược đồ. Có băm theo chuỗi (chained hashing), nơi bạn cứ thêm phần tử vào một chuỗi dài.
We said, oh, that kind of sucks because now it's in the worst case scenario. You're regressing to a linear scan and you're hitting up O(N).
Chúng ta nói, ồ, cái đó tệ vì trong trường hợp xấu nhất bạn thoái hóa thành quét tuyến tính và phải chịu O(N).
So we talked about these two approaches, extendible hashing and linear hashing. So I'm going to quickly just go over the example again. And then we didn't get through deletes for linear hashing.
Nên chúng ta nói về hai cách tiếp cận này, extendible hashing và linear hashing. Vì vậy tôi sẽ nhanh chóng đi lại ví dụ đó. Và chúng ta chưa kịp làm xong phần xóa của linear hashing.
So I want to cover that as well. Again, so these are two approaches that allow us to reorganize and resize our hash table without having to reorganize everything.
Nên tôi cũng muốn nói về phần đó. Một lần nữa, đây là hai cách tiếp cận cho phép chúng ta tổ chức lại và thay đổi kích thước bảng băm mà không phải tổ chức lại toàn bộ.
Right?
Đúng không?
When we had these static hash tables, When we ran out of space or the fill factor got too big, we then basically had to make a second copy of a hash table, usually double the size of the original one, and then take all the keys out of the first one and put them in the second one.
Với các bảng băm tĩnh, khi hết chỗ hoặc hệ số lấp đầy quá lớn, về cơ bản chúng ta phải tạo một bản sao thứ hai của bảng băm, thường có kích thước gấp đôi bảng ban đầu, rồi lấy tất cả các khóa ra khỏi bảng đầu và đưa vào bảng thứ hai.
Right? And that's a very expensive thing to do, especially if your hash table is really, really big.
Đúng không? Và đó là việc rất tốn kém, đặc biệt nếu bảng băm của bạn rất, rất lớn.
So with extendable hashing and linear hashing, the idea is that we can split buckets incrementally and grow them without having to reorganize everything.
Vì vậy với extendible hashing và linear hashing, ý tưởng là chúng ta có thể tách các bucket một cách tăng dần và mở rộng chúng mà không phải tổ chức lại toàn bộ.
So in the case of extendable hashing, you have this notion of a global bit counter. Basically, it's the number of bits we have to examine in our hashes. Right?
Trong trường hợp extendible hashing, bạn có khái niệm bộ đếm bit toàn cục. Về cơ bản, đó là số bit chúng ta phải xem xét trong các giá trị băm. Đúng không?
So when we hash a value or hash a key, we're always going to get 32 bits or 64 bits.
Vậy khi chúng ta băm một giá trị hoặc băm một khóa, lúc nào chúng ta cũng nhận được 32 bit hoặc 64 bit.
This global marker just says how many bits do we actually need to examine to figure out where to go.
Dấu mốc toàn cục này chỉ cho biết chúng ta thực sự cần xem xét bao nhiêu bit để biết phải đi đến đâu.
And then we had this bucket array that was going to correspond to bits that are part of the hash values.
Và sau đó chúng ta có mảng bucket này sẽ tương ứng với các bit là một phần của các giá trị băm.
So in this case here, we'd have some of the buckets only require one bit, and they end up pointing to the same bucket.
Vậy trong trường hợp này, một số bucket chỉ cần một bit, và cuối cùng chúng trỏ đến cùng một bucket.
And then these other two at the bottom are looking at two bits. All right?
Còn hai bucket ở dưới cùng thì xét hai bit. Được chứ?
So then when we started doing things like a lookup, a hash on A, we would look at the global bit counter. It's set to two.
Vậy khi bắt đầu thực hiện, chẳng hạn, một lookup, băm A, chúng ta sẽ xem bộ đếm bit toàn cục. Nó được đặt bằng hai.
So we know we only need to look at two bits to figure out where in our bucket array do we need to jump to. Right?
Nên chúng ta biết chỉ cần xét hai bit để xác định cần nhảy đến vị trí nào trong mảng bucket. Đúng không?
In this case, 01, we follow that, and we end up with this bucket here at the top.
Trong trường hợp này là 01, ta đi theo nó và đến bucket ở trên cùng này.
We find our key. Same thing. Now we do a put in B. We only need two bits. It lands in this. No problem. That's fine. Now we do a put at C.
Ta tìm thấy khóa. Tương tự. Giờ ta thực hiện put B. Chỉ cần hai bit. Nó rơi vào bucket này. Không vấn đề gì. Ổn. Giờ ta put C.
It requires two bits. But then when we follow the pointer, we land up the bucket here in the middle. But it's out of slots in our buckets. So now we've got our overflow.
Nó cần hai bit. Nhưng khi đi theo con trỏ, ta đến bucket ở giữa này. Nhưng bucket này hết chỗ trống. Vậy là ta bị tràn.
So when we do an overflow in extendible hashing, we're basically going to double the size of our bucket array. In actuality, you actually usually allocate maybe most of it at a large enough size.
Khi xảy ra tràn trong extendible hashing, về cơ bản ta sẽ nhân đôi kích thước mảng bucket. Trên thực tế, người ta thường cấp phát sẵn phần lớn nó ở một kích thước đủ lớn.
You're not doubling over time. Also, too, this thing is just not that big. So it's not like the whole hash table. We have the keys and the values and everything else.
Bạn không nhân đôi dần theo thời gian. Ngoài ra, thứ này cũng không lớn lắm. Nó không phải là toàn bộ bảng băm. Bảng băm có các khóa, các giá trị và mọi thứ khác.
So it's very expensive to double things. In this case, it's not that expensive. So now that I doubled the size, I can split the bucket that overflowed.
Nên nhân đôi nó rất tốn kém. Còn ở đây thì không tốn kém lắm. Giờ đã nhân đôi kích thước, ta có thể tách bucket bị tràn.
And then I set now the global counter to three. And then some of the buckets that weren't split still only require one bit. In that case, they're all pointing to the first bucket.
Rồi ta đặt bộ đếm toàn cục bằng ba. Và một số bucket chưa bị tách vẫn chỉ cần một bit. Trong trường hợp đó, chúng đều trỏ đến bucket đầu tiên.
The second ones that need two bits point to the other one here. And then for the ones that we split before, now they're using three bits. And they're now pointing to two different buckets.
Những bucket cần hai bit thì trỏ đến bucket kia ở đây. Còn những bucket mà ta đã tách trước đó thì giờ dùng ba bit. Và chúng giờ trỏ đến hai bucket khác nhau.
So now when I go back and I want to put C back in, again, now I look at three bits. I find the location in my bucket array.
Giờ khi quay lại và put C vào lần nữa, ta xét ba bit. Ta tìm vị trí trong mảng bucket.
And I follow the pointer to the bucket that I want.
Và đi theo con trỏ đến bucket cần tìm.
So linear hashing was a different approach, where instead of splitting the bucket that overflowed, we're actually going to end up splitting the bucket where something else is pointing to, this thing called a split pointer.
Còn linear hashing là một cách tiếp cận khác, trong đó thay vì tách bucket bị tràn, ta thực ra sẽ tách bucket mà một thứ khác đang trỏ tới, gọi là con trỏ tách.
So there was a question last time. Oh, this seems kind of wasteful. Why are we not splitting the bucket that overflowed? We're just splitting whatever one the split pointer is pointing to.
Lần trước có một câu hỏi: nghe có vẻ hơi lãng phí. Sao không tách bucket bị tràn? Ta chỉ tách bucket nào mà con trỏ tách đang trỏ tới.
And the idea is that over time, things are sort of balanced out. Eventually, you'll end up splitting the bucket that overflowed. And things sort of nicely balance out. Let's go back here.
Ý tưởng là theo thời gian, mọi thứ sẽ cân bằng dần. Cuối cùng, bạn sẽ tách đúng bucket bị tràn. Và mọi thứ cân bằng khá tốt. Ta quay lại đây.
So we still have our bucket array. And now, again, we're not looking at just the bits. It's just sort of what offset we are in our bucket array.
Ta vẫn có mảng bucket. Và giờ, ta không chỉ xét các bit nữa. Mà là xét độ lệch của ta trong mảng bucket.
And then we have a split pointer that's just a demarcation to say, what's the next bucket we're going to split?
Rồi ta có một con trỏ tách, chỉ như một vạch phân định để cho biết, bucket tiếp theo ta sẽ tách là bucket nào?
So at the very beginning, it's going to, soon as we overflow, we'll end up splitting bucket zero. And there'll be some hash function.
Vậy ngay từ đầu, nó sẽ, ngay khi bị tràn, chúng ta sẽ tách bucket số không. Và sẽ có một hàm băm nào đó.
We just can hash the key, then mod it by n, with n's the size of this bucket array. So we have n at this point, where n equals four.
Ta chỉ cần băm khóa, rồi lấy modulo n, với n là kích thước của mảng bucket này. Vậy tại thời điểm này ta có n, trong đó n bằng bốn.
All right, so now I want to put, so I'm going to get six, hash by six, just say it's the identity hash, mod it by four, and I get two.
Được rồi, bây giờ tôi muốn chèn, tôi sẽ lấy sáu, băm sáu, cứ cho là hàm băm đồng nhất, lấy modulo bốn, và tôi được hai.
And then I know how to jump to my bucket array at offset two. And I land to the bucket that I want. And there's the key I want.
Rồi tôi biết cách nhảy tới mảng bucket tại offset hai. Và tôi đến đúng bucket mình muốn. Và khóa tôi cần ở đó.
Now I'm going to put 17. 17 hashes to, when I mod four, end up with one. It points to that bucket here. But now that bucket is full.
Bây giờ tôi sẽ chèn 17. 17 băm ra, khi lấy modulo bốn, ta được một. Nó trỏ đến bucket này đây. Nhưng bây giờ bucket đó đã đầy.
So I have to overflow. But instead of splitting this, like I did in extendable hashing, I'm going to extend it out, like I do in chained hashing.
Vậy tôi phải xử lý tràn. Nhưng thay vì tách bucket này, như tôi đã làm trong extendible hashing, tôi sẽ mở rộng nó ra, như trong chained hashing.
Just add another bucket and maintain a linked list. But then now, I'm going to split whatever the split pointer is pointing at. In this case here, it's pointing at zero.
Chỉ cần thêm một bucket nữa và duy trì một danh sách liên kết. Nhưng sau đó, tôi sẽ tách bucket mà con trỏ tách đang trỏ tới. Trong trường hợp này, nó đang trỏ tới số không.
So I'm going to go ahead and split that guy at the top, even though that's not the one that overflowed. But this is just how the algorithm and the protocol works.
Vậy tôi sẽ tiến hành tách bucket ở trên cùng, dù đó không phải bucket bị tràn. Nhưng thuật toán và giao thức hoạt động đúng như vậy.
So now what I'm going to do, I'm going to add a new entry to my bucket array. So now I have a slot four at the bottom.
Bây giờ tôi sẽ thêm một mục mới vào mảng bucket. Vậy giờ ta có ô số bốn ở dưới cùng.
And then now I have a second hash key, or hash function, where I'm going to mod it by two times the original one. So before we had n, N equals two.
Và bây giờ ta có khóa băm thứ hai, hay hàm băm thứ hai, trong đó tôi lấy modulo hai lần giá trị ban đầu. Trước đây ta có n, n bằng hai.
And now we're going to mod it by eight. I'm sorry, by four, right? Because it's, sorry, n equals two. Because I have n equals four in the original one going back here.
Và giờ ta sẽ lấy modulo tám. Xin lỗi, bốn chứ, đúng không? Vì, xin lỗi, n bằng hai. Vì ở hàm ban đầu, quay lại chỗ này, tôi có n bằng bốn.
And then now, when I add the new hash function, now it's 2n. So that'll be eight. So eventually, I'll have eight slots in my bucket array.
Và khi thêm hàm băm mới, giờ nó là 2n. Tức là tám. Vậy cuối cùng, tôi sẽ có tám ô trong mảng bucket.
And the split pointers keep moving down. And then at some point, it'll wrap around. And then I start the whole process all over again.
Và con trỏ tách cứ dịch xuống. Rồi tới một lúc nào đó, nó sẽ quay vòng lại. Và tôi bắt đầu lại toàn bộ quá trình từ đầu.
All right, so in this case here, again, so we're going to take whatever the bucket at the top that the split point is pointing at. We're going to end up splitting that.
Được rồi, trong trường hợp này, ta sẽ lấy bucket ở trên cùng mà con trỏ tách đang trỏ tới. Chúng ta sẽ tách nó.
So we're going to look at all the keys that are inside that bucket and figure out, hash them again with the new hash function, and figure out where they go.
Vậy ta sẽ xem tất cả các khóa nằm trong bucket đó và xác định, băm lại chúng bằng hàm băm mới, và xem chúng đi đâu.
In the case of eight, eight stays where it's at because eight mod eight is zero.
Với tám, tám vẫn ở nguyên chỗ cũ vì tám modulo tám bằng không.
So that stays at the top. But then when I take 20 and mod eight, I end up with four. So it lands here at the bottom there.
Nên nó ở lại trên cùng. Nhưng khi lấy 20 modulo tám, tôi được bốn. Nên nó rơi vào đây, ở phía dưới.
OK, so it's not like when I do the second hash. Because I'm just doing 2n in the new hash function, it's not going to land in any arbitrary bucket.
Được rồi, nên không phải khi băm lần hai thì khóa đi đâu cũng được. Vì tôi chỉ dùng 2n trong hàm băm mới, nó sẽ không rơi vào một bucket bất kỳ.
It's either going to be the original bucket or the new bucket I just created. All right, and then this split pointer moves down by one.
Nó hoặc ở bucket ban đầu hoặc ở bucket mới tôi vừa tạo. Được rồi, và sau đó con trỏ tách dịch xuống một ô.
Now when I do a lookup on 20, all right, 20 mod four is zero.
Bây giờ khi tôi tra cứu 20, được rồi, 20 modulo bốn là không.
So when I do my first lookup, I would see that, oh, this thing for the first hash function is zero. Well, the split pointer is pointing at now one.
Vậy ở lần tra cứu đầu tiên, tôi sẽ thấy rằng, với hàm băm đầu tiên, kết quả là không. Nhưng con trỏ tách lúc này đang trỏ tới một.
So since zero is less than one, I know that I've already split it, anything above the split pointer.
Vì 0 nhỏ hơn 1, nên em biết là bucket đó đã được tách rồi, tức là mọi thứ phía trên con trỏ tách.
So to figure out where 20 actually is, I got to hash it again now with the hash function. With the second hash function.
Vậy để tìm xem 20 thực sự nằm ở đâu, em phải băm nó thêm một lần nữa bằng hàm băm. Hàm băm thứ hai.
And then now I'm going to land the location that has the key that I want.
Và khi đó em sẽ đến đúng vị trí chứa khóa mà em cần.
Same thing, get on eight. Eight mod four is just one. One is where the split pointer is at. So one is equal to one.
Tương tự, lấy 8. 8 mod 4 bằng 1. 1 là vị trí con trỏ tách đang trỏ tới. Vậy 1 bằng 1.
So I know I don't need to run the second hash function. I can just jump to the first one and find the thing I'm looking for.
Nên em biết là không cần chạy hàm băm thứ hai. Em chỉ cần nhảy thẳng tới bucket số 1 và tìm thứ mình cần.
Yes, the statement is the decision on when to use hash one or two is determined based on...
Vâng, câu hỏi là quyết định khi nào dùng hàm băm một hay hai thì dựa trên...
It has to do with what the first hash function points at and is above the split pointer. So going back here, I always got to hash the first one.
Nó liên quan đến việc hàm băm đầu tiên trỏ tới đâu và vị trí đó có nằm phía trên con trỏ tách hay không. Quay lại đây, em luôn phải băm bằng hàm đầu tiên trước.
If I hash the first one the first time, I get zero. Zero is less than one, where the split pointer is pointing at.
Nếu băm lần đầu, em được 0. 0 nhỏ hơn 1, là vị trí con trỏ tách đang trỏ tới.
So I know I have to go to the second hash function.
Nên em biết mình phải dùng hàm băm thứ hai.
The statement is, and he's correct, that say I keep splitting because you have overflows. And I'm going to keep adding new entries to my bucket, right, up until I get to seven.
Câu hỏi là, và bạn nói đúng, giả sử tôi cứ tách mãi vì có tràn. Và tôi cứ tiếp tục thêm các mục mới vào bucket, cho đến khi tới 7.
And then at that point, the split pointer wraps back around to zero. I can, yes, throw away the first hash function, key mod n.
Và lúc đó, con trỏ tách quay vòng về 0. Vâng, tôi có thể bỏ hàm băm đầu tiên, key mod n.
And I'll just have, and then key mod 2n will be the new hash function. Or they said the first hash function. And then I'll have key mod 4n after that. Yes.
Và key mod 2n sẽ là hàm băm mới. Hoặc như bạn nói là hàm băm đầu tiên. Rồi sau đó tôi sẽ có key mod 4n. Vâng.
Yeah, his question is, how do we deal with the overflow? It's just the bucket hashing we talked about before, the chain hashing. So just add a pointer, keep going.
Câu hỏi của bạn là, ta xử lý tràn như thế nào? Chính là băm bucket như đã nói trước đây, tức chain hashing. Chỉ cần thêm một con trỏ rồi cứ tiếp tục.
So his question is, yes, he's correct. So say now, say this bucket here, one. Say it was actually at the bottom. And I keep inserting into it, it keeps overflowing.
Vậy câu hỏi của bạn, vâng, bạn nói đúng. Giả sử bucket số 1 này thực ra nằm ở dưới cùng. Và tôi cứ chèn vào nó, nó cứ bị tràn.
Yes, you would keep splitting anything up above the split pointer. Because then eventually, it'll get to it, and then it'll split.
Vâng, bạn sẽ cứ tiếp tục tách những bucket phía trên con trỏ tách. Vì cuối cùng sẽ tới lượt nó, và nó sẽ được tách.
Yes. So your question is, if I insert something again here, does that count as an overflow? Yes.
Vâng. Vậy câu hỏi của bạn là, nếu tôi lại chèn thêm một thứ vào đây, thì có tính là tràn không? Có.
Because, I mean, you could not do it and say, "All right, I'll just keep going until that second bucket is full," because I've already created it, no big deal.
Vì thực ra bạn cũng có thể không làm vậy mà nói: "Được rồi, tôi cứ tiếp tục cho đến khi bucket thứ hai đó đầy," vì tôi đã tạo nó rồi, không sao cả.
But again, think of it at extremes. I don't want to have this really, I have to do a linear scan, jump inside that to find the thing I'm looking for.
Nhưng hãy nghĩ tới các trường hợp cực đoan. Tôi không muốn phải quét tuyến tính, nhảy vào bên trong đó để tìm thứ mình cần.
So if I can avoid that by splitting, it's worth doing that. OK. So again, this is what I've already said before.
Nên nếu tránh được bằng cách tách thì đáng để làm. OK. Vậy đây là điều tôi đã nói trước đó.
Basically, the idea is that we're just going to keep doing this until, even though we're not splitting the one that overflowed, eventually, we will get to this.
Về cơ bản, ý tưởng là ta cứ tiếp tục làm thế cho đến khi, dù ta không tách bucket đã bị tràn, cuối cùng ta cũng sẽ tới được đây.
Right? To do deletes, it's basically just the reverse. So if I want to delete key 20, same thing.
Đúng không? Để xóa thì về cơ bản chỉ là làm ngược lại. Giả sử tôi muốn xóa khóa 20, cũng tương tự.
I first do the first hash function. I get 0. I know 0 is above our split pointer.
Đầu tiên tôi áp dụng hàm băm thứ nhất. Tôi được 0. Tôi biết 0 nằm phía trên con trỏ tách của chúng ta.
So then I'm going to hash it again. And now I get 4. I jump down here. Right? I delete 20. But now the bucket is basically empty.
Vậy nên tôi băm lần nữa. Và bây giờ tôi được 4. Tôi nhảy xuống đây. Đúng không? Tôi xóa 20. Nhưng bây giờ bucket gần như trống.
So you could just leave it there if you wanted to. Or you just do the reverse. You could kill it, roll the split pointer back up.
Nếu muốn, bạn cứ để nguyên đó cũng được. Hoặc bạn làm ngược lại. Bạn có thể loại bỏ nó, rồi lùi con trỏ tách lên trên.
And then that 4 slot in the bucket array, nothing's really pointing to it. Nothing can get to it anyway, because my hash function won't ever jump to it.
Và khi đó ô số 4 trong mảng bucket, thực ra không còn gì trỏ tới nó. Dù sao cũng không thể tới được nó, vì hàm băm của tôi sẽ không bao giờ nhảy tới đó.
So I could just leave it there.
Nên tôi có thể cứ để nó ở đó.
And the reason why you maybe don't want to clean things up so quick, or eagerly, immediately as it happens, is because if someone now inserts 21 back in, I'm going to be back where I started before and just have another overflow and just do the same thing all over again.
Và lý do bạn có thể không muốn dọn dẹp quá nhanh, hay dọn ngay lập tức khi nó xảy ra, là vì nếu bây giờ có người chèn lại 21 vào, tôi sẽ quay về trạng thái ban đầu và lại bị tràn thêm một lần nữa rồi lại phải làm y hệt lần trước.
So I'm saying in implementations of this, you kind of relax the rules about how quickly you want to revert back on deletes, Because you may be doing the same thing over again.
Ý tôi là, trong các cách triển khai của cấu trúc này, người ta nới lỏng quy tắc về việc phải hoàn nguyên nhanh đến mức nào khi xóa, vì bạn có thể phải làm lại đúng việc đó.
And you're just spending time moving the split pointer back and forth and reusing space, or freeing up space, and then allocating it all over again.
Và bạn chỉ tốn thời gian di chuyển con trỏ tách qua lại và tái sử dụng không gian, hoặc giải phóng không gian rồi lại cấp phát lại từ đầu.
And we'll see the same idea when we talk about B+trees today, where there'll be times where the algorithm says you have to do [it].
Và chúng ta sẽ thấy ý tưởng tương tự khi nói về B+tree hôm nay, khi có những lúc thuật toán nói rằng bạn phải làm [việc đó].
But in real implementations, they'll relax this a little bit, because it'll make a difference in performance. All right, so let's jump into today's lecture, again, the beautiful B+trees.
Nhưng trong các triển khai thực tế, họ sẽ nới lỏng điều này một chút, vì nó tạo ra khác biệt về hiệu năng. Được rồi, vậy chúng ta vào bài giảng hôm nay, lại là B+tree tuyệt đẹp.
So first, we'll do an overview on what the data structure actually looks like. And then we'll talk about different design choices you have in actual implementation.
Đầu tiên, chúng ta sẽ có cái nhìn tổng quan xem cấu trúc dữ liệu này thực sự trông như thế nào. Sau đó chúng ta sẽ nói về các lựa chọn thiết kế khác nhau khi triển khai thực tế.
And then I'll try to plow through as many optimizations as we can until we run out of time.
Và rồi tôi sẽ cố gắng lướt qua càng nhiều tối ưu hóa càng tốt cho đến khi hết giờ.
But I'll cover the main ones that I think are the most interesting, most important ones in the beginning.
Nhưng tôi sẽ nói về những cái chính mà tôi nghĩ là thú vị nhất, và quan trọng nhất ngay từ đầu.
OK, so B+trees are by far the most common data structure you're going to have in databases used for indexes.
Được rồi, B+tree cho đến nay là cấu trúc dữ liệu phổ biến nhất trong cơ sở dữ liệu dùng cho chỉ mục.
Like, when you call CREATE INDEX in nearly every single database system, you're going to be getting a B+tree, or something that looks like a B+tree.
Chẳng hạn, khi bạn gọi CREATE INDEX trong hầu như mọi hệ quản trị cơ sở dữ liệu, bạn sẽ nhận được một B+tree, hoặc thứ gì đó trông giống B+tree.
In systems like Postgres that support hash table indexes, you have to explicitly say, I want to create an index using hash. Because otherwise, the default is always using the B+tree.
Trong các hệ thống như Postgres có hỗ trợ chỉ mục bảng băm, bạn phải nói rõ ràng là, tôi muốn tạo một chỉ mục dùng hash. Vì nếu không, mặc định luôn là dùng B+tree.
The reason why is because B+trees can do any search. You can do point queries. You can do range scans. You can do partial key lookups sometimes. We'll see how to do that.
Lý do là vì B+tree có thể thực hiện mọi kiểu tìm kiếm. Bạn có thể làm truy vấn điểm. Bạn có thể quét theo khoảng. Đôi khi bạn có thể tra cứu theo một phần của khóa. Chúng ta sẽ xem cách làm điều đó.
Whereas in hash tables, you can only do point lookups, like go get this one tuple. I can't do range scans, because everything's unordered in the hash table. So it doesn't mean anything.
Trong khi với bảng băm, bạn chỉ có thể tra cứu điểm, kiểu như lấy đúng một tuple này. Tôi không thể quét theo khoảng, vì mọi thứ trong bảng băm đều không có thứ tự. Nên điều đó không có ý nghĩa gì.
There's no notion of a range, or the values aren't ordered.
Không có khái niệm khoảng, hay các giá trị không được sắp xếp.
And if I have multiple keys, or multiple attributes in my index key, like column A and column B, I can't do a lookup on that index unless I have both columns.
Và nếu tôi có nhiều khóa, hay nhiều thuộc tính trong khóa chỉ mục, như cột A và cột B, thì tôi không thể tra cứu trên chỉ mục đó trừ khi có cả hai cột.
Because I can't go, "Give me the hash on A," and then have that mean anything without B. Because I have to have both of those keys together. So B+trees can be way more versatile.
Vì tôi không thể nói: "Hãy cho tôi giá trị băm trên A", rồi mong điều đó có ý nghĩa mà không có B. Vì tôi phải có cả hai khóa đó cùng nhau. Vì vậy B+tree linh hoạt hơn rất nhiều.
So now, the tricky thing is going to be, the name is going to be confusing.
Giờ điều khó là cái tên sẽ gây nhầm lẫn.
So there's going to be a class of data structures called B-trees, of which there's a specific data structure called a B+tree. But then there's also another data structure called a B-tree.
Có một lớp cấu trúc dữ liệu gọi là B-tree, trong đó có một cấu trúc dữ liệu cụ thể gọi là B+tree. Nhưng lại còn một cấu trúc dữ liệu khác cũng gọi là B-tree.
But the B+tree and the B-tree are both B-tree data structures. But the B+tree is not the same as the B-tree. I'll explain what I mean. OK.
B+tree và B-tree đều là các cấu trúc dữ liệu B-tree. Nhưng B+tree không giống với B-tree. Tôi sẽ giải thích ý tôi. OK.
But generally, this sort of category of data structures refer to what are called balanced trees.
Nhưng nói chung, nhóm cấu trúc dữ liệu này được gọi là cây cân bằng (balanced tree).
The original B-tree paper is roughly attributed around 1970. No one's quite sure exactly when it was added. Maybe 1969, 1970. And the original paper is basically this one here, came out of Boeing.
Bài báo gốc về B-tree được cho là ra đời khoảng năm 1970. Không ai biết chính xác nó xuất hiện khi nào. Có thể 1969, 1970. Và bài báo gốc về cơ bản là bài này đây, xuất phát từ Boeing.
And the second author here, McCreight, he's actually a CMU alum. He did his PhD here in the 60s. And then he went off to Boeing. And then they were building a data structure.
Tác giả thứ hai, McCreight, thực ra là cựu sinh viên CMU. Ông lấy bằng tiến sĩ ở đây vào những năm 60. Rồi ông đến Boeing. Và khi đó họ đang xây dựng một cấu trúc dữ liệu.
They built a data system, and they needed the data structure. And they basically invented the B-tree, the B+tree.
Họ xây một hệ thống dữ liệu và cần cấu trúc dữ liệu đó. Và về cơ bản họ đã phát minh ra B-tree, B+tree.
But the paper that most people cite, refer to as the original definition of the B+tree, came out nine years later. There's a famous paper called "Ubiquitous B-tree".
Nhưng bài báo mà hầu hết mọi người trích dẫn, coi là định nghĩa gốc của B+tree, ra đời chín năm sau. Đó là một bài báo nổi tiếng tên "Ubiquitous B-tree".
So again, it's early days of computing. And obviously, there wasn't internet. So things moved more slowly than they do now.
Lại nói, đó là thời kỳ đầu của máy tính. Và rõ ràng lúc đó chưa có internet. Nên mọi thứ chuyển động chậm hơn bây giờ.
But by 1979, the B-tree, the B+tree, was considered the essential data structure you use in the data system. So much of it was everywhere. And they were calling it ubiquitous. All right.
Nhưng đến năm 1979, B-tree, B+tree, được coi là cấu trúc dữ liệu thiết yếu dùng trong hệ thống dữ liệu. Nó có mặt ở khắp nơi. Và họ gọi nó là phổ biến khắp nơi. Được rồi.
So the challenging thing is going to be, like, there's the original definition of the B tree, the B+tree. But no one follows what this original paper is actually talking about.
Điều khó là, có định nghĩa gốc của B tree, B+tree. Nhưng không ai làm theo đúng những gì bài báo gốc này nói.
They're actually going to use bits and pieces of other data structures that are extensions to B+trees that have come along over the years.
Thực tế họ dùng các phần của những cấu trúc dữ liệu khác, là các phần mở rộng của B+tree xuất hiện qua nhiều năm.
And in particular, the one we're going to talk about today as well is called the B-link tree, which actually was invented here in 1981 at Carnegie Mellon.
Và đặc biệt, cái mà hôm nay chúng ta cũng sẽ nói đến gọi là B-link tree, thực ra được phát minh ngay tại Carnegie Mellon năm 1981.
And the first author for this, Phil Lehman, he's still here at CMU. So he's on the fifth floor or sixth floor at the dean's office. Right? The dude's awesome. He's still here.
Và tác giả đầu của bài này, Phil Lehman, vẫn còn ở CMU. Ông ở tầng năm hoặc tầng sáu, văn phòng trưởng khoa. Đúng không? Ông ấy tuyệt lắm. Vẫn còn ở đây.
And so when you go look at the Postgres code also, as well, they're basically going to be implementing this data structure as well.
Và khi bạn xem mã nguồn Postgres, về cơ bản họ cũng cài đặt cấu trúc dữ liệu này.
If you go look in the source code, it'll say, for the actual B+tree data structure, so they're going to call it a B tree.
Nếu bạn xem mã nguồn, với cấu trúc dữ liệu B+tree thực sự, họ gọi nó là B tree.
But in actuality, it's just a B+tree. Again, people get fuzzy with the names.
Nhưng thực chất nó chỉ là B+tree. Lại nói, người ta hay lẫn lộn tên gọi.
But lo and behold, it says right there, "This directory contains the correct implementation of Lehman and Yao's high-concurrency B-tree management algorithm," which comes from this paper written by the dude over there in Gates.
Nhưng quả nhiên, ngay đó có ghi: "Thư mục này chứa cài đặt chính xác của thuật toán quản lý B-tree đồng thời cao của Lehman và Yao," xuất phát từ bài báo do ông bạn ở bên Gates kia viết.
So again, Postgres is called the B tree, but it's really a B+tree. And actually, they're going to call this an NB tree, which is a non-balanced.
Vậy Postgres gọi là B tree, nhưng thực ra là B+tree. Và thực ra họ sẽ gọi cái này là NB tree, tức là không cân bằng.
So they're going to relax some of the things that we talked about before. Everybody take a guess what the B means in B+tree. Boeing. Yes, he's seen the video.
Vì vậy họ sẽ nới lỏng một số điều mà chúng ta đã nói trước đó. Mọi người thử đoán xem chữ B trong B+tree nghĩa là gì. Boeing. Đúng rồi, bạn ấy đã xem video.
Yes. OK. So people think it means balanced. People mistakenly think it means binary. A binary B tree is basically where N equals 3. We'll cover that in a second, or next slide.
Vâng. OK. Nhiều người nghĩ nó có nghĩa là cân bằng (balanced). Người ta cũng nhầm tưởng nó có nghĩa là nhị phân (binary). Một cây B nhị phân về cơ bản là trường hợp N bằng 3. Chúng ta sẽ nói về điều đó ngay sau đây, hoặc ở slide tiếp theo.
But according to Phil, he said he's like 99 sure, 90 sure that when he talked to the dudes that wrote all these other papers that were at Boeing, he said, "Yeah, they named it after Boeing because they were at Boeing."
Nhưng theo Phil, anh ấy nói là chắc khoảng 99 phần trăm, à không, 90 phần trăm, rằng khi anh ấy trao đổi với những người đã viết tất cả những bài báo khác, những người làm ở Boeing, họ nói: "Đúng vậy, họ đặt tên theo Boeing vì họ làm việc ở Boeing."
Right? So the Boeing tree doesn't sound very catchy.
Đúng không? Cây Boeing nghe không bắt tai lắm.
But people just heard it as the B tree or the B+tree. So I'll try to be very careful, and I'll make a distinction of what a B+tree is versus what a B-tree is.
Nhưng mọi người chỉ nghe thành cây B hoặc B+tree. Vì vậy tôi sẽ cố gắng thật cẩn thận, và sẽ phân biệt rõ B+tree là gì so với B-tree là gì.
But going forward, when a database system says they have a B-tree, 99.9 percent of the time, they really have a B+tree. OK? All right.
Nhưng từ giờ trở đi, khi một hệ quản trị cơ sở dữ liệu nói họ có B-tree, thì 99,9 phần trăm trường hợp, thực ra họ có B+tree. OK? Được rồi.
So a B+tree is going to be a self-balanced, ordered M-way tree that's going to support searches, sequential access, insertions, deletions, all the things that we'd want to do in a data structure, in log N time.
Vậy B+tree là một cây M-nhánh có thứ tự, tự cân bằng, hỗ trợ tìm kiếm, truy cập tuần tự, chèn, xóa, tất cả những gì ta muốn làm với một cấu trúc dữ liệu, trong thời gian log N.
Where M is going to be defining the fan out, the number of pointers that are going to come out of each node, which either could be to another node in the tree or could be to the record or whatever it is that we're trying to find.
Trong đó M xác định fan out, tức số con trỏ đi ra từ mỗi nút, có thể trỏ tới một nút khác trong cây hoặc trỏ tới bản ghi hay bất cứ thứ gì ta đang cần tìm.
So we define M by that. And so for every node, if we say it's an M-way tree, it'll have M outbound pointers. And that's the degree of the node.
Đó là cách ta định nghĩa M. Và với mỗi nút, nếu ta nói đó là cây M-nhánh, nó sẽ có M con trỏ đi ra. Đó là bậc của nút.
But then it's going to have M minus 1 keys that it can reference inside of each node.
Nhưng nó sẽ có M trừ 1 khóa để tham chiếu bên trong mỗi nút.
So it's being claimed it'd be perfect balance, meaning that the distance from the root to any leaf node will always be the same anywhere throughout the tree.
Vậy người ta khẳng định cây có sự cân bằng hoàn hảo, nghĩa là khoảng cách từ nút gốc tới bất kỳ nút lá nào luôn luôn như nhau ở mọi nơi trong cây.
And we're going to have to do a bunch of stuff in our data structure to ensure that this is the case.
Và ta sẽ phải làm khá nhiều việc trong cấu trúc dữ liệu để đảm bảo điều này đúng.
And one of the key requirements is that, I'm going to say that every single node, except for the root, because it's kind of a special case, or it is a special case, every single node needs to be at least half full.
Một trong những yêu cầu then chốt là, mọi nút, trừ nút gốc, vì nó là một trường hợp đặc biệt, hay đúng hơn nó chính là trường hợp đặc biệt, đều phải đầy ít nhất một nửa.
And then when it becomes less than half full, we have to do a bunch of extra work to make it be half full by taking keys from our neighbors or merging things together.
Và khi nó đầy chưa tới một nửa, ta phải làm thêm nhiều việc để đưa nó về đầy một nửa, bằng cách lấy khóa từ các nút lân cận hoặc gộp các nút lại.
And so the reason why this data structure is so important, because, especially in the early days, but even now with modern hardware, it's going to be optimized for reading and writing large blocks of data very efficiently.
Lý do cấu trúc dữ liệu này quan trọng đến vậy là vì, nhất là ở những ngày đầu, nhưng ngay cả bây giờ với phần cứng hiện đại, nó được tối ưu để đọc và ghi các khối dữ liệu lớn một cách rất hiệu quả.
This data structure is going to convert what would otherwise be potentially random I/O into sequential I/O.
Cấu trúc dữ liệu này sẽ chuyển đổi những gì lẽ ra thành I/O ngẫu nhiên tiềm tàng thành I/O tuần tự.
And as we said in the beginning, that's going to make a big deal when it comes to actually constant time factors for actually running our system.
Và như chúng ta đã nói ngay từ đầu, điều đó sẽ tạo ra khác biệt rất lớn khi nói đến các hệ số hằng số thời gian lúc thực sự chạy hệ thống của chúng ta.
If we can maximize the amount of sequential I/O, then we're going to get better performance.
Nếu có thể tối đa hóa lượng I/O tuần tự, thì chúng ta sẽ đạt hiệu năng tốt hơn.
And as I said, some systems that implement the B+tree will relax these properties, but we'll ignore that for now and go strictly by this definition.
Và như tôi đã nói, một số hệ thống cài đặt B+tree sẽ nới lỏng các thuộc tính này, nhưng bây giờ chúng ta sẽ bỏ qua điều đó và đi theo đúng định nghĩa này.
I'll say also, too, the fan out is going to be pretty large. So M is usually a large number. Think of an 8-kilobyte page in Postgres.
Tôi cũng xin nói thêm, fan out sẽ khá lớn. Vì vậy M thường là một số lớn. Hãy nghĩ đến một trang 8 kilobyte trong Postgres.
I could put a lot of key value pairs inside that thing. So the height of a real system with these data structures of B+tree is going to be maybe four or five levels.
Tôi có thể đặt rất nhiều cặp khóa-giá trị vào trong đó. Vì vậy chiều cao của một hệ thống thực tế dùng các cấu trúc dữ liệu B+tree này có lẽ chỉ khoảng bốn hoặc năm tầng.
The fan out is going to be quite large. But in case of PowerPoint, I have to make it fit. So we'll look at simple examples here. So this would be a three-way tree.
Fan out sẽ khá lớn. Nhưng với PowerPoint, tôi phải làm cho nó vừa khít trên slide. Nên ở đây ta sẽ xem các ví dụ đơn giản. Đây sẽ là một cây ba nhánh.
So the fan out is three for every node. So I've got three pointers coming out, and I'll store two keys inside each node. So at the top, we have the root node.
Tức là fan out bằng ba cho mọi nút. Vậy có ba con trỏ đi ra, và tôi sẽ lưu hai khóa trong mỗi nút. Ở trên cùng, chúng ta có nút gốc.
The middle layer is what we call the inner or non-leaf nodes. And the bottom is what we call the leaf nodes.
Tầng giữa là cái ta gọi là các nút trong hay nút không phải lá. Và tầng dưới cùng là cái ta gọi là các nút lá.
The way to think about this is that along the leaf nodes, our keys are going to be sorted from, In this case here, low to high.
Cách nghĩ về điều này là dọc theo các nút lá, các khóa của chúng ta sẽ được sắp xếp từ trong trường hợp này, thấp đến cao.
You can define you want it to be the opposite. You can go high to low.
Bạn có thể định nghĩa ngược lại, từ cao xuống thấp.
But these are going to be sorted according to some correlation ordering that we would define in our database system.
Nhưng chúng sẽ được sắp xếp theo một thứ tự đối chiếu nào đó mà chúng ta định nghĩa trong hệ quản trị cơ sở dữ liệu của mình.
So the contents of the nodes for the root and the non-leaf, the inner nodes, is going to be alternating key-value pairs of some kind of pointer to another node in our data structure, followed by a discriminating key that's going to allow us to determine whether we want to go left or right to find the entry that we're looking for.
Vậy nội dung của các nút gốc và nút không phải lá, tức các nút trong, sẽ là các cặp khóa-giá trị xen kẽ nhau gồm một con trỏ nào đó trỏ đến một nút khác trong cấu trúc dữ liệu, theo sau là một khóa phân biệt cho phép ta xác định nên đi sang trái hay sang phải để tìm mục mà ta đang tìm.
And then in the leaf nodes, these will be key-value pairs where they'll be the actual key that we want to find, and then its corresponding value, which could be a pointer to some data structure, something else, or it could be the record ID.
Còn ở các nút lá, đây sẽ là các cặp khóa-giá trị trong đó có khóa thực sự mà ta muốn tìm, và giá trị tương ứng của nó, có thể là một con trỏ tới một cấu trúc dữ liệu nào đó, hoặc thứ gì khác, hoặc có thể là record ID.
In the case of other systems like MySQL, it could actually be the entire tuple. For our purposes now, it doesn't quite matter.
Với các hệ thống khác như MySQL, nó thực sự có thể là toàn bộ tuple. Còn với mục đích của chúng ta bây giờ thì điều đó không quan trọng lắm.
So the way to understand these keys, they're basically, in the inner nodes, in the root, guideposts that allow us to figure out where we want to go when we do a traversal into the index.
Vậy cách hiểu về các khóa này, về cơ bản, ở các nút trong và nút gốc, chúng là những cột mốc chỉ dẫn giúp ta biết cần đi đâu khi duyệt xuống trong chỉ mục.
And so for this example here, I'm going to say my root node, I have key 20.
Trong ví dụ này, giả sử nút gốc của tôi có khóa 20.
So if I want to go to our left, that'll be all the keys that are less than 20.
Nếu muốn đi sang trái, đó sẽ là tất cả các khóa nhỏ hơn 20.
And then on the other side, the right, they'll be all keys that are equal to or greater than 20.
Còn ở phía bên kia, bên phải, sẽ là tất cả các khóa bằng hoặc lớn hơn 20.
So for any given key, I can just look at that node, look at the key, and decide whether I want to go left or right.
Vậy với bất kỳ khóa nào, tôi chỉ cần nhìn vào nút đó, nhìn vào khóa, và quyết định xem mình muốn đi sang trái hay sang phải.
One thing we're going to also add as well, and this will make it easier for us to do splits and merges in a second, is add sibling pointers.
Chúng ta cũng sẽ thêm một thứ nữa, và điều này sẽ giúp việc tách và gộp nút dễ dàng hơn ngay sau đây, đó là thêm các con trỏ anh em (sibling pointer).
This is what the B-link tree in 1981 added for us.
Đây là thứ mà B-link tree năm 1981 đã bổ sung cho chúng ta.
So now when I want to do a lookup, like a range scan, like find me all the keys that are greater than 15, 15 or greater, I can go start my root node, traverse down to the bottom, and then now scan across on the leaf nodes and follow those sibling pointers to find all the entries that I want.
Vì vậy bây giờ khi tôi muốn thực hiện một lần tra cứu, chẳng hạn quét theo khoảng, như tìm cho tôi tất cả các khóa lớn hơn 15, hoặc bằng 15 trở lên, tôi có thể bắt đầu từ nút gốc, đi xuống tận đáy, rồi quét ngang qua các nút lá và đi theo các con trỏ anh em đó để tìm tất cả các bản ghi mà tôi muốn.
And I don't have to backtrack and go back up to my parent to jump down to the next one.
Và tôi không phải quay lui rồi đi ngược lên nút cha để nhảy xuống nút kế tiếp.
Yes? Yes? What is the question? So what are the values of m?
Có câu hỏi không? Mời bạn. Câu hỏi là gì? Giá trị của m là bao nhiêu à?
So I mean, n is just the number of keys at the bottom when you count those. But m would be, in this case, there's three.
Ý tôi là, n chỉ là số khóa ở dưới đáy khi bạn đếm chúng. Còn m thì trong trường hợp này là ba.
Because for every node, right, going back, say the one at the top, right, you have a node pointer that tells you how to go down to one side, a discriminating key that tells you whether you want to go left or right based on the value of it, followed by the next pointer.
Bởi vì với mỗi nút, hãy nhìn lại nút ở trên cùng chẳng hạn, bạn có một con trỏ nút cho bạn biết cách đi xuống một phía, một khóa phân biệt cho bạn biết nên đi sang trái hay sang phải dựa trên giá trị của nó, tiếp theo là con trỏ kế tiếp.
Yes? The question is, for range scans, you don't know why you would need sibling pointers and aligning those. You'll need them for splits and merges.
Mời bạn? Câu hỏi là, với các lần quét theo khoảng, bạn không hiểu vì sao lại cần các con trỏ anh em và việc căn chỉnh chúng. Bạn sẽ cần chúng cho việc tách và gộp nút.
But once you reach the bottom, if you're just reading, you never have to go back up. Yes? Question, in that root node, there's three node pointers? Yes. Why what?
Nhưng một khi đã xuống tới đáy, nếu chỉ đọc thì bạn không bao giờ phải đi ngược lên nữa. Mời bạn? Câu hỏi: ở nút gốc đó có ba con trỏ nút phải không? Đúng vậy. Tại sao à?
So your question is, why do I need three node pointers and only one pointer to two? How am I allocating this? Think in a real system. What's the backing memory of this?
Vậy câu hỏi của bạn là, tại sao tôi cần ba con trỏ nút mà chỉ có một con trỏ tới hai? Tôi cấp phát nó như thế nào? Hãy nghĩ đến một hệ thống thực tế. Bộ nhớ nền của nó là gì?
No, no, no. What's the backing memory of the data in a node? Like, I have stored the node, the contents of the node somewhere.
Không, không, không. Bộ nhớ nền của dữ liệu trong một nút là gì? Ý là, tôi đã lưu nút đó, nội dung của nút đó ở đâu đó.
What am I storing it in? What is it? A page. Pages are all fixed size. So in my PowerPoint example, yeah, I have two pointers coming out of it.
Tôi lưu nó vào cái gì? Đó là gì? Một trang. Các trang đều có kích thước cố định. Vì vậy trong ví dụ PowerPoint của tôi, đúng, có hai con trỏ đi ra từ nó.
But in a real system, I'm going to allocate a four kilobyte, eight kilobyte page. I have to, you know, I'm going to allocate the space for it. So it's always going to be there.
Nhưng trong một hệ thống thực tế, tôi sẽ cấp phát một trang bốn kilobyte, tám kilobyte. Tôi phải, bạn biết đấy, cấp phát không gian cho nó. Nên không gian đó luôn luôn có ở đó.
Because his question is, why did I just, what I just said, explain about those three pointers?
Vì câu hỏi của bạn ấy là, tại sao tôi lại, điều tôi vừa nói, giải thích về ba con trỏ đó?
Because it's not like an in-memory data structure where I'm just calling malloc and I only get the data that I actually need.
Bởi vì nó không giống một cấu trúc dữ liệu trong bộ nhớ nơi tôi chỉ gọi malloc và chỉ nhận đúng phần dữ liệu mà tôi thực sự cần.
I'm going to go to the buffer pool manager and say, I need a page. And you're going to get back an eight kilobyte chunk of memory.
Tôi sẽ đến bộ quản lý buffer pool và nói, tôi cần một trang. Và bạn sẽ nhận lại một khối bộ nhớ tám kilobyte.
So I'm going to allocate the space for it. In my diagram, yes, the space is not being used.
Vì vậy tôi sẽ cấp phát không gian cho nó. Trong sơ đồ của tôi, đúng, không gian đó không được dùng.
In a real system, you would have that space allocated anyway, even if it's still not being used.
Trong một hệ thống thực tế, không gian đó vẫn được cấp phát sẵn, dù nó vẫn chưa được sử dụng.
All right. So on the leaf nodes, I'm just showing that you'd have pointers for siblings on the backside of the array, right?
Được rồi. Vậy ở các nút lá, tôi chỉ minh họa rằng bạn sẽ có các con trỏ tới nút anh em ở phía cuối của mảng, đúng không?
So at its core, what is the B+tree? What are we doing? He says binary search tree. Over what?
Vậy về bản chất, B+tree là gì? Chúng ta đang làm gì? Em ấy nói là cây tìm kiếm nhị phân. Trên cái gì?
Yeah, but what's the data structure at the bottom? What is this? Not a hash table. Linked list, right?
Ừ, nhưng cấu trúc dữ liệu ở dưới cùng là gì? Đây là gì? Không phải bảng băm. Danh sách liên kết, đúng không?
So all this data structure is, and all these tree data structures is, just allow us to jump into our linked list more efficiently.
Vậy toàn bộ cấu trúc dữ liệu này, và tất cả các cấu trúc dữ liệu dạng cây này, chỉ giúp chúng ta nhảy vào danh sách liên kết hiệu quả hơn.
Because otherwise, without this stuff at the top, what do I have to do? I've got to scan along linearly on the leaf nodes to find the thing that I want, right?
Vì nếu không, không có phần ở trên cùng này, tôi phải làm gì? Tôi phải quét tuyến tính dọc theo các nút lá để tìm thứ mình muốn, đúng không?
So, oops, sorry, go back. So it's not that exotic.
Ôi, xin lỗi, quay lại. Vậy nó không có gì quá lạ.
If you just think about the top part, it's just the scaffolding we're going to build on top of this linked list so that we can jump to the bottom to find the thing that we want, or the keys that we want, right?
Nếu bạn chỉ nghĩ về phần trên cùng, thì nó chỉ là giàn giáo mà chúng ta dựng lên trên danh sách liên kết này để có thể nhảy xuống dưới cùng tìm thứ chúng ta muốn, hay các khóa mà chúng ta muốn, đúng không?
Skip list, basically the same thing. Tries a little bit different, but in the end of the day, that's what this data structure is doing for us.
Skip list về cơ bản cũng giống vậy. Trie thì hơi khác một chút, nhưng cuối cùng thì đó là việc mà cấu trúc dữ liệu này làm cho chúng ta.
It allows us to jump to locations in our linked list without having to scan from beginning to end every single time. Again, because always think in extremes, right?
Nó cho phép chúng ta nhảy tới các vị trí trong danh sách liên kết mà không phải quét từ đầu đến cuối mỗi lần. Một lần nữa, hãy luôn nghĩ đến các trường hợp cực đoan, đúng không?
If I have a billion keys or trillion keys, I don't want to do that linear scan every single time. My B+tree will allow me to jump into it.
Nếu tôi có một tỉ khóa hoặc một nghìn tỉ khóa, tôi không muốn quét tuyến tính mỗi lần như vậy. B+tree sẽ cho phép tôi nhảy thẳng vào.
And as I said before, the fan out will be quite large in a real system. So I'm only going to have to jump down at mostly five levels.
Và như tôi đã nói trước đó, fan out trong một hệ thống thực tế sẽ khá lớn. Nên tôi chỉ phải nhảy xuống nhiều nhất khoảng năm tầng.
And I can represent a lot of keys in my leaf nodes.
Và tôi có thể biểu diễn rất nhiều khóa trong các nút lá.
All right, so the leaf nodes themselves, I'm sorry, the nodes themselves are just, thinking of them as arrays of key-value pairs, right?
Được rồi, bản thân các nút lá, xin lỗi, bản thân các nút thì chỉ là hãy nghĩ chúng là các mảng gồm các cặp khóa-giá trị, đúng không?
The values that we'll be storing will be different based on whether we are an inner node versus a leaf node, right?
Các giá trị mà chúng ta lưu sẽ khác nhau tùy theo đó là nút trong hay nút lá, đúng không?
If it's an inner node, the values are going to be pointers to other nodes. And these are just page numbers, right?
Nếu là nút trong, các giá trị sẽ là con trỏ tới các nút khác. Và đó chỉ là các số trang, đúng không?
That I can do a lookup in the buffer pool to go get the data that I want. And then the leaf nodes will vary based on what I actually want to store.
để tôi có thể tra cứu trong buffer pool và lấy dữ liệu mình cần. Còn các nút lá sẽ thay đổi tùy theo thứ tôi thực sự muốn lưu.
Do I want to store record IDs, the pointers to tuples? Do I want to store the entire tuple itself? I can do that in MySQL and SQLite.
Tôi muốn lưu record ID, tức các con trỏ tới tuple? Tôi muốn lưu toàn bộ tuple? Tôi có thể làm vậy trong MySQL và SQLite.
In some systems like MySQL as well, leaf nodes will actually store a primary key as the values.
Trong một số hệ thống như MySQL, các nút lá thực ra lưu khóa chính làm giá trị.
So then I can take the primary key and do a lookup in the primary key index to actually get the record ID or get the tuple, right?
Rồi tôi lấy khóa chính đó và tra cứu trong chỉ mục khóa chính để lấy record ID hoặc lấy tuple, đúng không?
And then for nulls, you have to treat them specially. And typically, you either put them at the beginning of the list or at the end of the leaf nodes, right?
Còn với null, bạn phải xử lý đặc biệt. Thông thường, bạn đặt chúng ở đầu danh sách hoặc ở cuối các nút lá, đúng không?
I think by default in Postgres, they put them at the end. So again, I'm showing this sort of diagram like this.
Tôi nghĩ mặc định trong Postgres, họ đặt chúng ở cuối. Vậy một lần nữa, tôi minh họa bằng sơ đồ kiểu như thế này.
You know, Before, because that's a bit in PowerPoint, I'm showing these sort of key-value pairs over and over again. In actuality, a real system wouldn't actually store it like this.
Trước đó, vì làm bằng PowerPoint hơi mất công, nên tôi cứ vẽ các cặp khóa-giá trị này lặp đi lặp lại. Thực tế, một hệ thống thật sẽ không lưu như thế này.
You would have some extra metadata. They would store it at the top. They'd say, like, what level am I at? How many slots can I store? What's my previous pointer and next pointer?
Sẽ có thêm một số siêu dữ liệu, và chúng được lưu ở phần đầu. Chẳng hạn như: tôi đang ở tầng nào? Tôi chứa được bao nhiêu slot? Con trỏ trước và con trỏ sau của tôi là gì?
Sometimes there's additional metadata. Say, like, how many keys do I have inside here? What's the high key? What's the max value I can store on my page?
Đôi khi còn có thêm siêu dữ liệu khác. Ví dụ như: bên trong này tôi có bao nhiêu khóa? High key là gì? Giá trị tối đa tôi có thể lưu trên trang của mình là gì?
Some extra things that make me find data more quickly. And then you could store it in the example I was showing before, where you just have the key followed by its record ID.
Một vài thứ bổ sung giúp tôi tìm dữ liệu nhanh hơn. Và sau đó bạn có thể lưu như ví dụ tôi cho xem lúc nãy, tức là khóa theo sau là record ID của nó.
Or sorry, the pointer right afterwards as the value. In a lot of systems instead, what you do is you store all the keys sorted as a separate array.
À xin lỗi, là con trỏ ngay sau đó làm giá trị. Thay vào đó, trong rất nhiều hệ thống, người ta lưu tất cả các khóa đã sắp xếp thành một mảng riêng.
Then you store all the values just in a fixed length array or some kind of array that you can then just jump to offsets like we did in the column store based on whatever key that I'm looking for.
Rồi lưu tất cả các giá trị trong một mảng có độ dài cố định hoặc một dạng mảng nào đó mà bạn có thể nhảy thẳng tới các offset như chúng ta đã làm trong column store, dựa trên khóa mà tôi đang tìm.
So now if I want to find the key that I want, I can just do binary search on the key array and not have to jump over data that I actually don't need.
Vậy bây giờ nếu muốn tìm khóa cần thiết, tôi chỉ cần tìm kiếm nhị phân trên mảng khóa mà không phải nhảy qua những dữ liệu thực sự không cần.
Yes? So actually, is one node one page? Not always, but you could, for simplicity, think of it like that, yes.
Vâng? Vậy một nút có phải là một trang không? Không phải lúc nào cũng vậy, nhưng cho đơn giản thì bạn có thể nghĩ như thế, vâng.
The database page is 8 kilobytes. The node is going to be 8 kilobytes. That's what I'm saying.
Trang cơ sở dữ liệu là 8 kilobyte. Nút cũng sẽ là 8 kilobyte. Ý tôi là vậy.
The fan-outs are going to be quite big because you can put a lot of key-value pairs in 8 kilobytes.
Fan-out sẽ khá lớn vì bạn có thể nhét rất nhiều cặp khóa-giá trị vào 8 kilobyte.
What's that? This question is, when will it not be one page? Give me a few more slides. Sometimes my keys can be quite big and I got to overflow.
Sao cơ? Câu hỏi là khi nào thì nó không phải một trang? Cho tôi thêm vài slide nữa. Đôi khi khóa có thể khá lớn và tôi phải dùng overflow.
This question is, how do you maintain a sort of keys? I don't know, pick your favorite sorting algorithm. Quicksort. All right, it's in memory.
Câu hỏi là làm sao duy trì thứ tự sắp xếp của các khóa? Tôi không biết, cứ chọn thuật toán sắp xếp bạn thích. Quicksort. Dù sao nó cũng nằm trong bộ nhớ.
This question is, does that mean whenever a key is inserted, am I going to resort it? In most systems, yes. You don't have to, but in general, yes.
Câu hỏi là, điều đó có nghĩa là mỗi khi chèn một khóa, tôi sẽ sắp xếp lại nó không? Ở hầu hết các hệ thống thì có. Bạn không bắt buộc, nhưng nói chung là có.
But again, it's in memory. I'm already reading it, so I hold the latch on it, the mutex on it, so I can do whatever I want once I have that.
Nhưng một lần nữa, nó nằm trong bộ nhớ. Tôi đã đang đọc nó rồi, nên tôi giữ latch trên nó, giữ mutex trên nó, nên khi có rồi thì tôi muốn làm gì cũng được.
This question is, that's a lot of movement. This is going to fit in cache lines. It's not going to be that bad. I can sort 100 keys pretty quickly. Yes, sorry.
Câu hỏi là, như vậy phải dịch chuyển dữ liệu nhiều quá. Nó vừa trong cache line. Sẽ không tệ đến thế đâu. Tôi sắp xếp 100 khóa khá nhanh. Vâng, xin lỗi.
Question is, keys be very length? Yes, we'll solve that. Give me a few more slides. Yes, that makes it harder. All right, so I've already said this.
Câu hỏi là khóa có độ dài thay đổi thì sao? Vâng, chúng ta sẽ giải quyết. Cho tôi thêm vài slide nữa. Vâng, điều đó làm mọi thứ khó hơn. Được rồi, tôi đã nói điều này rồi.
What are going to be the values in our leaf nodes? In most systems, it'll be the record ID, and it's like a page number and an offset.
Các giá trị trong nút lá của chúng ta sẽ là gì? Ở hầu hết các hệ thống, đó sẽ là record ID, gồm số trang và một offset.
That's going to always be fixed length, and that'll allow us to jump to find what we want. In other systems, it can actually be the tuples themselves.
Nó luôn có độ dài cố định, và điều đó cho phép chúng ta nhảy thẳng tới thứ mình cần. Ở các hệ thống khác, giá trị có thể chính là các tuple.
We saw this in index-organized storage, in MySQL and Postgres, and Oracle and other systems. MySQL and SQLite give you this by default. Like, when you create a table, you get it.
Chúng ta đã thấy điều này trong lưu trữ theo chỉ mục (index-organized storage), ở MySQL, Postgres, Oracle và các hệ thống khác. MySQL và SQLite cung cấp sẵn điều này theo mặc định. Tức là khi bạn tạo một bảng, bạn có nó luôn.
In SQL Server and Oracle, you have to explicitly say that I want it.
Còn trong SQL Server và Oracle, bạn phải nói rõ là mình muốn dùng nó.
All right, so now that you understand the basics of B-trees, and B+trees, you know the basics of B+trees, let me make the distinction of what a difference between a B-tree is and a B+tree.
Được rồi, giờ bạn đã hiểu những kiến thức cơ bản về B-tree, và B+tree, bạn đã biết những điều cơ bản về B+tree, hãy để tôi phân biệt sự khác nhau giữa B-tree và B+tree.
Actually, this should be 1979, not 1971. But in the original B-tree, all the values could exist anywhere in the inner nodes.
Thực ra chỗ này phải là 1979, chứ không phải 1971. Nhưng trong B-tree gốc, mọi giá trị đều có thể nằm ở bất kỳ đâu trong các nút trong.
Meaning, if I'm doing traversal to find the key that I want, I may hit the first root node, and then I'll find the key that I want, and then I get the value right then and there.
Nghĩa là, nếu tôi duyệt cây để tìm khóa mình muốn, tôi có thể gặp ngay nút gốc, rồi tìm thấy khóa mình cần, và lấy được giá trị ngay tại đó.
In the B+tree, the values, again, like the record IDs or whatever it is that's actually representing the data of the tuple that I'm trying to find in my data structure, only exist in the leaf nodes.
Trong B+tree, các giá trị, như đã nói, chẳng hạn các record ID hay bất cứ thứ gì đại diện cho dữ liệu của tuple mà tôi muốn tìm trong cấu trúc dữ liệu, chỉ tồn tại ở các nút lá.
So in order to find whether a key exists, I always got to get down to the leaf node. And it's either there or not there.
Vì vậy, để biết một khóa có tồn tại hay không, tôi luôn phải đi xuống nút lá. Và nó hoặc có ở đó, hoặc không.
So B-trees are going to be more efficient in terms of space, but I now may have to do this depth-first search and jump up and down and come back up to the root over and over again to try to find the thing that I want, and that's going to be a random IO that's going to be bad.
Như vậy B-tree sẽ hiệu quả hơn về không gian, nhưng giờ tôi có thể phải thực hiện tìm kiếm theo chiều sâu, nhảy lên nhảy xuống và quay lại nút gốc hết lần này đến lần khác để tìm thứ mình muốn, và đó sẽ là IO ngẫu nhiên, rất tệ.
In the case of a B+tree, once I get to the leaf nodes, ignoring splits and merges, once I get to the leaf nodes, I'm trying to find data, I can do sequential scans to find the things that I'm looking for.
Với B+tree, khi đã đến các nút lá, bỏ qua việc tách và gộp nút, một khi đã đến các nút lá, nơi tôi cần tìm dữ liệu, tôi có thể quét tuần tự để tìm những thứ mình cần.
And that's a key distinction. So when we delete a key now, in a B+tree, it may still exist in the inner nodes, but it'll get removed from the leaf nodes, and that's okay.
Và đó là một điểm khác biệt quan trọng. Vậy khi xóa một khóa trong B+tree, nó vẫn có thể còn trong các nút trong, nhưng sẽ bị xóa khỏi các nút lá, và như thế là ổn.
In a B-tree, if we delete a key, it has to be completely removed from the tree.
Trong B-tree, nếu xóa một khóa, nó phải bị loại bỏ hoàn toàn khỏi cây.
Red-black trees work the same way, all the other ones work the same way, but they're going to have their own issues.
Cây đỏ-đen cũng hoạt động như vậy, các loại khác cũng vậy, nhưng mỗi loại sẽ có những vấn đề riêng.
So B+trees are going to be slightly larger than B-trees, but we're going to get better performance because we do more sequential scans.
Vì vậy B+tree sẽ lớn hơn B-tree một chút, nhưng ta được hiệu năng tốt hơn vì thực hiện nhiều lần quét tuần tự hơn.
And actually, we'll see in two weeks or next week, when we start having multiple threads jump into our data structure, B+trees are going to be way better than a B-tree.
Thực ra, hai tuần nữa hoặc tuần sau ta sẽ thấy, khi nhiều luồng bắt đầu truy cập vào cấu trúc dữ liệu của ta, B+tree sẽ tốt hơn B-tree rất nhiều.
All right, so let's first talk about how we're going to insert.
Được rồi, trước tiên hãy nói về cách ta chèn dữ liệu.
The protocol, As I said, for doing a lookup is, again, you just look at the keys, figure out where you want to go, left and right, and then jump down and keep going until you find the leaf node, and you either find the data you want or you don't.
Như tôi đã nói, giao thức để tra cứu là, một lần nữa, bạn chỉ cần nhìn các khóa, xác định cần đi trái hay phải, rồi đi xuống và tiếp tục cho đến khi tới nút lá, và bạn hoặc tìm thấy dữ liệu mình muốn, hoặc không.
Now, to do an insert, we're going to do that same lookup procedure where we're going to traverse the data structure, find the leaf node that should have the key that we want to insert, and then go ahead and try to insert it.
Còn để chèn, ta sẽ dùng đúng quy trình tra cứu đó, tức là duyệt cấu trúc dữ liệu, tìm nút lá lẽ ra phải chứa khóa mà ta muốn chèn, rồi tiến hành thử chèn nó vào.
If there's enough space in that leaf node, great, we're done. If there's not enough space, meaning that all the array is full, then we have to do a split.
Nếu nút lá đó còn đủ chỗ thì tốt, chúng ta xong việc. Nếu không đủ chỗ, nghĩa là toàn bộ mảng đã đầy, thì chúng ta phải thực hiện một phép tách.
And that means, in this case, we will now redistribute our keys that are in the node that overflowed to other nodes, which then may require us to then do a bunch of splits going up the data structure.
Điều đó có nghĩa là, trong trường hợp này, ta sẽ phân phối lại các khóa đang nằm trong nút bị tràn sang các nút khác, và điều này có thể lại buộc ta phải thực hiện hàng loạt phép tách đi ngược lên trên cấu trúc dữ liệu.
So upon insert, we may have to reorganize the entire tree in the worst case scenario.
Vì vậy khi chèn, trong trường hợp xấu nhất ta có thể phải tổ chức lại toàn bộ cây.
But in most of the cases, most cases, we'll have enough space in the leaf node we're trying to insert into. And then worst case scenario, we'll have to then maybe split our parent.
Nhưng trong hầu hết các trường hợp, nút lá mà ta cố chèn vào sẽ còn đủ chỗ. Còn trường hợp xấu nhất thì có thể ta phải tách cả nút cha.
And then the split process, we're just going to redistribute the keys evenly by just taking whatever the middle key is and using that as the halfway point, split things in half, and then push the middle key up as a discriminator in the tree above us and recursively do this until everything's balanced.
Còn quá trình tách thì ta chỉ phân phối lại các khóa đều nhau bằng cách lấy khóa ở giữa, bất kể đó là khóa nào, và dùng nó làm điểm chia đôi, tách mọi thứ làm hai nửa, rồi đẩy khóa ở giữa lên làm khóa phân biệt ở tầng cây phía trên và làm đệ quy như vậy cho đến khi mọi thứ cân bằng.
So going back to a really simple example here, now we have, again, a four-way tree with three keys. So there's four branches that could come out of every single node.
Quay lại một ví dụ thật đơn giản, bây giờ chúng ta có một cây bốn nhánh với ba khóa. Tức là mỗi nút có thể có bốn nhánh đi ra.
And then we have our ranges here. And now I'm showing greater than or equal to 4 and less than 12. Here's the more compact form of that. So say I want to insert 6.
Và chúng ta có các khoảng giá trị ở đây. Giờ tôi đang hiển thị khoảng lớn hơn hoặc bằng 4 và nhỏ hơn 12. Đây là dạng gọn hơn của nó. Giả sử tôi muốn chèn 6.
So again, I started at my root node. I look at the keys that I had there. 6 is greater than 4 but less than 12.
Một lần nữa, tôi bắt đầu từ nút gốc. Tôi xem các khóa có ở đó. 6 lớn hơn 4 nhưng nhỏ hơn 12.
So I know I want to go down to this leaf node here. But this node is full, so I have to split it.
Vậy tôi biết mình cần đi xuống nút lá này. Nhưng nút này đã đầy, nên tôi phải tách nó.
So what I'm going to do is I'm going to end up creating a new node, a new leaf node, that's currently empty.
Vậy tôi sẽ tạo ra một nút mới, một nút lá mới, hiện đang trống.
Then I'm going to take half the keys in my first node, or take all the keys, figure out what the middle point is. Half the keys are going to go in the original node.
Sau đó tôi lấy một nửa số khóa trong nút đầu tiên, hoặc lấy tất cả các khóa, rồi xác định điểm giữa. Một nửa số khóa sẽ nằm trong nút ban đầu.
The other half of the keys are going to go into the other node. So you end up like this.
Nửa còn lại sẽ chuyển sang nút kia. Và kết quả sẽ như thế này.
The 6 went into the original node, but 9 and 10 got moved over to the other one. Am I done? No.
6 vào nút ban đầu, còn 9 và 10 được chuyển sang nút kia. Xong chưa? Chưa.
Now I've got to go back up to my parent and add a key there to make sure that if anybody's looking for 9 and 10, they know how to go find it.
Giờ tôi phải quay lên nút cha và thêm một khóa ở đó để bảo đảm rằng nếu ai tìm 9 và 10, họ biết cách đi tìm.
So in this case here, I can just choose the smallest key on this node here. 9 is basically what I split on before. And put 9 at the top there.
Trong trường hợp này, tôi có thể chọn khóa nhỏ nhất của nút này. 9 về cơ bản là giá trị tôi đã dùng để tách ban nãy. Và đặt 9 lên trên cùng.
At this point, I'm done. And I just update my, well, you wouldn't store this, the keys essentially are giving you that range.
Đến đây là xong. Và tôi chỉ cập nhật, à, bạn sẽ không lưu cái này, về bản chất các khóa đã cho bạn khoảng đó.
Because when you traverse the tree, you know how to interpret the contents. Yes.
Vì khi duyệt cây, bạn biết cách diễn giải nội dung. Vâng.
The question is, you don't remove the 9. Why would you do that?
Câu hỏi là, bạn không xóa 9. Tại sao lại làm vậy?
The statement is, why don't I remove the 9? The key exists. It has to exist in the leaf nodes. So going back here, 9 was in here before.
Ý bạn là, tại sao tôi không xóa 9? Khóa đó vẫn tồn tại. Nó phải tồn tại trong các nút lá. Quay lại đây, 9 đã ở trong này từ trước.
5, 9, 10. So 9's in there.
5, 9, 10. Vậy 9 nằm trong đó.
Statement is, and he's correct, any key that exists in my data structure has to exist in the leaf nodes. Yes. The question is, why isn't 4 there?
Phát biểu là, và bạn ấy nói đúng, bất kỳ khóa nào tồn tại trong cấu trúc dữ liệu của tôi đều phải tồn tại ở các nút lá. Vâng. Câu hỏi là, tại sao 4 không có ở đó?
Because 4 was inserted and then got deleted. That's OK. In a B-tree, you can't do that. In a B+tree, you can. All right.
Vì 4 đã được chèn vào rồi sau đó bị xóa. Điều đó không sao. Trong B-tree thì không làm vậy được. Trong B+tree thì được. Được rồi.
Let's do another insert. Let's now insert 8. 8, again, root node. We followed the pointer. 8 is less than 9 but greater than 4.
Hãy làm một lần chèn nữa. Giờ ta chèn 8. 8, lại bắt đầu từ nút gốc. Ta đi theo con trỏ. 8 nhỏ hơn 9 nhưng lớn hơn 4.
That takes us down here. We go ahead and hit Insert. And that's fine. All right. And let's look at a bigger table. So I want to insert 17. 17 should go here.
Điều đó đưa ta xuống đây. Ta tiến hành chèn. Và thế là ổn. Được rồi. Và hãy xem một bảng lớn hơn. Tôi muốn chèn 17. 17 sẽ nằm ở đây.
That's fine. Now I want to insert 16. 16 should go between 15 and 16. But there's not enough space in here where I can store it. So I want to split the node again.
Ổn rồi. Giờ tôi muốn chèn 16. 16 phải nằm giữa 15 và 16. Nhưng ở đây không còn đủ chỗ để lưu nó. Vì vậy tôi phải tách nút một lần nữa.
So essentially, I'm going to create a new node and then shuffle all the keys from the new node that got overflowed.
Về cơ bản, tôi sẽ tạo một nút mới rồi phân phối lại tất cả các khóa từ nút bị tràn sang nút mới.
Put half of one and half of the other. All right. So say I split on 16. So everything 16 or greater goes to the new node. Everything 16 less stays in the original node.
Đặt một nửa vào nút này và một nửa vào nút kia. Được rồi. Giả sử tôi tách tại 16. Vậy mọi khóa từ 16 trở lên sẽ chuyển sang nút mới. Mọi khóa nhỏ hơn 16 vẫn ở lại nút ban đầu.
But now I have to update my root parent, in this case the root node, to now add 16 there. So anybody that is coming down can find us.
Nhưng giờ tôi phải cập nhật nút cha, trong trường hợp này là nút gốc, để thêm 16 vào đó. Để bất kỳ ai đi xuống đều có thể tìm thấy chúng ta.
But of course, now the problem is our root node is full as well. So again, you recursively go up and keep trying to insert new keys back up.
Nhưng tất nhiên, vấn đề bây giờ là nút gốc của ta cũng đã đầy. Vì vậy, một lần nữa, bạn đệ quy đi lên và tiếp tục cố chèn các khóa mới lên trên.
And if you have to split your parent node, you've got to run basically the whole protocol again. And as you go up from one level to the next, you don't reorganize anything below you.
Và nếu bạn phải tách nút cha, về cơ bản bạn phải chạy lại toàn bộ giao thức. Và khi bạn đi lên từ tầng này sang tầng khác, bạn không tổ chức lại bất cứ thứ gì bên dưới.
Because you've already handled that. Make sure it's balanced. But as you go up, you make sure everything else is balanced until you reach the root.
Vì bạn đã xử lý xong phần đó. Hãy đảm bảo nó cân bằng. Nhưng khi đi lên, bạn đảm bảo mọi thứ khác đều cân bằng cho đến khi tới nút gốc.
And you're done. So in this case here, our root node is full. So we're going to split it again and then grow the tree and make it taller.
Và xong. Trong trường hợp này, nút gốc của ta đã đầy. Vì vậy ta sẽ tách nó một lần nữa rồi làm cây phát triển, cao thêm.
So 13 is going to get moved up, because that'll be the middle key for the new root of the entire tree. And then 16 is going to get put where, between 9 and 19.
Vậy 13 sẽ được đẩy lên, vì nó sẽ là khóa ở giữa cho nút gốc mới của toàn bộ cây. Và 16 sẽ được đặt ở đâu, giữa 9 và 19.
But now what we need to do is split this, because any time I've inserted something up, I have to split whatever node that's got to overflow.
Nhưng giờ ta cần tách nút này, vì bất cứ khi nào tôi chèn thứ gì lên trên, tôi phải tách bất kỳ nút nào bị tràn.
And so I'm going to create two new nodes here. Or you just copy, you create a new one and then reallocate things in the original one.
Và vì vậy tôi sẽ tạo hai nút mới ở đây. Hoặc bạn chỉ cần sao chép, bạn tạo một nút mới rồi phân bổ lại các thứ trong nút ban đầu.
That's fine. And then now I update my root node.
Ổn rồi. Và giờ tôi cập nhật nút gốc.
The new root node, 13, can now point to values less than 13, which is 5 and 9, and values greater than 13, which is 16 and 19 on this side.
Nút gốc mới, 13, giờ có thể trỏ tới các giá trị nhỏ hơn 13, là 5 và 9, và các giá trị lớn hơn 13, là 16 và 19 ở phía này.
Or greater than or equal to 13, which is 16 and 19 here. So the new organization of the discriminator keys looks like this.
Hoặc lớn hơn hay bằng 13, là 16 và 19 ở đây. Vậy cách tổ chức mới của các khóa phân biệt trông như thế này.
Yes? Is there a reason why, when you finish root, like, you just move stuff to the left? Like, do people at the very beginning want to type something?
Vâng? Có lý do nào mà khi bạn xong phần gốc, kiểu như, bạn chỉ dồn mọi thứ sang bên trái không? Kiểu như, những người ngay từ đầu có muốn gõ gì đó không?
Like, in the node on the left, like, there's always a sign that you want to type something. Yes. So he's talking about optimization, and we'll see this when we do deletes.
Ví dụ, ở nút bên trái, lúc nào cũng có dấu hiệu cho thấy bạn muốn gõ gì đó. Vâng. Bạn ấy đang nói về một tối ưu hóa, và chúng ta sẽ thấy nó khi làm phần xóa.
If I'm back here, I want to insert 16. I can recognize, oh, well, the guy where node 9, 11 are, or even 20, 21, 23, they can absorb one more key.
Nếu tôi quay lại đây và muốn chèn 16. Tôi có thể nhận ra rằng nút chứa 9, 11, hoặc thậm chí 20, 21, 23, vẫn còn chỗ cho thêm một khóa.
So I could follow my sibling pointers and just shuffle things around, move 13 and 14 over to the other one, and then put 16 in this one.
Vậy tôi có thể đi theo các con trỏ anh em và dồn các thứ lại, chuyển 13 và 14 sang nút kia, rồi đặt 16 vào nút này.
I wouldn't have to split it. You could do that. It's basically what you do when somebody deletes another thing. Just more machinery, right? It's an optimization. I'm just trying to do the basics first.
Tôi sẽ không phải tách nút. Bạn có thể làm vậy. Về cơ bản đó là điều bạn làm khi có ai đó xóa một khóa khác. Chỉ là thêm cơ chế phức tạp thôi, đúng không? Đó là một tối ưu hóa. Tôi chỉ đang cố trình bày phần cơ bản trước.
But yes, you could do that, and it still would be correct.
Nhưng đúng, bạn có thể làm vậy, và nó vẫn đúng.
And then the question all these people ask is, like, going back here, At this point here, why not just say we're done here?
Và câu hỏi mà mọi người hay hỏi là, quay lại chỗ này, Đến điểm này, tại sao không nói luôn là xong?
Why do I have to create a new node at the second level? Because then it's actually no longer balanced, right?
Tại sao tôi phải tạo một nút mới ở tầng thứ hai? Vì khi đó cây thực sự không còn cân bằng nữa, đúng không?
It doesn't follow the protocol where you have exactly, you know, it's still, the traversal is still correct.
Nó không tuân theo quy tắc là phải có đúng, bạn biết đấy, việc duyệt cây vẫn đúng.
But from the top point, from the root's node perspective, all of the keys are on one side of it, not the other side. So it's not considered balanced in that way.
Nhưng từ phía trên, theo góc nhìn của nút gốc, tất cả các khóa nằm về một phía, không phải phía bên kia. Nên theo cách đó nó không được coi là cân bằng.
So that's why we always have to split whatever the one, whatever the level that's overflowed, to create new nodes and then reconstruct the tree like that.
Đó là lý do chúng ta luôn phải tách tầng nào bị tràn, để tạo các nút mới rồi dựng lại cây như vậy.
And again, since these are all backed by pages, if all the keys on this side of the tree were out on disk and not in our buffer pool manager, or not in our buffer pool, we don't have to bring them in to do anything, because we're just updating pointers to, or the page IDs for, the other parts of the tree.
Và một lần nữa, vì tất cả những thứ này đều được lưu trong các trang, nếu mọi khóa ở phía này của cây đang nằm trên đĩa chứ không nằm trong buffer pool manager, hay không nằm trong buffer pool, ta không cần nạp chúng vào để làm gì cả, vì ta chỉ đang cập nhật các con trỏ tới, hay các page ID của, những phần khác của cây.
And so the nice thing about this data structure is that we just, you know, there's parts of the tree that we don't need while we're reorganizing things.
Và điểm hay của cấu trúc dữ liệu này là có những phần của cây mà ta không cần đến khi đang tổ chức lại.
They just can sit out on disk and not bother anybody and not take up space.
Chúng cứ nằm trên đĩa, không làm phiền ai và không chiếm chỗ.
All right, so look at the delete. Deletes are basically opposite of this.
Được rồi, giờ xem phần xóa. Xóa về cơ bản là ngược lại với điều này.
Again, the idea is that when we delete a key, if after the deletion of a key from a leaf node it's still at least half full, congrats, we're done, we don't do anything, all right?
Một lần nữa, ý tưởng là khi ta xóa một khóa, nếu sau khi xóa khóa khỏi nút lá mà nó vẫn đầy ít nhất một nửa, chúc mừng, xong rồi, ta không phải làm gì thêm, được chứ?
If, though, deleting that key now makes us less than half full, we can first try to redistribute and rebalance the data structure in the way he was suggesting, by trying to steal keys from our siblings so that we don't have to reorganize everything all over again.
Nhưng nếu việc xóa khóa đó khiến nút đầy chưa đến một nửa, trước hết ta có thể thử phân phối lại và cân bằng lại cấu trúc dữ liệu theo cách bạn ấy đề xuất, bằng cách thử lấy khóa từ các nút anh em để không phải tổ chức lại mọi thứ từ đầu.
But if stealing a key from an adjacent node, and usually you only look at the one guy over, you don't try to look at all your siblings, If you can steal it without rebalancing, you're done.
Nhưng nếu lấy một khóa từ nút kề bên, và thường thì bạn chỉ xem nút ngay bên cạnh, bạn không cố xem tất cả các nút anh em, nếu lấy được mà không cần cân bằng lại, thì xong.
If, though, you steal a key from either one of your siblings and it makes them less than half full, then you have to do a merge, in which case you'll end up deleting a key, a discriminating key, in your parent above you, which may, again, recursively go all the way to the top and cause you to rewrite the entire tree.
Nhưng nếu bạn lấy một khóa từ một trong hai nút anh em và khiến chúng đầy chưa đến một nửa, thì bạn phải thực hiện gộp (merge), và khi đó bạn sẽ xóa một khóa, một khóa phân biệt, trong nút cha phía trên bạn, việc này lại có thể lan đệ quy lên tận trên cùng và khiến bạn phải ghi lại toàn bộ cây.
All right, so let's see here. We're going to delete key six. We'll go ahead and delete that, do internal, right? Now we're less than half full after that.
Được rồi, hãy xem thử nhé. Chúng ta sẽ xóa khóa 6. Cứ xóa nó đi, nút trong, đúng không? Sau đó nút này đầy chưa đến một nửa.
So we can try to borrow from a rich sibling, being a sibling that can absorb a delete from us and still be more than half full.
Vì vậy ta có thể thử mượn từ một nút anh em còn dư, tức là nút anh em có thể bị lấy bớt một khóa mà vẫn đầy hơn một nửa.
So in this case here, we can take nine from our sibling, go ahead and put that in our data structure.
Trong trường hợp này, ta có thể lấy 9 từ nút anh em, rồi đặt nó vào cấu trúc dữ liệu của mình.
But now we need to update our parent pointer, or parent key, for the discriminator, because anybody looking for any value greater than or equal to nine, as in this current form of the tree, would end up falling along the right side, and at least this leaf node, and then completely miss the key.
Nhưng bây giờ ta cần cập nhật con trỏ cha, hay khóa cha, cho khóa phân biệt, vì bất kỳ ai tìm giá trị lớn hơn hoặc bằng 9, với dạng hiện tại của cây, sẽ đi xuống nhánh bên phải, và ít nhất là tới nút lá này, rồi hoàn toàn bỏ sót khóa.
I think it was actually not there when it actually was there. So we've got to go up and update that guy here by putting 12 there.
Nó sẽ cho rằng khóa không có ở đó trong khi thực ra nó có. Vì vậy ta phải đi lên và cập nhật khóa đó bằng cách đặt 12 vào đây.
And then now our tree is considered correct. Yes?
Và bây giờ cây của ta được coi là đúng. Bạn có câu hỏi?
So in the production system, if you're going to do something like this, would you store metadata about the root program in the code, or the number that you're using?
Trong một hệ thống production, nếu bạn làm việc như thế này, bạn có lưu metadata về chương trình gốc trong mã, hay con số mà bạn đang dùng không?
So you said in the protection system? What do you mean? Sorry. Production system. What's that? A production system. Oh, production. Sorry, sorry, sorry.
Bạn nói là hệ thống bảo vệ à? Ý bạn là gì? Xin lỗi. Hệ thống production. Sao cơ? Hệ thống production. À, production. Xin lỗi, xin lỗi.
Yeah, the question is, how do you find out whether you can steal keys from your neighbor? Yeah, you only look at the next-door neighbors. You don't try to look at all the possible siblings.
Vâng, câu hỏi là, làm sao biết được bạn có thể lấy khóa từ nút bên cạnh hay không? Vâng, bạn chỉ xem các nút anh em ngay bên cạnh. Bạn không cố xem tất cả các nút anh em có thể có.
You could, but it's just like now you're taking latches, which again, we'll talk about next week. You're just taking more locks and taking latches, not locks.
Bạn có thể làm vậy, nhưng khi đó bạn phải lấy các latch, mà ta sẽ nói đến vào tuần sau. Bạn sẽ phải lấy nhiều khóa hơn, và lấy latch chứ không phải lock.
Taking latches, and that just can slow everything else down.
Lấy latch, và điều đó có thể làm chậm mọi thứ khác.
Yes, yes, yes. But for simplicity, there's too many leaf nodes.
Vâng, vâng. Nhưng để đơn giản, có quá nhiều nút lá.
All right, let's look at a more complicated example. So I'm going to delete key 15 here.
Được rồi, hãy xem một ví dụ phức tạp hơn. Ở đây tôi sẽ xóa khóa 15.
So again, if I delete key 15 from this node, or when I delete key 15, the node is less than half full.
Vậy nếu tôi xóa khóa 15 khỏi nút này, thì khi xóa khóa 15, nút đầy chưa đến một nửa.
So I can steal from a rich sibling, and then 17 goes over there. Update the parent now to put 19 there, and now everything is all kosher and correct.
Nên tôi có thể lấy từ một nút anh em còn dư, và 17 được chuyển sang đó. Giờ cập nhật nút cha để đặt 19 vào đó, và mọi thứ đều ổn và đúng.
So that's fine. But now I want to go ahead and delete 19.
Vậy là ổn. Nhưng bây giờ tôi muốn xóa 19.
So again, I delete 19, and I want to try to see whether I can steal from one of my neighbors, and I can't.
Một lần nữa, tôi xóa 19, và tôi muốn thử xem có thể lấy từ một trong các nút bên cạnh không, nhưng không được.
Because if I take either from 13, 17 or 21, 23, I've taken from any of those nodes, they'll be less than half full.
Vì nếu tôi lấy từ 13, 17 hoặc 21, 23, thì lấy từ bất kỳ nút nào trong số đó, chúng cũng sẽ đầy chưa đến một nửa.
And then now that's not balanced, and we've got to fix that. So in this case here, we don't have a choice. We're going to have to do a merge.
Và như vậy cây không cân bằng, và ta phải sửa lại. Trong trường hợp này, ta không có lựa chọn. Ta sẽ phải thực hiện gộp.
So we're going to merge from our neighbor to our right. You could do it from the left. Different systems do different things.
Vì vậy ta sẽ gộp với nút bên phải. Bạn cũng có thể gộp từ bên trái. Các hệ thống khác nhau làm khác nhau.
It doesn't matter. As long as we sort of go one way, it doesn't matter. Actually, I think you could go both ways. For simplicity, most people go one way.
Không quan trọng. Miễn là mình đi nhất quán theo một hướng thì không quan trọng. Thật ra, tôi nghĩ bạn có thể đi cả hai hướng. Nhưng cho đơn giản, hầu hết mọi người chỉ đi một hướng.
All right, so we're going to go ahead and merge these guys.
Được rồi, vậy chúng ta sẽ tiến hành gộp hai nút này.
So in this case here, we're going to basically take all the keys, 21, 23, and put it in the node where 20 is located here.
Trong trường hợp này, về cơ bản chúng ta lấy tất cả các khóa, 21, 23, và đưa vào nút chứa khóa 20 ở đây.
And we have to then delete the discriminator key in our parent, because we don't need to point down now to this other node.
Sau đó chúng ta phải xóa khóa phân biệt (discriminator key) trong nút cha, vì giờ chúng ta không cần trỏ xuống nút kia nữa.
It doesn't exist anymore. So after we did this, our leaf nodes are all balanced. That's fine. But now this parent node is less than half full. So now we've got to do a merge.
Nó không còn tồn tại nữa. Vậy sau khi làm xong, các nút lá của chúng ta đều đã cân bằng. Vậy là ổn. Nhưng bây giờ nút cha này lại ít hơn một nửa. Nên bây giờ chúng ta phải gộp tiếp.
And essentially to do this, because it's the root, we can pull the root down here, merge these guys together into a new node like this. Right? And the height of our tree has shrunk.
Về cơ bản, để làm việc này, vì đây là nút gốc, chúng ta có thể kéo nút gốc xuống đây, rồi gộp các nút này lại thành một nút mới như thế này. Đúng không? Và chiều cao của cây đã giảm đi.
And then all of the discriminator keys correctly point to the pages that we want.
Và tất cả các khóa phân biệt đều trỏ đúng đến những trang mà chúng ta muốn.
Yeah, so this question is, what do I mean by pull down? Yeah, you would see, well, this guy is under full.
Vâng, câu hỏi là: tôi muốn nói gì khi nói "kéo xuống"? Vâng, bạn sẽ thấy là nút này đang thiếu.
If I take my sibling, following that sibling pointer I'm just not showing in the diagram, then that guy would be under full.
Nếu tôi lấy nút anh em của nó, đi theo con trỏ anh em mà tôi không vẽ trong sơ đồ, thì nút đó cũng sẽ bị thiếu.
So I have no choice but to go up. In this case here, it's the root. So therefore, I know I can bring it down and then collapse them together into a single node.
Nên tôi không còn cách nào khác ngoài đi lên trên. Trong trường hợp này, đó là nút gốc. Vì vậy, tôi biết có thể kéo nó xuống rồi gộp lại thành một nút duy nhất.
But point out here, so I deleted key 19, but I still have key 19 in my inner node.
Nhưng lưu ý ở đây: tôi đã xóa khóa 19, nhưng khóa 19 vẫn còn trong nút trong.
And again, in a B+tree, that's OK, because it's just a guidepost to tell us where to go find the things that we want.
Và một lần nữa, trong B+tree thì điều đó không sao, vì nó chỉ là một cột mốc chỉ đường cho chúng ta biết đi đâu để tìm thứ mình muốn.
You wouldn't actually say, oh, I got key 19 in the inner node, I'm looking for key 19, I'm done.
Bạn sẽ không nói rằng: ồ, khóa 19 có trong nút trong, mình đang tìm khóa 19, vậy là xong.
You always have to check the leaf node to see whether it actually exists or not. So it's OK, the key 19 is in there already.
Bạn luôn phải kiểm tra nút lá để xem nó có thực sự tồn tại hay không. Nên không sao, khóa 19 đã nằm trong đó rồi.
Which means that we can throw away anything we don't need in our inner nodes when we do this compaction or merging. Because, again, we're not throwing away real data.
Điều đó có nghĩa là chúng ta có thể bỏ đi bất cứ thứ gì không cần trong các nút trong khi thực hiện việc thu gọn hay gộp này. Vì, một lần nữa, chúng ta không vứt bỏ dữ liệu thật.
Long as our discriminator keys correctly point to the parts that we want in our leaf nodes, it's OK for us to go from five keys to four keys.
Miễn là các khóa phân biệt trỏ đúng đến những phần mà chúng ta muốn trong các nút lá, thì việc chuyển từ năm khóa xuống bốn khóa là không sao.
Yes.
Vâng.
This question is, has the root been underfilled from the beginning in this example? Yes. The root is like a special case.
Câu hỏi này là: nút gốc có bị thiếu ngay từ đầu trong ví dụ này không? Đúng. Nút gốc là một trường hợp đặc biệt.
You can kind of let that go less than half full. That's usually how it works.
Bạn có thể để nó ít hơn một nửa. Thường thì hoạt động như vậy.
Yes.
Vâng.
Yeah, this question is, if the node 59 could handle sending a key over to the sibling, what we had to redistribute, then you wouldn't have to touch the leaf nodes.
Vâng, câu hỏi này là: nếu nút 59 có thể chuyển một khóa sang nút anh em, tức là phần chúng ta phải phân phối lại, thì bạn sẽ không cần động đến các nút lá.
All you'd have to do, say there was key, I don't know, four, five, nine, and I send nine over.
Bạn chỉ cần, giả sử có khóa, tôi không biết nữa, bốn, năm, chín, và tôi chuyển số chín sang.
All you need to do is drop the pointer from, I'm going to use the laser pointer, drop that pointer here, give it a this, then now you have a new one point to that.
Bạn chỉ cần bỏ con trỏ từ, tôi sẽ dùng bút laser, bỏ con trỏ đó ở đây, gán nó như thế này, rồi cho một con trỏ mới trỏ vào đó.
And that's all fine. Yeah, that's fine.
Và như vậy là ổn. Vâng, vậy là được.
OK. Well, if you follow this so far, congrats. This is the B+tree. Of course, the devil's in the details. Implementing it will be challenging for project two.
Được rồi. Nếu bạn theo kịp đến đây thì xin chúc mừng. Đây là B+tree. Tất nhiên, vấn đề nằm ở các chi tiết. Việc cài đặt nó sẽ khá thử thách trong project hai.
But the gist of it is pretty straightforward.
Nhưng ý chính của nó thì khá đơn giản.
The challenge really comes to be when you start having to do concurrent access of doing splits and merges while other threads are trying to read and write data at the same time.
Thử thách thực sự xuất hiện khi bạn bắt đầu phải xử lý truy cập đồng thời khi thực hiện các lần tách và gộp node trong lúc các luồng khác đang cố đọc và ghi dữ liệu cùng lúc.
That's where things get tricky. All right.
Đó là lúc mọi thứ trở nên phức tạp. Được rồi.
So I sort of mentioned this before, that the great things about B+trees is that you can use composite keys or composite indexes, use them as composite indexes, which basically means you have a key that's comprised of multiple attributes.
Tôi đã nhắc đến điều này trước đó, rằng điểm tuyệt vời của B+tree là bạn có thể dùng khóa tổ hợp hay chỉ mục tổ hợp, dùng chúng như chỉ mục tổ hợp, nghĩa là về cơ bản bạn có một khóa gồm nhiều thuộc tính.
So I can create an index on table xxx. And in here, you can see that I'm using three columns, a, b, and c, for my key.
Vậy tôi có thể tạo một chỉ mục trên bảng xxx. Ở đây, bạn thấy tôi dùng ba cột a, b và c làm khóa.
And I can also specify additional metadata about what should be the sort order on a per-key basis or whether I want the nulls to be first or last on a per-key basis.
Tôi cũng có thể chỉ định thêm siêu dữ liệu về việc thứ tự sắp xếp sẽ như thế nào cho từng khóa hoặc muốn giá trị null đứng đầu hay cuối cho từng khóa.
And then now, in a B+tree, because I'm not hashing, where I'm sort of randomizing the keys, I can do a bunch of different lookups on having either the entire keys or all the keys or a subset of the keys.
Và bây giờ, trong B+tree, vì tôi không băm, tức là không ngẫu nhiên hóa các khóa, tôi có thể thực hiện nhiều kiểu tra cứu khác nhau, với toàn bộ khóa hoặc một tập con của các khóa.
And everything just all works. So again, I have an index on a, b, and c. I can do a lookup on a, and b, and c, or an index on a and b.
Và mọi thứ đều hoạt động. Vậy, tôi có một chỉ mục trên a, b và c. Tôi có thể tra cứu theo a, b và c, hoặc theo chỉ mục trên a và b.
And in some systems, Oracle and now Postgres now has too, you can do what are called skip scans or partial keys, where I don't have the prefix.
Và ở một số hệ thống, như Oracle và giờ là cả Postgres, bạn có thể làm cái gọi là skip scan hay khóa một phần, khi tôi không có tiền tố.
I don't have a, but I can still do lookups on b and c. There's extra machinery to make that work. We'll see that in this slide. OK.
Tôi không có a, nhưng vẫn có thể tra cứu theo b và c. Cần có thêm cơ chế để làm được điều đó. Chúng ta sẽ thấy ở slide này. Được rồi.
So again, say I have a key on a and b. And so again, you can see that the keys now are comprised of multiple things. These are just the bits stored sequentially after another.
Vậy, giả sử tôi có một khóa trên a và b. Bạn có thể thấy các khóa giờ gồm nhiều thành phần. Đây chỉ là các bit được lưu liên tiếp nhau.
There's nothing that's really special about it. And because it's now, it's all declared in SQL, I know what the size of the data type I'm trying to store is.
Chẳng có gì đặc biệt cả. Và vì mọi thứ đều được khai báo trong SQL, tôi biết kích thước của kiểu dữ liệu mình đang lưu.
So I know how to interpret a byte array as the first 32 bits is an integer for key a, and the next 32 bits are an integer for key b.
Nên tôi biết cách diễn giải một mảng byte như sau: 32 bit đầu là một số nguyên cho khóa a, và 32 bit tiếp theo là một số nguyên cho khóa b.
All that you know because it's in the catalog when you created the table, or created the index.
Tất cả những điều đó bạn biết vì nó nằm trong catalog khi bạn tạo bảng, hoặc tạo chỉ mục.
So if I want to do a lookup on key 1, 2, where a equals 1 and b equals 2. So again, I just jump to the first node.
Vậy nếu tôi muốn tra cứu khóa 1, 2, tức là a bằng 1 và b bằng 2. Tôi chỉ việc nhảy đến node đầu tiên.
I look at the first key in my composite index, so my composite key. 1 is less than 1, and then 2 is less than or equal to 3.
Tôi xem khóa đầu tiên trong chỉ mục tổ hợp, tức là khóa tổ hợp của tôi. 1 nhỏ hơn 1, rồi 2 nhỏ hơn hoặc bằng 3.
And I know how to then jump down to the leaf node to find the thing that I'm looking for. So that's when you look up when you have all the answers, the full lookup.
Và tôi biết cách nhảy xuống node lá để tìm thứ mình cần. Đó là khi bạn tra cứu mà có đủ mọi thông tin, tức tra cứu đầy đủ.
If you only have the first key and not the other keys, like a prefix lookup, then, well, in this case here, I just do the lookup for the first key that I do have.
Nếu bạn chỉ có khóa đầu tiên mà không có các khóa còn lại, như tra cứu theo tiền tố, thì, trong trường hợp này, tôi chỉ tra cứu theo khóa đầu tiên mà mình có.
1 is less than or equal to 1. I then jump down to this leaf node here. But now, since I don't know...
1 nhỏ hơn hoặc bằng 1. Rồi tôi nhảy xuống node lá này. Nhưng bây giờ, vì tôi không biết...
Since there may be multiple keys or multiple key-value pairs in my leaf nodes where key a equals 1, I have to scan along the leaf nodes until I find the first entry where key a does not equal 1.
Vì có thể có nhiều khóa hoặc nhiều cặp khóa-giá trị trong các nút lá của tôi mà khóa a bằng 1, nên tôi phải quét dọc theo các nút lá cho đến khi tìm thấy mục đầu tiên mà khóa a không bằng 1.
Right? So in this case here, I would come across the next key in this leaf node, that key a equals 2.
Đúng không? Vậy ở trường hợp này, tôi sẽ gặp khóa tiếp theo trong nút lá này, là khóa a bằng 2.
I know that doesn't equal 1, so I can stop scanning there and not have to look anything up for that.
Tôi biết nó không bằng 1, nên tôi có thể dừng quét ở đó và không cần tra cứu gì thêm cho nó.
So I can do a sequential scan along the leaf nodes and find everything I want.
Vậy tôi có thể quét tuần tự dọc theo các nút lá và tìm ra mọi thứ tôi muốn.
And the last one, as I said, you can actually do a suffix search, or Oracle calls them skip scans.
Và trường hợp cuối cùng, như tôi đã nói, thực ra bạn có thể tìm kiếm theo hậu tố, hoặc Oracle gọi đó là skip scan.
Basically, it says, I don't know what's in the prefix of my key. I don't have that. I only have the second part. Right? So I have... I don't have a, but I have b.
Về cơ bản, nó nói rằng tôi không biết phần tiền tố của khóa là gì. Tôi không có phần đó. Tôi chỉ có phần thứ hai. Đúng không? Tức là tôi không có a, nhưng tôi có b.
So in this case here, there's nothing really magical you can do. You kind of got to look at everything. Right?
Vậy ở trường hợp này, thực sự không có chiêu gì đặc biệt cả. Bạn đại khái phải xem hết mọi thứ. Đúng không?
You got to look at all the leaf nodes. But you can do this in parallel.
Bạn phải xem tất cả các nút lá. Nhưng bạn có thể làm việc này song song.
They can all scan across the leaf nodes until you find all the matches that you want where b equals 1. Because again, it's sort of... This key is first sorted on a, then b.
Chúng đều có thể quét qua các nút lá cho đến khi bạn tìm được mọi kết quả khớp mà bạn muốn, với b bằng 1. Bởi vì, một lần nữa, khóa này được sắp xếp theo a trước, rồi mới đến b.
So all the a's... You know, a equals 1 is going to be on one side, then 2s and 3s and so forth. The b values are kind of just...
Nên tất cả các giá trị a... Bạn biết đấy, a bằng 1 sẽ nằm ở một phía, rồi đến các giá trị 2, 3 và cứ thế. Còn các giá trị b thì chỉ...
They're sort of within each subset of the a values. Like a group by with multiple columns. Yes?
nằm trong từng tập con của các giá trị a. Giống như group by với nhiều cột. Bạn hỏi gì?
What do you mean, I reordered the keys?
Ý bạn là sao, tôi sắp xếp lại các khóa?
This question is, if I... Do I have to specify in my SQL query, my where clause, the keys in the same order that the index is defined on?
Câu hỏi này là, nếu tôi... Tôi có phải chỉ định trong truy vấn SQL, trong mệnh đề where, các khóa theo cùng thứ tự mà chỉ mục được định nghĩa không?
No. Again, it's declarative. SQL says, I do a lookup on a equals 1 and b equals 2. Right? I can do b equals 2 and a equals 1. Semantically, they're the same.
Không. Một lần nữa, nó mang tính khai báo. SQL nói rằng tôi tra cứu a bằng 1 và b bằng 2. Đúng không? Tôi có thể viết b bằng 2 và a bằng 1. Về ngữ nghĩa thì chúng giống nhau.
Because you wrote them in that order. It doesn't mean I'm going to run them in that order. Right?
Vì bạn viết chúng theo thứ tự đó. Điều đó không có nghĩa là tôi sẽ chạy chúng theo thứ tự đó. Đúng không?
The question is, are the optimizers actually smart enough to see that? The good ones are. Right?
Câu hỏi là, các trình tối ưu hóa có thực sự đủ thông minh để nhận ra điều đó không? Những cái tốt thì có. Đúng không?
Most of the ones you can think of, like Oracle, Postgres, MySQL, all of them are... They'll do it. When we talk about join ordering, there's a bunch of systems...
Hầu hết những hệ thống bạn nghĩ đến, như Oracle, Postgres, MySQL, tất cả đều... Chúng sẽ làm được. Khi nói về thứ tự join, có một loạt hệ thống...
It's a join ordering. You basically want to figure out the right way to join order... To join tables. And that way, you can have a huge difference in performance.
Đó là thứ tự join. Về cơ bản, bạn muốn tìm ra cách đúng để sắp thứ tự join các bảng. Và cách đó có thể tạo ra sự chênh lệch hiệu năng rất lớn.
There's a bunch of systems where they'll go in the order that you define in the SQL query. And they don't try to reorder it for you.
Có một loạt hệ thống sẽ chạy theo thứ tự mà bạn định nghĩa trong truy vấn SQL. Và chúng không cố sắp xếp lại giúp bạn.
The good ones say, like, I don't care how you defined it. I'm going to figure out the best way to do it. Right? So Oracle used to do that.
Những hệ thống tốt thì nói kiểu: tôi không quan tâm bạn định nghĩa thế nào. Tôi sẽ tự tìm cách tốt nhất để làm. Đúng không? Oracle từng làm như vậy.
Oracle in the 80s... We'll cover this later. Used to say, oh, yeah, no. We're going to give you a query plan in the order that you define the tables.
Oracle những năm 80... Chúng ta sẽ học sau. Từng nói: ồ, vâng, không. Chúng tôi sẽ đưa bạn một kế hoạch truy vấn theo đúng thứ tự bạn định nghĩa các bảng.
Because that's... They call it a semantic optimizer. It's all bull****. It's like, oh, here's the... This is the order you meant it to be in. So we're going to run it that way.
Vì đó là... Họ gọi nó là trình tối ưu hóa ngữ nghĩa. Toàn là nhảm nhí. Kiểu như, ồ, đây là... Đây là thứ tự mà bạn muốn. Nên chúng ta sẽ chạy theo cách đó.
Even though that wasn't actually what the right way to do it is. We'll cover this later. Yes. There's a lot... A lot of systems...
Dù thực ra đó không phải là cách đúng để làm. Chúng ta sẽ học phần này sau. Vâng. Có rất nhiều... Rất nhiều hệ thống...
Forgetting this, right? It's not hard. Join order is the harder one. And some systems will cheap out on that. Okay. So, all right. Duplicate keys.
Quên chuyện này đi, đúng không? Nó không khó. Thứ tự join mới là phần khó hơn. Và một số hệ thống sẽ làm qua loa chỗ đó. Được rồi. Nào, tiếp tục. Khóa trùng lặp.
So we've talked about primary key indexes. Primary key indexes have to be guaranteed unique. Our primary key has to be guaranteed unique. You can also have secondary indexes.
Chúng ta đã nói về các chỉ mục khóa chính. Chỉ mục khóa chính phải đảm bảo là duy nhất. Khóa chính của chúng ta phải đảm bảo là duy nhất. Bạn cũng có thể có các chỉ mục phụ.
Where, again, you can define that the secondary index has to be unique on the keys. In actuality, though, a lot of systems actually still don't store things... They still will have duplicate keys.
Ở đó, một lần nữa, bạn có thể định nghĩa rằng chỉ mục phụ phải là duy nhất trên các khóa. Tuy nhiên, thực tế là rất nhiều hệ thống vẫn không lưu mọi thứ... Chúng vẫn sẽ có các khóa trùng lặp.
Because you may do multi-versioning. We'll cover that later. But I may have multiple versions of a tuple. That they're all gonna have the same primary key.
Vì bạn có thể dùng đa phiên bản. Chúng ta sẽ học sau. Nhưng tôi có thể có nhiều phiên bản của một tuple. Tất cả chúng sẽ có cùng một khóa chính.
And I gotta put this in the index in order to find them. So how do you handle... How do you handle that? All right. Or think of, like, people...
Và tôi phải đưa chúng vào chỉ mục để tìm được chúng. Vậy làm sao xử lý... Làm sao xử lý chuyện đó? Được rồi. Hoặc hãy nghĩ đến, ví dụ, con người...
If you have an index on the zip code for people's address... Mailing address. There's a bunch of people that live in 15217, 15213 in Pittsburgh.
Nếu bạn có chỉ mục trên mã bưu chính trong địa chỉ của mọi người... Địa chỉ gửi thư. Có cả đống người sống ở 15217, 15213 tại Pittsburgh.
So I can't have you... How am I gonna handle having duplicate keys in that case? So there's two ways to do this. The first one is the right one.
Vậy tôi không thể để bạn... Tôi sẽ xử lý các khóa trùng lặp trong trường hợp đó thế nào? Có hai cách. Cách đầu tiên là cách đúng.
The second one, don't do this. All right. So the first one is you basically store a hidden value... Or sorry, a hidden attribute in the key of the index.
Cách thứ hai thì đừng làm. Được chứ. Cách đầu tiên là về cơ bản bạn lưu một giá trị ẩn... À xin lỗi, một thuộc tính ẩn trong khóa của chỉ mục.
That's gonna be the record ID of the thing I want to point to. Remember, the record ID is like a page number and an offset.
Đó sẽ là record ID của thứ mà tôi muốn trỏ tới. Hãy nhớ, record ID giống như một số trang và một offset.
It's going to be physically unique for every single physical value. So even though I'm going to declare my index on the zip code...
Nó sẽ là duy nhất về mặt vật lý cho từng giá trị vật lý. Vì vậy, dù tôi khai báo chỉ mục trên mã bưu chính...
I'm actually storing the key. I'm also going to store the record ID. And it'll be hidden from you as the end user. You can't see it through SQL.
Thực ra tôi đang lưu khóa. Tôi cũng sẽ lưu cả record ID. Và nó sẽ bị ẩn khỏi bạn, người dùng cuối. Bạn không thể thấy nó qua SQL.
And the reason why B+trees are going to work for this... Because we can do that prefix scan. Because if I have an index on A and B...
Và lý do B+tree sẽ dùng được cho việc này... Là vì chúng ta có thể quét theo tiền tố. Vì nếu tôi có chỉ mục trên A và B...
But I only have the value of key A, the first part... I can still do lookups on it. So now I can do my lookup on the zip code without having your record ID...
Nhưng tôi chỉ có giá trị của khóa A, phần đầu tiên... Tôi vẫn có thể tra cứu trên nó. Vậy giờ tôi có thể tra cứu theo mã bưu chính mà không cần có record ID của bạn...
And find all the entries that I wanted. The alternative is to do overflow leaf nodes. Now, we'll see overflow nodes to handle large keys.
Và tìm tất cả các mục mà tôi muốn. Cách thay thế là dùng các nút lá tràn. Chúng ta sẽ thấy các nút tràn dùng để xử lý khóa lớn.
Which you kind of have to do. There's no way to get around this. But if you want to handle duplicate keys, you got to overflow on the leaf nodes.
Điều này gần như bắt buộc. Không có cách nào tránh được. Nhưng nếu muốn xử lý khóa trùng lặp, bạn phải tràn trên các nút lá.
Don't do this, even though it's going to look very similar. One is sort of... This is all semantics. One is sort of overflowing down versus across.
Đừng làm cách này, dù nó trông rất giống. Một cách thì kiểu... Đây toàn là cách gọi thôi. Một cách là tràn xuống so với tràn sang ngang.
Don't do the down one. Do the across one. It'll make more sense in the next slide. So the first one: append the record ID. So the key now is going to be...
Đừng làm cách xuống. Hãy làm cách sang ngang. Slide tiếp theo sẽ dễ hiểu hơn. Vậy cách đầu tiên: nối thêm record ID. Vậy khóa bây giờ sẽ là...
Whatever the real key is, I define on column A. But also, in that same byte array for that key, I'm going to store the record ID.
Bất kể khóa thật là gì, tôi định nghĩa trên cột A. Nhưng cũng trong cùng mảng byte đó cho khóa ấy, tôi sẽ lưu cả record ID.
And that'll be guaranteed uniqueness, because there's only one physical tuple. It could be at some physical address in my pages at an offset.
Và điều đó đảm bảo tính duy nhất, vì chỉ có một tuple vật lý. Nó có thể nằm ở một địa chỉ vật lý nào đó trong các trang của tôi, tại một offset.
So this guarantees uniqueness, even though I may have the same key over and over again. So now I want to do keys. So I'm going to insert six in my data structure, my B+tree.
Vậy cách này đảm bảo tính duy nhất, dù tôi có thể có cùng một khóa lặp đi lặp lại. Giờ tôi muốn làm với các khóa. Tôi sẽ chèn số sáu vào cấu trúc dữ liệu của mình, tức B+tree.
What I'm really doing is inserting six, followed by the page number and the offset. And then now I just do the traversal down, looking at the first key for six.
Thực chất điều tôi đang làm là chèn sáu, theo sau là số trang và offset. Rồi tôi chỉ việc duyệt xuống, xét khóa đầu tiên là sáu.
Then I land into whatever the leaf node that I want, and store the thing that I want. In this case here, I have to do a split, and everything works out fine.
Sau đó tôi đến nút lá mà mình muốn, và lưu thứ tôi cần lưu. Trong trường hợp này, tôi phải tách nút, và mọi thứ vẫn ổn.
If I want to overflow nodes, I already have key six in my data structure. Now I want to insert six again.
Nếu muốn dùng nút tràn, thì tôi đã có khóa sáu trong cấu trúc dữ liệu rồi. Giờ tôi muốn chèn sáu thêm lần nữa.
So I traverse down, I enter this leaf node here, see that it's already full.
Vậy tôi duyệt xuống, vào nút lá này, và thấy nó đã đầy.
So I'm going to add another page to it, and just maintain a linked list going in the vertical direction, going down.
Nên tôi sẽ thêm một trang nữa vào nó, và duy trì một danh sách liên kết theo chiều dọc, đi xuống.
It violates that log n lookup, because now I have to jump to this one and maybe keep scanning.
Cách này phá vỡ việc tra cứu log n, vì giờ tôi phải nhảy sang nút này và có thể phải quét tiếp.
But it's sort of like the chain hash table, where I could just keep adding buckets to my chain in order to accommodate when I have overflow.
Nhưng nó hơi giống bảng băm dạng chuỗi, nơi tôi có thể cứ thêm các bucket vào chuỗi để chứa phần tràn khi xảy ra tràn.
It's basically the same idea. I want to insert seven. So four is sitting out here.
Về cơ bản là cùng một ý tưởng. Tôi muốn chèn bảy. Còn bốn nằm ngoài này.
So in this case here, I can absorb a bunch of writes into this overflow leaf node here, and I'm not changing any of the discriminator keys in my inner nodes up above.
Vậy trong trường hợp này, tôi có thể hấp thụ một loạt thao tác ghi vào nút lá tràn này, và tôi không thay đổi bất kỳ khóa phân biệt nào trong các nút trong phía trên.
Insert six and do the same thing.
Chèn sáu và làm tương tự.
The reason why this is a bad idea is because if I need to now do a split, because I want to insert, say, key 7.5, that logically should go between seven and eight.
Lý do đây là ý tưởng tồi là vì nếu giờ tôi cần tách nút, vì tôi muốn chèn, chẳng hạn, khóa 7,5, mà về logic phải nằm giữa bảy và tám.
Now I've got to do a split, and now I've got to remove all this other crap down below as well. I have to scan them all. Bring them all into memory.
Giờ tôi phải tách nút, và còn phải gỡ hết đống lộn xộn khác bên dưới nữa. Tôi phải quét hết chúng, đưa tất cả vào bộ nhớ.
Figure out where they need to go and split them up. And they now may have overflows on both sides, or both the new pages. Yes.
Xác định chúng cần đi đâu rồi chia ra. Và chúng có thể bị tràn ở cả hai phía, hoặc ở cả hai trang mới. Vâng, mời bạn.
This question is, for this one here, because C6 already existed, am I only inserting the page number and the slot number in the new key I'm inserting, or all the keys?
Câu hỏi là, ở chỗ này, vì C6 đã tồn tại rồi, thì tôi chỉ chèn số trang và số slot vào khóa mới mà tôi chèn, hay chèn tất cả các khóa?
It has to be all the keys.
Phải là tất cả các khóa.
The question is, do you change the B+tree for all the keys? Yes. Postgres does this. Most systems have to do this.
Câu hỏi là, bạn có thay đổi B+tree cho mọi khóa không? Có. Postgres làm vậy. Hầu hết các hệ thống đều phải làm vậy.
So cluster index is basically the idea. Sometimes you hear things referred to as cluster index or cluster table. It just means sorted, a sorted table.
Vậy ý tưởng của chỉ mục cụm (cluster index) về cơ bản là thế. Đôi khi bạn nghe gọi là cluster index hay cluster table. Nó chỉ có nghĩa là đã được sắp xếp, một bảng được sắp xếp.
And it's sorted based on some B+tree up above, right? You can't use hash index, hash table, because that's not sorted. But it'll be B+tree up above.
Và nó được sắp xếp dựa trên một B+tree nào đó ở phía trên, đúng không? Bạn không thể dùng chỉ mục băm, bảng băm, vì nó không được sắp xếp. Mà sẽ là B+tree ở phía trên.
And so if you do index organized storage, like MySQL and Post, or MySQL and SQLite, you get this for free, because the leaf nodes are sorting the data based on the primary key up above in the inner nodes.
Và nếu bạn dùng lưu trữ có tổ chức theo chỉ mục, như MySQL và Post, hoặc MySQL và SQLite, bạn có được điều này miễn phí, vì các nút lá sắp xếp dữ liệu dựa trên khóa chính ở phía trên, trong các nút trong.
In some systems, you can create a table using heap storage, so unordered tuples.
Ở một số hệ thống, bạn có thể tạo bảng dùng heap storage, tức là các tuple không có thứ tự.
But then you can tell the data system, oh, by the way, manage this, make sure things are sorted based on this other data structure here. And in some systems, they'll maintain it.
Nhưng sau đó bạn có thể bảo hệ quản trị dữ liệu: này, hãy quản lý cái này, đảm bảo dữ liệu được sắp xếp dựa trên cấu trúc dữ liệu khác này. Và ở một số hệ thống, chúng sẽ duy trì thứ tự đó.
So if I insert new things, it'll make sure everything's still sorted. In other systems like Postgres, you can call this a cluster command.
Nên nếu tôi chèn dữ liệu mới, hệ thống sẽ đảm bảo mọi thứ vẫn được sắp xếp. Ở các hệ thống khác như Postgres, bạn có thể gọi lệnh cluster.
It'll sort your table based on some index. But it'll do it once. And then if it's updated and changed over time, it doesn't maintain the sort order.
Nó sẽ sắp xếp bảng của bạn theo một index nào đó. Nhưng chỉ làm một lần. Sau đó nếu bảng được cập nhật và thay đổi theo thời gian, nó không duy trì thứ tự sắp xếp.
You've got to run the cluster thing again. So the reason why this matters is that it's going to make a lookup some more efficient in many cases, right?
Bạn phải chạy lại lệnh cluster. Lý do điều này quan trọng là nó sẽ làm cho việc tra cứu hiệu quả hơn trong nhiều trường hợp, đúng không?
And we have to get things from disk.
Và chúng ta phải lấy dữ liệu từ đĩa.
So if my table pages are sorted in the same order that's defined by the index, then when I want to do a scan and try to find data, I can just, again, use my index to find some offset within or some location at a table page, and then scan along the rest of the pages, and I'll find everything that I want.
Nên nếu các trang của bảng được sắp xếp cùng thứ tự với thứ tự mà index định nghĩa, thì khi tôi muốn quét và tìm dữ liệu, tôi có thể dùng index để tìm một offset hay một vị trí nào đó trong trang của bảng, rồi quét tiếp các trang còn lại, và sẽ tìm thấy mọi thứ tôi cần.
Where things can go wrong is that if the index is going to define one sort order, but then the data is going to be sorted in another sort order, I may have really inefficient access if I naively retrieve whatever the page is the index is pointing to one at a time.
Vấn đề có thể xảy ra là nếu index định nghĩa một thứ tự sắp xếp, nhưng dữ liệu lại được sắp xếp theo một thứ tự khác, thì việc truy cập có thể rất kém hiệu quả nếu tôi lấy một cách ngây thơ từng trang mà index trỏ tới, lần lượt từng trang một.
So let's say I'm trying to find some range of data between these pages here.
Giả sử tôi đang tìm một khoảng dữ liệu nằm giữa các trang này.
And so if you look at the pointers in my, or the record IDs in my index and the leaf nodes, they're basically pointing to all different locations in these different pages.
Và nếu bạn nhìn vào các con trỏ trong index của tôi, hay các record ID trong index và các nút lá, về cơ bản chúng trỏ tới các vị trí khác nhau trong các trang khác nhau này.
So if I do a sequential scan, just starting at whatever the first key that I want, and then just go get that data, and then go look at the next key in the order defined by the index, I'm going to start jumping around at these different pages over and over again unnecessarily.
Vậy nếu tôi quét tuần tự, bắt đầu từ khóa đầu tiên mà tôi muốn, rồi đi lấy dữ liệu đó, rồi xem khóa tiếp theo theo thứ tự mà index định nghĩa, tôi sẽ nhảy qua nhảy lại giữa các trang khác nhau này hết lần này đến lần khác một cách không cần thiết.
So if you think of a really stupid system that only has one slot, or one frame in our buffer pool, I would read page 102, throw that away, then read page 103, throw that away, and then read page 104.
Nếu bạn nghĩ đến một hệ thống thật ngớ ngẩn chỉ có một ô, hay một frame trong buffer pool, tôi sẽ đọc trang 102, rồi bỏ nó đi, rồi đọc trang 103, bỏ đi, và sau đó đọc trang 104.
In which case here, I have two keys that are both in page 104, and I can read that page, use that page twice.
Trong trường hợp này, tôi có hai khóa cùng nằm trong trang 104, và tôi có thể đọc trang đó và dùng nó hai lần.
So in a bunch of systems, the simple optimization is you'd actually first do a scan on the index, find all the record IDs and the corresponding page IDs that you know you're going to need to access, sort them by the page ID, and then now go retrieve them in that sort order.
Vì vậy ở nhiều hệ thống, cách tối ưu đơn giản là trước tiên quét trên index, tìm tất cả record ID và các page ID tương ứng mà bạn biết mình sẽ cần truy cập, sắp xếp chúng theo page ID, rồi mới đi lấy chúng theo thứ tự đã sắp xếp đó.
So that guarantees I'm only retrieving each page once and only once.
Như vậy đảm bảo mỗi trang chỉ được lấy đúng một lần.
I still have to maintain some metadata to keep track of what's the key sort order that came out of the index, but I'm basically going to scan the index first, figure out what I need, then go get it.
Tôi vẫn phải duy trì một ít metadata để theo dõi thứ tự sắp xếp của các khóa đã đi ra từ index là gì, nhưng về cơ bản tôi sẽ quét chỉ mục trước, xác định xem mình cần gì, rồi mới đi lấy dữ liệu.
And you can start playing other games.
Và bạn có thể bắt đầu chơi những chiêu khác.
We'll see next class, or in a couple weeks if I have, where A equals one and I have an index on that, and B equals two and I have a separate index on that, I'll do an index scan across them both, then do an intersection of those two lists of page IDs to figure out what's the minimal set that I actually need, then go get those pages.
Chúng ta sẽ thấy ở buổi sau, hoặc vài tuần nữa nếu tôi kịp, trong đó A bằng một và tôi có một chỉ mục trên đó, và B bằng hai và tôi có một chỉ mục riêng trên đó, tôi sẽ quét chỉ mục trên cả hai, rồi lấy giao của hai danh sách ID trang đó để xác định tập tối thiểu mà tôi thực sự cần, rồi mới đi lấy các trang đó.
Postgres calls this a bitmap heap scan. So we can use these indexes to help us be more intelligent about going to the data that we need to avoid random IO.
Postgres gọi cách này là bitmap heap scan. Vậy chúng ta có thể dùng các chỉ mục này để truy cập dữ liệu cần thiết một cách thông minh hơn, nhằm tránh IO ngẫu nhiên.
All right, so let me get through the node design choices. And like I said, I want to plow through as many optimizations as we can. These ones are pretty straightforward.
Được rồi, giờ tôi sẽ đi qua các lựa chọn thiết kế nút. Và như tôi đã nói, tôi muốn lướt qua càng nhiều tối ưu hóa càng tốt. Những cái này khá đơn giản.
And again, just to reiterate how important this data structure is just for humanity, there's a book written about 10 years ago on modern B+trees. So here's like a data structure from the 1970s.
Và nhắc lại để thấy cấu trúc dữ liệu này quan trọng thế nào với nhân loại, có một cuốn sách viết khoảng 10 năm trước về B+tree hiện đại. Đây là một cấu trúc dữ liệu từ thập niên 1970.
Here's all the modern incarnations and optimizations you can do to it to make these things go better.
Còn đây là tất cả các phiên bản hiện đại và các tối ưu hóa bạn có thể áp dụng để làm nó tốt hơn.
And again, it's so important that they wrote a second book that came out last year on more modern B+trees.
Và nó quan trọng đến mức họ đã viết cuốn thứ hai, ra mắt năm ngoái, về các B+tree hiện đại hơn nữa.
And the guy that wrote this is, we're going to see multiple times throughout the semester, that he's going to invent the iterator model of the Volcano query processing model.
Và người viết cuốn này là người mà chúng ta sẽ gặp lại nhiều lần trong suốt học kỳ, ông ấy sẽ phát minh ra mô hình iterator của mô hình xử lý truy vấn Volcano.
He's going to invent the way we want to build query optimizers. He's going to invent the way we're going to do parallel operations in our database system.
Ông ấy sẽ phát minh ra cách chúng ta xây dựng bộ tối ưu hóa truy vấn. Ông ấy sẽ phát minh ra cách chúng ta thực hiện các thao tác song song trong hệ quản trị cơ sở dữ liệu.
So this guy is brilliant, and he's written the definitive guide on B+trees. Notice though, he calls them B-trees instead of B+trees, right? But it's the same thing. All right.
Người này rất xuất sắc, và ông ấy đã viết cuốn hướng dẫn chuẩn mực về B+tree. Nhưng để ý là ông ấy gọi chúng là B-tree thay vì B+tree, nhé? Nhưng nó là một thứ thôi. Được rồi.
Node size should be pretty obvious that you can have different node sizes for the inner nodes versus the leaf nodes.
Về kích thước nút thì khá hiển nhiên là bạn có thể dùng kích thước nút khác nhau cho nút trong và nút lá.
Typically, you want to maybe have larger inner nodes than leaf nodes, assuming you're not storing the tuples themselves or just record IDs, because then you can have a, within one node, you can have a higher fan out and find things more quickly.
Thông thường, bạn muốn nút trong lớn hơn nút lá, giả sử bạn không lưu chính các tuple mà chỉ lưu record ID, vì khi đó trong một nút, bạn có thể có fan out cao hơn và tìm thấy dữ liệu nhanh hơn.
And then of course, the size of the node is going to depend on what the hardware looks like.
Và tất nhiên, kích thước nút sẽ phụ thuộc vào phần cứng như thế nào.
So the way the research basically plays out is that if your hardware is very, very fast, your storage is very, very fast, like in memory, then you actually want really small node sizes because you want to be able to go acquire the latch on one small page, find what you want, and what you can do quickly, immediately jump out of that.
Kết quả nghiên cứu về cơ bản cho thấy nếu phần cứng của bạn rất, rất nhanh, bộ nhớ lưu trữ rất, rất nhanh, như trong bộ nhớ, thì bạn thực sự muốn kích thước nút rất nhỏ vì bạn muốn lấy latch trên một trang nhỏ, tìm thứ cần tìm, làm nhanh những gì cần làm, rồi thoát ra ngay.
But if your hardware is slower, like a spinning disk hard drive, then you want your node sizes to be maybe one megabyte.
Nhưng nếu phần cứng chậm hơn, như ổ cứng đĩa quay, thì bạn muốn kích thước nút có thể là một megabyte.
So in a system like Postgres, you can't vary the size of index pages, but in enterprise systems like in DB2, again, you can specify different page sizes on a table basis and on an index basis.
Vậy trong một hệ thống như Postgres, bạn không thể thay đổi kích thước trang chỉ mục, nhưng trong các hệ thống doanh nghiệp như DB2, một lần nữa, bạn có thể chỉ định kích thước trang khác nhau cho từng bảng và cho từng chỉ mục.
And I think they can even discriminate between the inner nodes and the leaf nodes and have different page sizes for them.
Và tôi nghĩ họ thậm chí có thể phân biệt giữa các nút trong và các nút lá, rồi dùng kích thước trang khác nhau cho chúng.
So the merge threshold we talked about is like, if it's less than half full, then I have to do a merge or try to steal from my sibling.
Vậy ngưỡng gộp mà ta đã nói là: nếu nút đầy chưa tới một nửa, thì tôi phải gộp nút hoặc thử lấy bớt từ nút anh em của mình.
If you follow exactly that protocol, then you roughly end up with the occupancy rate of about 69, 70%.
Nếu bạn tuân theo đúng giao thức đó, thì bạn sẽ có tỉ lệ lấp đầy khoảng 69, 70%.
So about 70% of your nodes are going to be full at any given time. All right.
Tức là khoảng 70% số nút của bạn sẽ đầy tại một thời điểm bất kỳ. Được rồi.
So if you can delay the merge process as long as possible, then you can avoid some unnecessary disk IO, because you're not in a situation where I'm merging and then someone immediately inserts something and I have to split again.
Nên nếu bạn có thể trì hoãn quá trình gộp càng lâu càng tốt, thì bạn có thể tránh được một số thao tác IO đĩa không cần thiết, vì bạn sẽ không rơi vào tình huống tôi vừa gộp xong rồi ngay lập tức có người chèn thêm và tôi lại phải tách nút.
So you want to let things kind of go a little less than half full for a while. Eventually, maybe say, "I'm not using this space, let me go ahead and clean it up."
Vì vậy bạn muốn để các nút đầy chưa tới một nửa trong một thời gian. Cuối cùng, có thể bạn nói: "Tôi không dùng chỗ này, cứ dọn nó đi."
But it'll allow you to insert, handle more inserts without having to do additional splits if you don't relax this right away. And so it ends up being not exactly balanced anymore.
Nhưng điều đó cho phép bạn chèn, xử lý thêm nhiều lần chèn mà không phải tách thêm nếu bạn không nới lỏng ngay. Và vì thế cây không còn cân bằng hoàn toàn nữa.
This is why the Postgres B+tree implementation is called a non-balanced B+tree. So overall, it's balanced, but sometimes it's okay to relax that.
Đây là lý do cài đặt B+tree của Postgres được gọi là B+tree không cân bằng. Nhìn tổng thể thì nó cân bằng, nhưng đôi khi nới lỏng điều đó cũng không sao.
All right. The last question is how to handle very long keys. So there's a bunch of ways to do this. One optimization is just to store pointers.
Được rồi. Câu hỏi cuối cùng là cách xử lý các khóa rất dài. Có nhiều cách để làm việc này. Một cách tối ưu là chỉ lưu con trỏ.
So instead of actually storing the actual very long key in my nodes, my pages, I have a pointer, the record ID, to the actual tuple with that attribute I want.
Tức là thay vì lưu khóa rất dài thực sự trong các nút, các trang của tôi, tôi có một con trỏ, là record ID, trỏ tới tuple thực chứa thuộc tính mà tôi muốn.
Because I already knew how to store very long data in my table pages that we talked about before.
Vì tôi đã biết cách lưu dữ liệu rất dài trong các trang bảng mà ta đã nói trước đó.
So instead of storing that in my tuple pages, I'm going to store a record ID to it. Yes. Especially, you still need the key to range search.
Vậy thay vì lưu nó trong các trang tuple của mình, tôi sẽ lưu một record ID trỏ tới nó. Vâng. Đặc biệt là bạn vẫn cần khóa để tìm kiếm theo khoảng.
You got to follow the pointer to go get the key to figure out how to do the range search.
Bạn phải đi theo con trỏ để lấy khóa rồi mới biết cách tìm kiếm theo khoảng.
Yes. Yes. Yes. Go ahead.
Vâng. Vâng. Vâng. Bạn cứ nói.
Yes. Don't do that. This shows up in in-memory data systems in the 80s. There was a system from Oracle called TimesTen in the 90s that did this.
Vâng. Đừng làm vậy. Cách này xuất hiện trong các hệ thống dữ liệu trong bộ nhớ ở những năm 80. Có một hệ thống của Oracle tên là TimesTen vào những năm 90 đã làm như vậy.
The basic idea is like, oh, memory is so precious. Instead of storing these redundant keys, because essentially the index is storing another copy of data.
Ý tưởng cơ bản là: ồ, bộ nhớ quý giá quá. Thay vì lưu những khóa dư thừa này, vì về bản chất chỉ mục đang lưu thêm một bản sao của dữ liệu.
It's a secondary copy of the data that's in your tables.
Nó là bản sao thứ hai của dữ liệu nằm trong các bảng của bạn.
So instead of storing the secondary copy of data in my index, if I can go get the data very quickly because everything's in memory, then I'll just store the pointer to it.
Nên thay vì lưu bản sao thứ hai của dữ liệu trong chỉ mục, nếu tôi có thể lấy dữ liệu rất nhanh vì mọi thứ đều nằm trong bộ nhớ, thì tôi chỉ cần lưu con trỏ tới nó.
It turns out, though, that random access still sucks in memory as well as definitely on disk. So nobody actually does this, at least I'm aware of. Oracle still supports this in TimesTen.
Tuy nhiên, hóa ra truy cập ngẫu nhiên vẫn rất tệ trong bộ nhớ, và chắc chắn là tệ trên đĩa. Nên thực tế không ai làm vậy, ít nhất là theo những gì tôi biết. Oracle vẫn hỗ trợ điều này trong TimesTen.
By default, you went back to the B+tree. You could have variable length nodes. Basically, it allows the size...
Theo mặc định, bạn quay lại dùng B+tree. Bạn có thể có các nút độ dài thay đổi. Về cơ bản, nó cho phép kích thước...
Every single node could be arbitrarily different size. Usually, you do almost like a slab allocator. You have a one kilobyte node, a two kilobyte node, four, and so forth.
Mỗi nút có thể có kích thước khác nhau tùy ý. Thông thường, bạn làm gần giống như một slab allocator. Bạn có một nút 1 kilobyte, một nút 2 kilobyte, rồi 4, và cứ thế tiếp tục.
This one, you can do it.
Cách này thì bạn có thể làm được.
It only shows up in academic systems because it requires more memory management, because now the frames in your buffer pool manager could be different sizes and you have to be able to handle that.
Nó chỉ xuất hiện trong các hệ thống học thuật vì nó đòi hỏi quản lý bộ nhớ nhiều hơn, vì lúc này các frame trong bộ quản lý buffer pool có thể có kích thước khác nhau và bạn phải xử lý được điều đó.
You're basically re-implementing malloc in your database system, which may not be a good idea. A cheap out would be just padding, so you know the max size of any given key.
Về cơ bản bạn đang cài đặt lại malloc trong hệ quản trị cơ sở dữ liệu của mình, và đó có thể không phải là ý hay. Một cách làm đơn giản là độn thêm (padding), vì bạn biết kích thước tối đa của một khóa bất kỳ.
It's going to be 32 characters, so no matter whether it's 32 characters or something less, you just pad it out with a bunch of zeros at the end so that things always nicely fit.
Giả sử là 32 ký tự, thì dù khóa dài đúng 32 ký tự hay ngắn hơn, bạn cứ độn thêm một loạt số không ở cuối để mọi thứ luôn vừa khít gọn gàng.
The implementation that everyone usually does is that you just have a...
Cách cài đặt mà mọi người thường dùng là bạn chỉ cần có một...
The same way we have slotted pages, where you could take a page and sort of the data's growing from the end to the beginning, you can do the same thing for your variable keys.
Giống như cách chúng ta có các trang có khe (slotted page), trong đó bạn lấy một trang và dữ liệu phát triển từ cuối về đầu, bạn có thể làm điều tương tự cho các khóa có độ dài thay đổi.
Then now you have an offset array to say, for a given key, here's the offset within my page to find the actual key that I want.
Khi đó bạn có một mảng offset để cho biết, với một khóa nhất định, đây là offset trong trang của tôi để tìm đúng khóa mà tôi muốn.
So the last one is usually what people do. And then if you have really, really large keys that don't fit, then you just have... You overflow horizontally, and that's okay. All right.
Vậy cách cuối cùng là cách mọi người thường làm. Và nếu bạn có những khóa thật sự rất lớn không vừa, thì bạn chỉ cần... Bạn tràn sang bên cạnh theo chiều ngang, và như vậy là ổn. Được rồi.
How do you find the data within a node? So the first obvious thing to do is just do linear search.
Làm thế nào để tìm dữ liệu bên trong một nút? Điều hiển nhiên đầu tiên cần làm là tìm kiếm tuyến tính.
So I want to find key eight. I got to find it in my array. I just start from the beginning, scan across until I find it, and I'm done.
Giả sử tôi muốn tìm khóa tám. Tôi phải tìm nó trong mảng của mình. Tôi chỉ việc bắt đầu từ đầu, quét qua cho đến khi tìm thấy, là xong.
Again, it's not the full table, or not the full data set, so this is okay. The number of keys we have within a node is not gonna be massively large.
Một lần nữa, đây không phải là toàn bộ bảng hay toàn bộ tập dữ liệu, nên cách này vẫn ổn. Số khóa trong một nút sẽ không quá lớn.
So yeah, it's linear scan, but it's not too bad because it's in memory.
Vậy nên đúng là quét tuyến tính, nhưng không tệ lắm vì nó nằm trong bộ nhớ.
One optimization you can do, if you have certain data types that are fixed size, you can use SIMD to do vectorized operations. Who here has taken 418? All right. Was that taken right now?
Một cách tối ưu bạn có thể làm, nếu có một số kiểu dữ liệu có kích thước cố định, là dùng SIMD để thực hiện các phép toán vectơ hóa. Ở đây ai đã học 418 rồi? Được rồi. Có phải học ngay bây giờ không?
Have you covered SIMD yet? You're right. SIMD basically means single instruction, multiple data.
Các bạn đã học SIMD chưa? Đúng rồi. SIMD về cơ bản có nghĩa là một lệnh, nhiều dữ liệu.
So think of like, it's a single CPU instruction that allows you to do some operation on multiple data items at the same time.
Hãy hình dung đó là một lệnh CPU duy nhất cho phép bạn thực hiện một phép toán trên nhiều phần tử dữ liệu cùng lúc.
So SISD is what you normally think about, like one single instruction, single data, like one plus one equals two.
Còn SISD là cái bạn thường nghĩ tới, tức là một lệnh, một dữ liệu, như một cộng một bằng hai.
Like you take the register for one, the register for the other one, you add them together, single instruction, and it produces one output.
Bạn lấy thanh ghi của số này, thanh ghi của số kia, cộng chúng lại, một lệnh duy nhất, và nó cho ra một kết quả.
SIMD allows you to take a single instruction and take a vector of data and do some operation on it and produce a vectorized output.
SIMD cho phép bạn lấy một lệnh duy nhất và một vectơ dữ liệu rồi thực hiện một phép toán trên đó và tạo ra một đầu ra dạng vectơ.
So to do something like this, so say I have a, you can use a 128-bit SIMD instruction. This is Intel Intrinsics or x86 Intrinsics.
Để làm một việc như thế này, giả sử tôi có một, bạn có thể dùng một lệnh SIMD 128 bit. Đây là Intel Intrinsics hay x86 Intrinsics.
So I take the first four keys, four, five, and six, I can then build a vector of just the key I'm looking for, eight.
Tôi lấy bốn khóa đầu tiên, bốn, năm và sáu, rồi tôi có thể tạo một vectơ chỉ gồm khóa mà tôi đang tìm, là tám.
And then in a single instruction, I can do a comparison of the input vector with my target vector, and it'll produce a bitmap that says, here's all the tuples, or here's the offsets of the tuples that match.
Và sau đó chỉ trong một lệnh, tôi có thể so sánh vectơ đầu vào với vectơ đích của mình, và nó sẽ tạo ra một bitmap cho biết, đây là tất cả các tuple, hay đây là các offset của những tuple khớp.
In this case here, none of them matches, but it's a single instruction to do this comparison and produce the output.
Trong trường hợp này, không có cái nào khớp, nhưng chỉ cần một lệnh duy nhất để thực hiện phép so sánh này và tạo ra kết quả.
And there's other SIMD instructions that then do, you know, find all the ones to see whether I have a match or not.
Và còn có những lệnh SIMD khác để tìm xem tôi có khớp hay không.
In this case here, I don't have a match, so I just slide over, do the next SIMD instruction on this.
Trong trường hợp này, tôi không có kết quả khớp, nên tôi chỉ trượt sang, thực hiện lệnh SIMD tiếp theo trên đoạn này.
In this case here, I only have three keys instead of eight, sorry, instead of four. So I, you know, the last one's ignored.
Ở đây, tôi chỉ có ba khóa thay vì tám, xin lỗi, thay vì bốn. Nên khóa cuối cùng bị bỏ qua.
And now I find a match, I see a one, I know I find the thing I'm looking for.
Và bây giờ tôi tìm thấy kết quả khớp, tôi thấy số một, tôi biết mình đã tìm được thứ cần tìm.
So again, instead of having to do sequential one by one, I can do a small number of instructions to do this in parallel.
Vậy nên, thay vì phải duyệt tuần tự từng phần tử một, tôi có thể dùng một số ít lệnh để làm việc này song song.
x86 has this, ARM has this, RISC-V has their own, like a bunch of systems have vectorized instructions for this. But it only works if, you know, it doesn't work on strings.
x86 có cái này, ARM có, RISC-V có bản riêng của họ, nhiều hệ thống đều có các lệnh vector hóa cho việc này. Nhưng nó chỉ hoạt động khi... nó không hoạt động trên chuỗi.
If things are variable length, you know, you won't fix length values. Another obvious choice is to do binary search, because if everything's sorted, I just jump in the middle, look for key eight.
Nếu dữ liệu có độ dài thay đổi thì không được, bạn cần các giá trị có độ dài cố định. Một lựa chọn hiển nhiên khác là tìm kiếm nhị phân, vì nếu mọi thứ đã được sắp xếp, tôi chỉ cần nhảy vào giữa, tìm khóa tám.
I know key eight is greater than seven, so I want to look at the next side, binary search over here, and eventually land in the middle, right?
Tôi biết khóa tám lớn hơn bảy, nên tôi muốn xem phía bên kia, tìm kiếm nhị phân ở đây, và cuối cùng dừng lại ở giữa, đúng không?
That's pretty obvious. And the last one is rare. So no commercial system or real system actually does this: interpolation.
Cái đó khá hiển nhiên. Và cái cuối cùng thì hiếm gặp. Không có hệ thống thương mại hay hệ thống thực tế nào làm điều này: nội suy.
Where we just do some math and say, well, I know I have a densely packed array of keys with no gaps, like four, five, six, seven, eight, nine, ten.
Tức là ta chỉ cần tính toán một chút và nói rằng, tôi biết mình có một mảng khóa dày đặc, không có khoảng trống, như bốn, năm, sáu, bảy, tám, chín, mười.
And the key I'm looking for is key eight.
Và khóa tôi đang tìm là khóa tám.
So I can just do the simple math and say, well, if key eight's going to exist, then if I just take the min value, the max value, jump to my offset, then I know it's going to be here.
Vậy tôi chỉ cần tính đơn giản, nếu khóa tám tồn tại, thì lấy giá trị nhỏ nhất, giá trị lớn nhất, nhảy tới offset của mình, và tôi biết nó sẽ nằm ở đây.
All right? It's not, if you land on something that's not eight, then you know it doesn't exist.
Được chứ? Nếu bạn rơi vào chỗ không phải tám, thì bạn biết nó không tồn tại.
If you can't, the question is, what if the array is sparse, not dense, it's not packed, you can't do this. That's what I'm saying.
Còn nếu không thể, câu hỏi là nếu mảng thưa, không dày đặc, không được nén chặt thì sao, bạn không thể làm vậy. Đó là điều tôi muốn nói.
It's a huge win if you could do this, but you can only do it in rare cases.
Sẽ lợi rất lớn nếu làm được, nhưng bạn chỉ làm được trong những trường hợp hiếm.
All right, three minutes left. Let me get through, I'll get through four of these. All right, again, it's a data structure from the 1970s.
Được rồi, còn ba phút. Để tôi lướt qua, tôi sẽ làm xong bốn cái này. Được rồi, một lần nữa, đây là cấu trúc dữ liệu từ những năm 1970.
Look at all the crazy you can do with this and make these things actually work. And this is what real systems are actually doing.
Hãy xem những thứ điên rồ mà bạn có thể làm với nó để khiến chúng thực sự hoạt động. Và đây là những gì các hệ thống thực tế đang làm.
All right, first one is pointer swizzling. This one is super common. I don't know why it's called swizzling. I didn't make the name up. It's the 80s.
Được rồi, cái đầu tiên là pointer swizzling. Cái này cực kỳ phổ biến. Tôi không biết vì sao nó gọi là swizzling. Tôi không đặt ra cái tên đó. Đó là thập niên 80.
I think it's a reference, but I wasn't there, so I don't know. All right, so when we do lookups, when we follow pointers in our B+tree, what are we doing, right?
Tôi nghĩ nó là một ám chỉ nào đó, nhưng tôi không có mặt ở đó nên không biết. Được rồi, khi chúng ta thực hiện tra cứu, khi đi theo các con trỏ trong B+tree, chúng ta đang làm gì nhỉ?
We're not actually storing memory pointers, we're storing page numbers.
Thực ra ta không lưu con trỏ bộ nhớ, mà lưu số trang.
So if I want a traversal, find key greater than three, the first thing I gotta do is look at my key, my root node, find, you know, it says six.
Vậy nếu tôi muốn duyệt, tìm khóa lớn hơn ba, việc đầu tiên tôi phải làm là xem khóa của mình, nút gốc, thấy, bạn biết đấy, nó ghi là sáu.
And I know I wanna go down to this side. Okay, well, how do I get down to that leaf node? Well, I'm gonna have a page number in my root node.
Và tôi biết mình muốn đi xuống nhánh bên này. Được rồi, vậy làm sao để xuống được nút lá đó? Thì trong nút gốc của tôi sẽ có một số trang.
It tells me how to go down there.
Nó cho tôi biết cách đi xuống đó.
So to get that page, I gotta go to my buffer pool and say, hey, go give me page two, give me back the pointer in memory for the frame that has that data.
Vậy để lấy trang đó, tôi phải đến buffer pool và nói: này, đưa cho tôi trang hai, trả lại cho tôi con trỏ trong bộ nhớ của frame chứa dữ liệu đó.
Okay. Once I get that, then I can do the traversal. Now I gotta scan along the leaf nodes following the sibling pointers. Same thing. I wanna get page three. What do I gotta do?
Được rồi. Khi có nó, tôi mới thực hiện việc duyệt cây. Bây giờ tôi phải quét dọc các nút lá theo các con trỏ anh em (sibling pointer). Cũng vậy. Tôi muốn lấy trang ba. Tôi phải làm gì?
I gotta go to the buffer manager and say, "Hey, go give me page three," right?
Tôi phải đến buffer manager và nói: "Này, đưa cho tôi trang ba", đúng không?
But because now we know it's a hierarchical data structure, we can have some guarantees about the order in which things would get evicted if we're a bit careful about this.
Nhưng vì bây giờ ta biết đây là một cấu trúc dữ liệu phân cấp, nên ta có thể có một số đảm bảo về thứ tự các trang bị loại ra (evict) nếu ta cẩn thận một chút về việc này.
So instead of actually storing the page numbers in the pages, we actually store just the pointers to the actual data.
Vì vậy, thay vì lưu số trang trong các trang, thực ra ta chỉ lưu các con trỏ tới dữ liệu thực.
You gotta pin those pages, make sure they don't get swapped out and replaced with something else, right?
Bạn phải ghim (pin) các trang đó, để chắc chắn chúng không bị tráo ra ngoài và thay bằng thứ khác, đúng không?
But now when I have a swizzled pointer, I basically have a little region in my page where I can store the actual raw memory pointers, and I have to know that if it gets evicted to disk, I bring it back in, this pointer is not valid anymore.
Nhưng khi tôi có một con trỏ đã swizzle, về cơ bản tôi có một vùng nhỏ trong trang của mình để lưu các con trỏ bộ nhớ thô thực sự, và tôi phải biết rằng nếu nó bị loại ra đĩa, rồi tôi nạp lại, thì con trỏ này không còn hợp lệ nữa.
But now I can just look at my page and say, "Here's directly the location that I want," as I do my traversal. And you get a huge win if you do this.
Nhưng bây giờ tôi chỉ cần nhìn vào trang của mình và nói: "Đây là vị trí tôi muốn, ngay trực tiếp", khi tôi duyệt cây. Và bạn sẽ có lợi rất lớn nếu làm như vậy.
And the data structure provides this nice guarantee where we would say, we can know that, I can't, I don't wanna evict anything in a root node, an inner node, if one of its children nodes has been swizzled or is in memory.
Và cấu trúc dữ liệu này cung cấp một đảm bảo hay ho, đó là ta có thể nói rằng, ta có thể biết rằng, tôi không thể, tôi không muốn loại bỏ bất cứ thứ gì trong nút gốc, một nút trong, nếu một trong các nút con của nó đã được swizzle hoặc đang nằm trong bộ nhớ.
So this makes sure we have some guarantee about how we order things, to make sure that we don't end up with pointers that go to nowhere or pointers that go to a frame that no longer has the data we want.
Như vậy ta có một đảm bảo nào đó về thứ tự xử lý các trang, để chắc chắn rằng ta không kết thúc với những con trỏ trỏ tới hư không hoặc trỏ tới một frame không còn chứa dữ liệu mà ta muốn.
All right, the last one I wanna talk about is, well, I'll go two more. So it should be clear that modifying a B+tree when we have to do splits and merges is expensive.
Được rồi, phần cuối cùng tôi muốn nói là, à, tôi sẽ nói thêm hai phần nữa. Vậy hẳn là đã rõ rằng việc sửa đổi một B+tree khi phải thực hiện tách và gộp nút là tốn kém.
If it's inserts, we just keep inserting to one side, and if our node has space for it, that's fast, that's fine. Same with deletes, right?
Nếu là chèn, ta cứ chèn liên tục về một phía, và nếu nút còn chỗ thì nhanh, như vậy là ổn. Xóa cũng vậy, đúng không?
But the worst case scenario is that we do a delete or an insert, we gotta reorganize the entire tree to make sure that it's balanced, right?
Nhưng trường hợp xấu nhất là khi ta xóa hoặc chèn, ta phải tổ chức lại toàn bộ cây để đảm bảo nó cân bằng, đúng không?
So ideally, it'd be kind of nice if we can delay having to do these splits and merges, to accumulate a bunch of them and then do them in a batch, rather than having to treat them as single inserts and updates one at a time.
Vì vậy, lý tưởng nhất, sẽ khá tuyệt nếu ta có thể trì hoãn việc tách và gộp này, gom một loạt chúng lại rồi thực hiện theo lô, thay vì phải coi chúng là từng thao tác chèn và cập nhật riêng lẻ, lần lượt từng cái một.
So this is what's called a write-optimized tree. I think Wikipedia calls them the fractal trees. That was sort of like the brand name, like Kleenex is the brand name of face tissue, right?
Đây gọi là cây tối ưu cho ghi (write-optimized tree). Tôi nghĩ Wikipedia gọi chúng là fractal tree. Đó từng là tên thương hiệu, giống như Kleenex là tên thương hiệu của khăn giấy vậy, đúng không?
So fractal tree is the brand name. The generic name is also called a B-epsilon tree.
Vậy fractal tree là tên thương hiệu. Tên gọi chung của nó là B-epsilon tree.
And the basic idea here is that in the same way you saw in MySQL for compressed pages, they added a mod log in front of the page.
Ý tưởng cơ bản ở đây là giống như cách các bạn đã thấy trong MySQL với các trang nén, họ thêm một mod log vào phía trước trang.
We're gonna add a mod log in front of every single node.
Chúng ta sẽ thêm một mod log vào phía trước mỗi nút.
So now, anytime we wanna do an operation, we don't have to maybe traverse all the way down to the bottom of the tree.
Như vậy, mỗi khi muốn thực hiện một thao tác, ta có thể không cần duyệt hết xuống tận đáy của cây.
We just find the first spot we can put something in a mod log and put it in there. So I wanna insert seven, all right?
Ta chỉ cần tìm chỗ đầu tiên có thể đặt một thứ vào mod log và đặt nó vào đó. Giả sử tôi muốn chèn 7, được chứ?
So in a regular B+tree, I'd have to traverse all the way down and then insert it on this node here.
Với B+tree thông thường, tôi phải duyệt hết xuống dưới rồi chèn vào nút này ở đây.
Instead, what I'm gonna do, I'm gonna put an insert entry in my mod log.
Thay vào đó, tôi sẽ đặt một mục chèn vào mod log của mình.
It's like the mem table, more or less, or not the mem table, like how in the log structure storage, we were storing these log records.
Nó giống như mem table, ít nhiều là vậy, hoặc không phải mem table, mà giống như trong lưu trữ có cấu trúc log, chúng ta lưu các bản ghi log này.
Here's the changes I made without maybe actually applying them. So I'm gonna put the insert seven in my mod log. Now I'm gonna delete 10, same thing. And I put it in there, right?
Đây là những thay đổi tôi đã thực hiện mà có thể chưa thực sự áp dụng. Vậy tôi đặt thao tác chèn 7 vào mod log. Giờ tôi xóa 10, cũng tương tự. Và tôi đặt nó vào đó, đúng không?
So now if anybody comes along and wants to do a lookup on 10, when you do the traversal, you normally do it in a B+tree, but you check the mod log first.
Giờ nếu có ai đó đến và muốn tra cứu 10, khi duyệt cây, bình thường bạn làm như với B+tree, nhưng bạn kiểm tra mod log trước.
And if the mod log contains the thing you're actually looking for, the actual key that you want, then you know you can stop right there because you found what you want and you don't have to do traversal.
Và nếu mod log chứa thứ bạn thực sự đang tìm, tức là chính khóa mà bạn muốn, thì bạn biết có thể dừng ngay tại đó vì đã tìm thấy thứ cần và không phải duyệt tiếp.
So to find 10, I land in the first root node. I look in the mod log, I see delete 10.
Để tìm 10, tôi vào nút gốc đầu tiên. Tôi xem mod log, thấy delete 10.
Well, I know that at that point, the last thing that happened to key 10 was that it was deleted, because it's at the top of the tree.
Vậy tôi biết rằng lúc đó, việc cuối cùng xảy ra với khóa 10 là nó đã bị xóa, vì nó nằm ở trên cùng của cây.
So I can go ahead and stop my search because I know it's not there. Even though physically, it's still in the leaf node here. And I gotta be careful.
Nên tôi có thể dừng tìm kiếm vì biết nó không có ở đó. Dù về mặt vật lý, nó vẫn còn ở nút lá này. Và tôi phải cẩn thận.
And everybody scans along and tries to find it. There's actual bookkeeping I have to do. But in this case here, I don't have to propagate the changes immediately.
Và mọi người quét dọc qua và cố tìm nó. Có việc ghi chép quản lý thực sự mà tôi phải làm. Nhưng trong trường hợp này, tôi không phải lan truyền các thay đổi ngay lập tức.
So what you do, what happens is when the mod log does get full, like I want to do insert 40, now I don't have any more space in my mod log, my root node.
Vậy điều xảy ra là khi mod log đầy, ví dụ tôi muốn chèn 40, giờ tôi không còn chỗ trong mod log của nút gốc nữa.
So then I got to propagate the changes down. And then whether you just go one level down or all the way down, depends on the implementation.
Vậy tôi phải lan truyền các thay đổi xuống dưới. Còn việc chỉ xuống một mức hay xuống hết tận đáy thì tùy vào cách triển khai.
So this is kind of getting the benefit of the log-structured merge tree. But in the context of a B-tree, you're kind of blending the best of both worlds.
Như vậy là tận dụng được lợi ích của log-structured merge tree. Nhưng trong ngữ cảnh của B-tree, bạn kết hợp được những điều tốt nhất của cả hai.
This is very rare. I think the data structure was invented in the 90s. But very few systems actually implement this. There was a system called Tokutech. They got bought by Percona.
Cái này rất hiếm. Tôi nghĩ cấu trúc dữ liệu này được phát minh vào thập niên 90. Nhưng rất ít hệ thống thực sự triển khai nó. Có một hệ thống tên là Tokutech. Họ đã bị Percona mua lại.
They got the new professor, William Kuszmaul, in computer science. His dad was one of the inventors of that data structure, Even though he claimed not to be a database person.
Họ có một giáo sư mới, William Kuszmaul, ở khoa khoa học máy tính. Bố của anh ấy là một trong những người phát minh ra cấu trúc dữ liệu đó, mặc dù ông ấy nói mình không phải người làm về cơ sở dữ liệu.
The best implementation, probably, that was out for a while is this thing called SplinterDB from VMware. That, I think, has been discontinued because the guy left to go to Cornell.
Bản triển khai tốt nhất, có lẽ, từng xuất hiện một thời gian là thứ gọi là SplinterDB của VMware. Theo tôi, nó đã bị ngừng phát triển vì anh chàng đó chuyển sang Cornell.
But RelationalAI's and ChromoDB, out of China. RelationalAI's in the US, ChromoDB's in China. Those are the two systems that I know that are pushing this pretty hard, okay?
Nhưng còn RelationalAI và ChromoDB, đến từ Trung Quốc. RelationalAI ở Mỹ, còn ChromoDB ở Trung Quốc. Đó là hai hệ thống mà tôi biết đang thúc đẩy hướng này khá mạnh, được chứ?
All right, quick question. Yes, go for it. So why isn't this more popular? Because it's hard, right?
Được rồi, một câu hỏi nhanh. Vâng, em hỏi đi. Vậy tại sao nó không phổ biến hơn? Vì nó khó, đúng không?
Because you have to, like I said, by scanning along the leaf nodes, I got to know how to find blah, blah, blah, blah, okay? All right, guys, see you on Wednesday. Hit it.
Vì như tôi đã nói, khi quét dọc theo các nút lá, tôi phải biết cách tìm cái này cái kia, v.v., được chứ? Được rồi các bạn, hẹn gặp lại vào thứ Tư. Bắt đầu nhạc nào.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.