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ả.
A round of applause for DJ Cash. Again, thank you for being here. A lot to cover today. Have you heard from your friend? Fascinating. Yeah, he's doing good.
Xin một tràng pháo tay cho DJ Cash. Một lần nữa, cảm ơn các bạn đã có mặt. Hôm nay có rất nhiều nội dung. Các bạn có tin gì từ bạn của mình chưa? Thú vị đấy. Ừ, anh ấy vẫn ổn.
He's doing better? Okay. He picked up a charge, though. He picked up a charge in London? Yeah, he did. For what? I can't tell you that.
Anh ấy khá hơn rồi à? Được rồi. Nhưng anh ấy bị buộc tội rồi. Anh ấy bị buộc tội ở London à? Ừ, đúng vậy. Vì tội gì? Tôi không nói được.
Oh, man. All right. Well, that's his problem. It's in London. We can't help him here. All right, so let's jump into databases, because that's the most important thing in life.
Trời ơi. Được rồi. Thôi, đó là chuyện của anh ấy. Ở London mà. Chúng ta không giúp được anh ấy ở đây. Được rồi, vậy chúng ta vào cơ sở dữ liệu nhé, vì đó là điều quan trọng nhất trong cuộc sống.
So, again, this is just a reminder for everything for you guys is due. Project 1 is due coming up. Homework 3 will be out today, and that'll be due in a few weeks.
Một lần nữa, đây chỉ là lời nhắc về mọi thứ đến hạn của các bạn. Project 1 sắp đến hạn. Homework 3 sẽ được đăng hôm nay, và hạn nộp là vài tuần nữa.
And then the midterm exam, again, will be in class on October 8th, and it'll cover lecture 1 to lecture 11.
Còn kỳ thi giữa kỳ sẽ diễn ra trong lớp vào ngày 8 tháng 10, và bao gồm từ bài giảng 1 đến bài giảng 11.
Okay? And then we'll post the study guide this weekend or Monday next week. Okay? Any questions about any of this?
Được chứ? Chúng tôi sẽ đăng bản hướng dẫn ôn tập vào cuối tuần này hoặc thứ Hai tuần sau. Được chứ? Có câu hỏi nào về những điều này không?
Again, we have the special office hours this Saturday at 3 p.m. in Gates 5207. That's one of the lab rooms. Again, there'll be multiple TAs there.
Một lần nữa, chúng tôi có giờ hỗ trợ đặc biệt vào thứ Bảy này lúc 3 giờ chiều tại Gates 5207. Đó là một trong các phòng thực hành. Sẽ có nhiều trợ giảng ở đó.
We'll use OHQ. You can queue yourself up and come and ask questions. Okay?
Chúng ta sẽ dùng OHQ. Các bạn có thể xếp hàng rồi đến hỏi. Được chứ?
All right, so let's continue on our discussion and our journey about indexes and the data structures we're going to use to build these things inside of our system.
Được rồi, giờ hãy tiếp tục phần thảo luận và hành trình về các chỉ mục và các cấu trúc dữ liệu mà chúng ta sẽ dùng để xây dựng chúng bên trong hệ thống của mình.
Today's class, we want to talk about indexes and filters. We mentioned filters briefly early in the semester when we mentioned Bloom filters. We haven't described what they are yet.
Hôm nay, chúng ta sẽ nói về chỉ mục và bộ lọc. Chúng ta đã nhắc sơ qua về bộ lọc hồi đầu học kỳ khi nói đến Bloom filter. Chúng ta vẫn chưa mô tả chúng là gì.
But I just want to highlight the distinction between what a filter is and what an index is.
Nhưng tôi muốn nhấn mạnh sự khác biệt giữa bộ lọc và chỉ mục.
And we're going to need both, and sometimes you'll put a filter in your index to help sort of speed up certain operations.
Chúng ta sẽ cần cả hai, và đôi khi bạn sẽ đặt một bộ lọc vào trong chỉ mục để giúp tăng tốc một số thao tác nhất định.
So an index is going to be a data structure, like a hash table or a B+tree or the things we've talked about so far, that we're going to use as a way to find individual records that we want, or sets of records that we want, based on some attribute within the table, like a column in the table.
Chỉ mục là một cấu trúc dữ liệu, như bảng băm hay B+tree hay những thứ chúng ta đã nói đến từ đầu đến giờ, mà ta dùng để tìm từng bản ghi cần thiết, hoặc các tập bản ghi cần thiết, dựa trên một thuộc tính nào đó trong bảng, như một cột của bảng.
We want to be able to do a quick lookup to find all the users, or all the people with a cs.cmu.edu email address. We can use an index to go find that.
Chúng ta muốn tra cứu nhanh để tìm tất cả người dùng, hoặc tất cả những người có địa chỉ email cs.cmu.edu. Chúng ta có thể dùng chỉ mục để tìm chúng.
So it'll give us, for some key, it'll give us an exact location of where we can go find the data we want, or at least a starting point for the data that we want.
Với một khóa nào đó, nó sẽ cho ta vị trí chính xác để tìm dữ liệu mình muốn, hoặc ít nhất là điểm bắt đầu của dữ liệu đó.
A filter is going to be like an index, but instead of being able to tell us, "Does this thing exist and where does it exist in our tables?", a filter is going to be able to tell us just set membership.
Bộ lọc cũng giống như chỉ mục, nhưng thay vì cho ta biết "Thứ này có tồn tại không và nó nằm ở đâu trong các bảng của ta?", bộ lọc chỉ cho ta biết về quan hệ thuộc tập hợp.
Does this thing exist, yes or no? And it can't tell you where it is, it's just going to tell you that it does exist. Right?
Thứ này có tồn tại không, có hay không? Và nó không cho bạn biết nó ở đâu, chỉ cho biết là nó có tồn tại. Đúng không?
Now, the tricky thing is going to be when we look at Bloom filters, these will be what are called probabilistic data structures, where it will tell you that it's likely that the key you're looking for exists, but it may actually give you a false positive.
Phần khó là khi chúng ta xét Bloom filter, chúng là cái gọi là cấu trúc dữ liệu xác suất, trong đó nó sẽ cho bạn biết khả năng cao là khóa bạn đang tìm có tồn tại, nhưng thực tế nó có thể cho bạn một kết quả dương tính giả.
It may tell you actually it exists when it actually doesn't.
Nó có thể báo là khóa tồn tại trong khi thực ra không.
It'll guarantee no false negatives, so if it says it doesn't exist, it definitely does not exist, but it may give you false positives, and we'll see what that looks like.
Nó đảm bảo không có âm tính giả, nên nếu nó nói là không tồn tại thì chắc chắn là không tồn tại, nhưng nó có thể cho dương tính giả, và chúng ta sẽ xem điều đó trông như thế nào.
So I'm going to quickly describe what a Bloom filter is, and then we'll see how we can tackle this onto other data structures we've been going through. Okay?
Vì vậy tôi sẽ mô tả nhanh Bloom filter là gì, rồi chúng ta sẽ xem làm sao có thể áp dụng nó vào các cấu trúc dữ liệu khác mà chúng ta đã học. Được chứ?
So today we're going to do a smorgasbord of a bunch of other data structures we're going to want to use in our data system, and we'll start off with Bloom filters, And then we'll jump to skip lists, tries, inverted indexes, and vector indexes.
Hôm nay chúng ta sẽ đi qua một loạt đủ thứ cấu trúc dữ liệu khác mà chúng ta sẽ muốn dùng trong hệ thống dữ liệu của mình, và chúng ta sẽ bắt đầu với Bloom filter, Sau đó sẽ chuyển sang skip list, trie, inverted index và vector index.
Quick show of hands, who here has heard of a, know what a Bloom filter is? Less than 10%. Who here knows what a skip list is? Ah, about that same.
Giơ tay nhanh nào, ai ở đây đã nghe nói đến, biết Bloom filter là gì? Dưới 10%. Ai biết skip list là gì? À, cũng khoảng đó.
What about tries and radix trees? Yep, okay. Inverted indexes? Few. And then vector indexes, I'm assuming maybe HNSW, IVF Flat? Nobody.
Còn trie và radix tree? Vâng, được. Inverted index? Một vài người. Còn vector index, tôi đoán có thể là HNSW, IVF Flat? Không ai.
Perfect, all right.
Tuyệt, được rồi.
So we'll see as we go along in today's lecture as well that we're going to use some of these earlier data structures that were described as building blocks to make more complicated things, or we'll apply some of the ideas we've used in other parts of the database system, and we can use them to enhance these different data structures.
Như vậy, trong bài giảng hôm nay chúng ta cũng sẽ thấy rằng chúng ta sẽ dùng một số cấu trúc dữ liệu trước đó làm các khối xây dựng để tạo ra những thứ phức tạp hơn, hoặc áp dụng một số ý tưởng mà chúng ta đã dùng ở các phần khác của hệ quản trị cơ sở dữ liệu, và dùng chúng để cải tiến các cấu trúc dữ liệu khác nhau này.
All right, so let's start off with Bloom filters. These are super useful, super common.
Được rồi, chúng ta bắt đầu với Bloom filter. Chúng cực kỳ hữu ích và rất phổ biến.
They're pretty much used in almost every single database system, and it's a probabilistic data structure where it's going to be able to tell you whether a key exists in your set or whether it does not exist, right?
Gần như hệ quản trị cơ sở dữ liệu nào cũng dùng chúng, và đây là một cấu trúc dữ liệu xác suất, có thể cho bạn biết một khóa có tồn tại trong tập của bạn hay không, đúng không?
And the term probabilistic means that there'll be some bit of randomness to it, where it could tell you that something exists even though it doesn't, but it's guaranteed to never tell you something does not exist when it actually does.
Thuật ngữ xác suất nghĩa là có một chút ngẫu nhiên trong đó, nó có thể báo rằng một thứ tồn tại dù thực tế không, nhưng được đảm bảo là sẽ không bao giờ báo rằng một thứ không tồn tại trong khi thực ra có.
So it'll give you false positives, and you can tune it based on what the false positive rate you want it to be, depending on the size and the number of hash functions you're going to use, but again, you'll never get false negatives.
Vì vậy nó sẽ cho dương tính giả, và bạn có thể điều chỉnh theo tỉ lệ dương tính giả mà bạn muốn, tùy vào kích thước và số lượng hàm băm bạn sử dụng, nhưng một lần nữa, bạn sẽ không bao giờ gặp âm tính giả.
So Bloom filters are only going to be able to give you basically two operations. The API only has two things.
Bloom filter về cơ bản chỉ cung cấp hai thao tác. API chỉ có hai thứ.
You can insert a key, and you can do a lookup of a key. You can't delete a key.
Bạn có thể chèn một khóa và tra cứu một khóa. Bạn không thể xóa khóa.
We'll see how to handle that in a second with other data structures, but you can only do lookups, and you can only do inserts.
Lát nữa chúng ta sẽ xem cách xử lý điều đó bằng các cấu trúc dữ liệu khác, nhưng bạn chỉ có thể tra cứu và chỉ có thể chèn.
Basically, the way it's going to work is that there's going to be this bitmap, or bit vector, like the thing with one hot encoding, that we're going to use to keep track of whether a key hashes to some location in the bitmap.
Về cơ bản, cách nó hoạt động là có một bitmap, hay vectơ bit, giống thứ dùng trong one hot encoding, mà chúng ta dùng để theo dõi xem một khóa có băm đến một vị trí nào đó trong bitmap hay không.
And we can use multiple hash functions to land at different locations to ensure that... to change the false positive rate, or change the accuracy of the data structure.
Và chúng ta có thể dùng nhiều hàm băm để trỏ đến các vị trí khác nhau nhằm đảm bảo rằng... thay đổi tỉ lệ dương tính giả, tức là thay đổi độ chính xác của cấu trúc dữ liệu.
So this is going to be widely used for in-memory caches. We'll want to use this when we do joins.
Vì vậy nó được dùng rộng rãi cho các bộ nhớ đệm trong bộ nhớ. Chúng ta sẽ muốn dùng nó khi thực hiện phép join.
We can also put these things in our hash tables, put these things in our B+trees. We can use these things everywhere because they're really compact.
Chúng ta cũng có thể đặt chúng vào các bảng băm, vào các cây B+tree. Chúng ta có thể dùng chúng ở mọi nơi vì chúng thực sự rất gọn nhẹ.
So here's a basic Bloom filter that has eight bits, right? And initially, when I first start the data structure, they're all set to zero, right?
Đây là một Bloom filter cơ bản có tám bit, đúng không? Và ban đầu, khi mới khởi tạo cấu trúc dữ liệu, tất cả đều được đặt bằng không, đúng không?
So say I want to insert a key. I want to insert the RISM. So for this Bloom filter, I have eight bits. I'm going to use two hash functions, right?
Giả sử tôi muốn chèn một khóa. Tôi muốn chèn RISM. Vậy với Bloom filter này, tôi có tám bit. Tôi sẽ dùng hai hàm băm, đúng không?
You can calibrate how many hash functions you want. You can calibrate what size you want the bitmap to be. To make this work in PowerPoint, I'm doing two functions with eight bits.
Bạn có thể tùy chỉnh số hàm băm mà bạn muốn. Bạn có thể tùy chỉnh kích thước bitmap mà bạn muốn. Để minh họa được trong PowerPoint, tôi dùng hai hàm với tám bit.
So what I'm going to do is I'm going to hash it, these two hash functions.
Vậy tôi sẽ băm khóa đó bằng hai hàm băm này.
And again, it'll be the same algorithm, the same hash function algorithm, like murmur hash, city hash, whatever you want.
Và một lần nữa, đó sẽ là cùng một thuật toán, cùng một thuật toán hàm băm, như murmur hash, city hash, tùy bạn chọn.
Just I give it a different seed so that it permutes it in a different way for each invocation.
Chỉ là tôi cung cấp cho nó một seed khác nhau để nó hoán vị theo một cách khác nhau ở mỗi lần gọi.
So let's say that I get now two different hash values: two, two, two, four, four, four, four.
Giả sử bây giờ tôi nhận được hai giá trị băm khác nhau: hai, hai, hai, bốn, bốn, bốn, bốn.
And I'm going to modulo by the number of bits I have in my Bloom filter bit vector. I get six and four.
Và tôi sẽ lấy phần dư theo số bit trong vectơ bit của Bloom filter. Tôi được sáu và bốn.
So now I'm just going to jump into those different offsets and set those bits to one, Right? That's pretty cheap. That's fast to do. Let me insert the JISO.
Vậy bây giờ tôi chỉ việc nhảy tới các vị trí đó và đặt các bit đó bằng một, đúng không? Việc đó khá rẻ. Làm rất nhanh. Giờ tôi chèn JISO.
All right, same thing: hash it twice, modify the number of locations or spots I have in my bitmap.
Được rồi, làm tương tự: băm hai lần, lấy phần dư theo số vị trí tôi có trong bitmap.
And then that's going to point me into now two different locations, and I set those bits to one. So now when I do a lookup on RZA, do the same thing.
Và nó sẽ trỏ tôi tới hai vị trí khác nhau, và tôi đặt các bit đó bằng một. Giờ khi tôi tra cứu RZA, cũng làm như vậy.
We're going to hash it again, and I'm going to get those same bit locations.
Ta băm lại lần nữa, và tôi sẽ nhận được đúng những vị trí bit đó.
And then as long as whatever I'm pointing at, as long as all the bits are set to one, then I know the key is, you know, I'm going to say the key exists, right?
Và miễn là những vị trí mà tôi trỏ tới, miễn là tất cả các bit đều bằng một, thì tôi biết khóa đó, ừm, tôi sẽ nói là khóa đó tồn tại, đúng không?
And this is why we can't have false negatives, right?
Và đây là lý do ta không thể có âm tính giả, đúng không?
Because if one of those bits were zero, then I would have never been able to insert RZA, because when I hash it and put it in there, I set them to one.
Bởi vì nếu một trong các bit đó bằng không, thì tôi đã không bao giờ chèn được RZA, vì khi tôi băm và đưa nó vào, tôi đã đặt các bit đó bằng một.
All right, so this will always return true, and it'll be, in this case here, it's correct.
Được rồi, vậy nó sẽ luôn trả về true, và trong trường hợp này, kết quả là đúng.
If I do a lookup on Raycon and The Chef, right, same thing, I hash it twice, now I get five and three, right?
Nếu tôi tra cứu Raycon và The Chef, đúng không, cũng vậy, tôi băm hai lần, giờ được năm và ba, đúng không?
One of those bits is set to zero, so I know that this key was not inserted, so I set it to false.
Một trong các bit đó bằng không, nên tôi biết khóa này chưa được chèn, và tôi trả về false.
Now I look up ODB, rest in peace, same thing, hash it twice, get two different locations.
Giờ tôi tra cứu ODB, cầu mong anh yên nghỉ, cũng vậy, băm hai lần, được hai vị trí khác nhau.
I didn't insert ODB, but my two hash locations that I land on are both set to one, so in this case here, I'm gonna say true, right?
Tôi chưa chèn ODB, nhưng cả hai vị trí băm mà tôi rơi vào đều được đặt bằng một, nên trong trường hợp này, tôi sẽ nói là true, đúng không?
And this is an example of the false positive, right? Both locations are set to one that I'm looking up on, but I know I didn't insert this key.
Và đây là một ví dụ về dương tính giả, đúng không? Cả hai vị trí mà tôi tra cứu đều được đặt bằng một, nhưng tôi biết là tôi chưa chèn khóa này.
So now you can see why if I have more hash functions, I can have a higher guarantee of this thing producing a correct answer, but now if I have a really small bitmap, Then if I have a lot of hash functions, I may just be setting them all to one, and then it's basically useless.
Vậy giờ các bạn có thể thấy vì sao nếu tôi có nhiều hàm băm hơn, tôi có thể bảo đảm tốt hơn là cấu trúc này đưa ra câu trả lời đúng, nhưng giờ nếu tôi có một bitmap rất nhỏ, thì nếu có rất nhiều hàm băm, có thể tôi sẽ đặt tất cả chúng thành một, và khi đó về cơ bản nó vô dụng.
So there's a bit of a balance on how much you wanna, you know, the size and how much compute you wanna do, but we're talking maybe, you know, kilobytes.
Vì vậy cần cân bằng một chút xem bạn muốn bao nhiêu, ý tôi là kích thước và lượng tính toán bạn muốn bỏ ra, nhưng ở đây ta đang nói đến cỡ vài kilobyte thôi.
These things aren't that big relative to the size of large data sets. All right, you guys did the count-min sketch. That's another example for project zero.
Những thứ này không lớn so với kích thước của các tập dữ liệu lớn. Được rồi, các bạn đã làm count-min sketch. Đó là một ví dụ khác trong project zero.
That's another example of our probabilistic data structure where, in exchange for not having to store, you know, a giant list of all the possible keys I could have to keep count of everything, I allow myself to have some wrong answers with some, you know, some guarantee of that probability.
Đó là một ví dụ khác về cấu trúc dữ liệu xác suất, trong đó, để đổi lấy việc không phải lưu trữ một danh sách khổng lồ gồm mọi khóa có thể có để đếm mọi thứ, tôi chấp nhận có một số câu trả lời sai, với một mức bảo đảm nào đó về xác suất.
Pretty straightforward, right? And there's a bunch of optimizations you can do to make these things real fast, real efficient. For this class, again, we're not worried about cache line stuff in the CPU.
Khá đơn giản, đúng không? Và có một loạt tối ưu hóa bạn có thể làm để làm cho chúng rất nhanh, rất hiệu quả. Với lớp này, một lần nữa, ta không lo về chuyện cache line trong CPU.
We can ignore that. You understand the basic data structure. It's pretty small. It's pretty compact. It's pretty fast to do this lookup, right?
Ta có thể bỏ qua. Các bạn hiểu cấu trúc dữ liệu cơ bản. Nó khá nhỏ. Nó khá gọn. Tra cứu bằng nó khá nhanh, đúng không?
Much faster than doing a probe in a hash table if you have to scan through, because now I'm comparing hashes and comparing keys as I go along.
Nhanh hơn nhiều so với việc dò trong bảng băm nếu phải quét qua, vì khi đó tôi vừa so sánh giá trị băm vừa so sánh khóa trong lúc đi.
So when we talk about doing hash joins in a few weeks, some systems will build a Bloom filter in front of the hash table, so you probe the Bloom filter first.
Vì vậy, khi nói về hash join trong vài tuần nữa, một số hệ thống sẽ xây một Bloom filter đặt trước bảng băm, nên bạn dò Bloom filter trước.
If it comes back as negative, then you know it can't be in your hash table, so you don't probe the hash table.
Nếu kết quả trả về là âm tính, thì bạn biết khóa không thể có trong bảng băm, nên bạn không dò bảng băm.
If this comes back as positive, then you go probe the hash table and see whether it actually exists. Right? Sometimes it's called a Bloom join, a Bloom hash join. Basic idea.
Nếu kết quả trả về là dương tính, thì bạn đi dò bảng băm để xem nó có thật sự tồn tại không. Đúng không? Đôi khi nó được gọi là Bloom join, Bloom hash join. Ý tưởng cơ bản là vậy.
Again, this is a useful data structure we can use in a bunch of different locations. Other filters we may want to consider also is a counting Bloom filter.
Một lần nữa, đây là cấu trúc dữ liệu hữu ích mà ta có thể dùng ở nhiều chỗ khác nhau. Một bộ lọc khác mà ta cũng có thể cân nhắc là counting Bloom filter.
For this one, you basically have multiple levels of bitmaps, and this allows you then to also do deletes. You sort of stage things out.
Với loại này, về cơ bản bạn có nhiều tầng bitmap, và điều này cho phép bạn thực hiện cả thao tác xóa. Bạn chia các thứ ra thành từng tầng.
And instead of storing single bits, I can store actually the count, right? So I know if I decrement the count to zero, I know I've removed something.
Và thay vì lưu từng bit đơn, tôi có thể lưu hẳn giá trị đếm, đúng không? Nên nếu tôi giảm bộ đếm xuống không, tôi biết là mình đã xóa một thứ.
But I still have the guarantee where I can have false positives but not false negatives. Yes? This question is, how do you update a Bloom filter if you delete a key?
Nhưng tôi vẫn có bảo đảm là có thể có dương tính giả nhưng không có âm tính giả. Bạn có câu hỏi? Câu hỏi là: làm sao cập nhật Bloom filter nếu xóa một khóa?
You can't. You can't. Right? Because again, if I delete, going back here, if I delete, who hashed to my, RZA hashed to what, three? Right? Or four. So if I, or six.
Không được. Không thể. Đúng không? Vì như tôi nói, quay lại chỗ này, nếu tôi xóa, RZA băm vào đâu nhỉ, ba? Đúng không? Hoặc bốn. Vậy nếu tôi, hoặc sáu.
I had to take the six and then one of these guys hashed to it, right? Or maybe I didn't see that.
Tôi phải lấy vị trí sáu và rồi một trong mấy khóa kia cũng băm vào đó, đúng không? Hoặc có thể tôi không thấy điều đó.
But anyway, if I delete one of these hashes or one of these bits for one key, then I don't know what are the keys I have in here because this is at bits.
Nhưng dù sao, nếu tôi xóa một trong các giá trị băm này, hay một trong các bit này của một khóa, thì tôi sẽ không biết mình đang có những khóa nào ở đây, vì đây chỉ là các bit.
So I may have ended up removing a key, removing a bit from a key that should be in there, and now I'm getting false negatives.
Vậy nên tôi có thể đã xóa mất một khóa, xóa một bit của một khóa lẽ ra phải có ở đó, và giờ tôi sẽ gặp các âm tính giả (false negative).
This question is, the false positive rate will increase when? Sorry?
Câu hỏi này là, tỉ lệ dương tính giả sẽ tăng khi nào? Xin lỗi, bạn nói gì?
You don't delete keys with ease. You just don't. The way, you want to delete keys, you want to use a counting Bloom filter, where instead of storing a bit, you store a count.
Bạn không xóa khóa một cách dễ dàng được. Đơn giản là không. Cách làm, nếu muốn xóa khóa, là dùng counting Bloom filter, trong đó thay vì lưu một bit, bạn lưu một bộ đếm.
And that solves that problem. There's another version of this called the Cuckoo filter.
Và như vậy là giải quyết được vấn đề đó. Còn có một phiên bản khác gọi là Cuckoo filter.
And the basic idea is it's kind of like the Cuckoo hash table, but instead of storing the entire key, you just store a small representation called a fingerprint of the key.
Ý tưởng cơ bản là nó hơi giống bảng băm Cuckoo, nhưng thay vì lưu toàn bộ khóa, bạn chỉ lưu một biểu diễn nhỏ của khóa, gọi là dấu vân tay (fingerprint).
And then that guarantees that if I remove it, the fingerprint gets removed and I still have the guarantee that I can have false positives but not false negatives.
Và điều đó đảm bảo rằng nếu tôi xóa nó, thì dấu vân tay bị xóa đi và tôi vẫn có được đảm bảo là có thể có dương tính giả nhưng không có âm tính giả.
And the last one is called the Thin Ring filter.
Và loại cuối cùng gọi là SuRF filter.
We'll see this in a second when we talk about tries, but this is basically a compact version of a radix tree where not only can I do set membership queries, but I can do range membership queries.
Chúng ta sẽ thấy nó ngay sau đây khi nói về trie, nhưng về cơ bản đây là một phiên bản nén của cây radix mà trong đó tôi không chỉ truy vấn được tư cách thành viên của tập hợp, mà còn truy vấn được tư cách thành viên theo khoảng.
Like, does this key exist within some range of values? Whereas all these other ones cannot do that. So, the bottom two here were invented here at CMU.
Ví dụ, khóa này có tồn tại trong một khoảng giá trị nào đó không? Trong khi tất cả các loại khác không làm được điều đó. Vậy hai loại ở dưới này được phát minh ngay tại CMU.
Cuckoo filter was created by Dave Anderson and his students in the computer science department, and then the SuRF filter, or SuRF, that was also created by a student that I co-advised with Dave Anderson, who's now a faculty at Tsinghua.
Cuckoo filter do Dave Anderson và các sinh viên của ông ở khoa khoa học máy tính tạo ra, còn SuRF filter, hay SuRF, cũng do một sinh viên mà tôi đồng hướng dẫn cùng Dave Anderson tạo ra, hiện là giảng viên ở Đại học Thanh Hoa.
It's another cool data structure. And actually in Redis you can actually explicitly ask for a Cuckoo filter, and they have their own built-in type for this.
Đó cũng là một cấu trúc dữ liệu thú vị. Và thực ra trong Redis bạn có thể yêu cầu tường minh một Cuckoo filter, và họ có kiểu dữ liệu tích hợp sẵn riêng cho nó.
Again, it gives you that same guarantees you want for actually a value you can store.
Một lần nữa, nó cho bạn cùng những đảm bảo mà bạn muốn đối với một giá trị bạn có thể lưu.
The question is, what's the difference between a counting Bloom filter and a count-min sketch? A count-min sketch is giving you approximate cardinality. Like, for a given key, how many times have I seen it?
Câu hỏi là, counting Bloom filter khác gì với count-min sketch? Count-min sketch cho bạn lực lượng (cardinality) xấp xỉ. Ví dụ, với một khóa cho trước, tôi đã thấy nó bao nhiêu lần?
Counting Bloom filter just says, like, does this key exist? But then if I do multiple keys, I can delete it. Counting Bloom filter won't handle deletes.
Còn counting Bloom filter chỉ cho biết khóa này có tồn tại không. Nhưng nếu tôi có nhiều khóa, tôi có thể xóa nó. Counting Bloom filter sẽ không xử lý được việc xóa.
It won't tell you the exact number of times you've seen a key.
Nó sẽ không cho bạn biết chính xác số lần bạn đã thấy một khóa.
You can do the same thing with a count-min sketch. Count-min sketch, again, it's meant to track cardinality. This is just trying to say, does the key exist?
Bạn có thể làm điều tương tự với count-min sketch. Count-min sketch, một lần nữa, được dùng để theo dõi lực lượng. Còn cái này chỉ cố cho biết khóa có tồn tại không.
Count-min sketch can do more than this than counting Bloom filter.
Count-min sketch làm được nhiều hơn counting Bloom filter.
So Bloom filter, again, that's the most important filter you need to know about. It's used everywhere.
Vậy Bloom filter, một lần nữa, là loại filter quan trọng nhất bạn cần biết. Nó được dùng ở khắp nơi.
These other ones I just talked about, they're used, but not as common as Bloom filter, because they're not as fast as a Bloom filter. All right.
Những loại khác tôi vừa nói thì được dùng, nhưng không phổ biến bằng Bloom filter, vì chúng không nhanh bằng Bloom filter. Được rồi.
So last class, when we talked about the B+tree, switching over now to index data structures, we talked about how the leaf nodes are essentially a sorted linked list.
Vậy ở buổi trước, khi nói về B+tree, giờ chuyển sang các cấu trúc dữ liệu chỉ mục, chúng ta đã nói rằng các nút lá về cơ bản là một danh sách liên kết đã được sắp xếp.
And then all the Inner nodes and the root nodes above it, with those guide post keys, discriminator keys, they're basically allowing you to jump into the linked list to find the data that you want more quickly.
Còn tất cả các nút trong và nút gốc phía trên nó, với các khóa dẫn đường, khóa phân biệt đó, về cơ bản giúp bạn nhảy vào danh sách liên kết để tìm dữ liệu mình muốn nhanh hơn.
All right. So if now we want to do, you know, if we just use a linked list, we end up with O(N) searches on average case. Right?
Được rồi. Giờ nếu chúng ta muốn làm, nếu chỉ dùng một danh sách liên kết, thì tìm kiếm sẽ mất O(N) trong trường hợp trung bình. Đúng không?
Because any single time we have to look for something, we may have to scan the entire linked list to find the thing we want.
Vì mỗi lần cần tìm một thứ gì đó, ta có thể phải quét toàn bộ danh sách liên kết để tìm thứ mình muốn.
We're not even talking about how to maintain it, but it's basically the same. All right. So a simple linked list would be sort of like this. Right?
Chúng ta còn chưa nói đến việc duy trì nó, nhưng về cơ bản cũng tương tự. Được rồi. Một danh sách liên kết đơn giản sẽ trông thế này. Đúng không?
And just key followed by a pointer to the next key. All right.
Chỉ là một khóa theo sau là con trỏ tới khóa kế tiếp. Được rồi.
And so if we want to make this go faster, we can do what the B+tree did, which was, as things get inserted, right, you start keeping track of the guide post as you go down, just to figure out when you want to go left or right to narrow down where you want to jump.
Và nếu muốn nó chạy nhanh hơn, ta có thể làm như B+tree, tức là khi các phần tử được chèn vào, bạn bắt đầu theo dõi các khóa dẫn đường trên đường đi xuống, chỉ để xác định khi nào nên đi sang trái hay sang phải để thu hẹp vị trí cần nhảy tới.
But a really more sort of simple, more simple approach would be, let's just have every other key also maintain a pointer that allows it to jump over the next key.
Nhưng một cách đơn giản hơn nhiều là, cứ để cách một khóa lại có thêm một con trỏ cho phép nhảy qua khóa kế tiếp.
Or jump over by one.
Hay nhảy qua một khóa.
So if we land on key one, if you know we got to get to some later point, we can just follow the key, follow the pointer at the top to jump over key two to get to key three.
Nên nếu ta đáp xuống khóa một, và cần đến một vị trí phía sau, ta chỉ cần đi theo khóa, đi theo con trỏ ở phía trên để nhảy qua khóa hai tới khóa ba.
And so forth. And we keep doing this to now also then jump over larger segments. All right.
Cứ thế tiếp tục. Và ta làm vậy để nhảy qua những đoạn dài hơn nữa. Được rồi.
So this, again, this is going to smell a lot like the B+tree, what we're doing here, but instead of having the keys being sort of added incrementally and then building things out, in a skip list we're basically going to flip a coin and decide when we want to have these little sort of skip pointers.
Như vậy, điều này sẽ khá giống B+tree, những gì ta đang làm ở đây, nhưng thay vì các khóa được thêm dần dần rồi xây dựng cấu trúc, trong skip list ta về cơ bản sẽ tung đồng xu để quyết định khi nào muốn có những con trỏ nhảy nhỏ này.
All right.
Được rồi.
So you can think of a skip list as just a multi-level linked list where you just add these extra pointers that allow you to skip over nodes to jump to farther locations into the list.
Bạn có thể xem skip list chỉ là một danh sách liên kết nhiều tầng mà bạn thêm các con trỏ phụ cho phép bỏ qua các nút để nhảy tới những vị trí xa hơn trong danh sách.
The way it works is it's a probabilistic data structure in that, not that you'll get false negatives or false positives, but more like the construction of the data structure is based on some randomness.
Cách hoạt động của nó là một cấu trúc dữ liệu xác suất, theo nghĩa là không phải bạn sẽ gặp âm tính giả hay dương tính giả, mà là việc xây dựng cấu trúc dữ liệu dựa trên yếu tố ngẫu nhiên.
So the way to think about it is at the bottom level of the list we're going to have all the keys, and then in the next level above it we're going to have about half the keys as the one below it.
Cách nghĩ về nó là ở tầng dưới cùng của danh sách ta sẽ có tất cả các khóa, và ở tầng kế tiếp phía trên ta sẽ có khoảng một nửa số khóa của tầng bên dưới.
And then at the next level above that I'll have half the keys below that.
Rồi ở tầng tiếp theo phía trên đó, tôi sẽ có một nửa số khóa của tầng bên dưới.
And so now when we insert something, we're basically going to flip a coin and decide for any key we're inserting what levels do we need to keep those skip pointers for.
Và bây giờ khi chèn một thứ gì đó, về cơ bản chúng ta sẽ tung đồng xu và quyết định, với mỗi khóa đang được chèn, cần giữ các con trỏ nhảy cho khóa đó ở những tầng nào.
And so you'll get approximate log n, right? Where the B+tree, if it was balanced, it guarantees to be log n. In this case here, on average it's approximate log n.
Và như vậy bạn sẽ có xấp xỉ log n, đúng không? Trong khi B+tree, nếu được cân bằng, thì đảm bảo là log n. Còn ở đây, trung bình nó xấp xỉ log n.
It usually works out to be just fine. So the skip lists are from the 1990s, B+trees are from the 1970s.
Thường thì như vậy là hoàn toàn ổn. Skip list có từ những năm 1990, còn B+tree có từ những năm 1970.
If you squint at them, they basically look the same. We'll see in a second. But these are typically used for in-memory data structures or in-memory indexes.
Nếu nhìn lướt qua thì về cơ bản chúng trông giống nhau. Lát nữa chúng ta sẽ thấy. Nhưng chúng thường được dùng cho các cấu trúc dữ liệu hay chỉ mục trong bộ nhớ.
Remember we talked about the mem table or log-structured merge trees, there was like this in-memory piece. Oftentimes in a lot of systems that's going to be using a skip list.
Nhớ là chúng ta đã nói về mem table hay log-structured merge tree, trong đó có một phần nằm trong bộ nhớ như vậy. Rất thường thì trong nhiều hệ thống, phần đó sẽ dùng skip list.
There are very few systems that I'm aware of that use skip lists for on disk, just because there's a lot more movement that you would have than a B+tree for moving things around.
Tôi biết rất ít hệ thống dùng skip list trên đĩa, chỉ vì sẽ có nhiều việc phải di chuyển dữ liệu hơn so với B+tree khi phải xê dịch các thứ.
In the back, yes. Question: is it only three levels? No, you can go, you can flip the coin and keep adding.
Ở phía sau, vâng. Câu hỏi: chỉ có ba tầng thôi à? Không, bạn có thể tung đồng xu và tiếp tục thêm tầng.
All right, so here's a basic one. Again, I'm showing three levels but it doesn't have to be.
Được rồi, đây là một ví dụ cơ bản. Một lần nữa, tôi vẽ ba tầng nhưng không nhất thiết phải vậy.
All right, so say we've already inserted a bunch of keys, and again I flip coins and decide how we want to put these.
Được rồi, giả sử chúng ta đã chèn một loạt khóa, và tôi lại tung đồng xu để quyết định đặt chúng như thế nào.
So on your right or left side we have all the levels. These are the entry points into the data structure.
Ở phía bên phải hay bên trái của bạn là tất cả các tầng. Đây là các điểm vào của cấu trúc dữ liệu.
And then on the right side, these have these markers to say this is the end of the linked list. All right, so if I see this then I know I've gone too far.
Còn ở phía bên phải, chúng có những dấu hiệu cho biết đây là cuối danh sách liên kết. Được rồi, nếu thấy dấu này thì tôi biết mình đã đi quá xa.
All right, the thing that I'm looking for doesn't exist.
Tức là thứ tôi đang tìm không tồn tại.
So the probability that a key is going to exist at any level will be the number of keys that I have divided by, you know, 2n from one, or divided by 2n from the one below me.
Vậy xác suất một khóa tồn tại ở một tầng bất kỳ sẽ là số khóa tôi có chia cho 2ⁿ tính từ tầng một, hay chia cho 2ⁿ tính từ tầng bên dưới tôi.
Right? So at the first level the probability that a key is going to exist is going to be one because it's all the keys.
Đúng không? Vậy ở tầng đầu tiên, xác suất để một khóa tồn tại là một, vì đó là tất cả các khóa.
At the next level it'll be n over 2, n over 4, and so forth going up. All right, skipping this.
Ở tầng tiếp theo sẽ là n/2, rồi n/4, và cứ thế đi lên. Được rồi, bỏ qua phần này.
All right, so when I want to insert a level, or insert a key, I'm basically going to flip a coin, and starting at the sort of the lowest level I'll flip a coin, and if it's equal to true then I know I want to, I'll insert the key there.
Được rồi, khi tôi muốn chèn một tầng, hay chèn một khóa, về cơ bản tôi sẽ tung đồng xu, và bắt đầu từ tầng thấp nhất, tôi tung đồng xu, nếu kết quả là true thì tôi biết mình muốn chèn khóa ở đó.
So the very beginning, again, so you have to always put the key at the bottom because that's the final location where every key has to exist.
Vậy ngay từ đầu, một lần nữa, bạn luôn phải đặt khóa ở tầng đáy vì đó là vị trí cuối cùng nơi mọi khóa đều phải tồn tại.
So this, when you don't flip a coin, you know you're always going to insert it. Right?
Vậy ở đây, khi không tung đồng xu, bạn biết là mình luôn chèn nó. Đúng không?
But then at the next level I'll say, all right, I'll flip a coin, and if it's true or heads, whatever, then I know I want to insert this and I go to the next one.
Nhưng rồi ở tầng tiếp theo tôi sẽ nói, được rồi, tôi tung đồng xu, và nếu là true hay mặt ngửa, sao cũng được, thì tôi biết mình muốn chèn khóa này và tôi đi tiếp lên tầng kế.
If it's false then I don't insert an entry at this level and I'm done.
Nếu là false thì tôi không chèn một mục vào tầng này và xong việc.
So in this case here, I flip a coin at the second level, it's true, so I know I want to insert a coin or insert the key.
Vậy trong trường hợp này, tôi tung đồng xu ở tầng thứ hai, kết quả là true, nên tôi biết là tôi muốn chèn một đồng xu, à nhầm, chèn khóa.
Then flip the next, go to the next level, flip a coin, it equals true, then I want to insert it again.
Sau đó lên tầng kế tiếp, tung đồng xu, kết quả bằng true, thì tôi lại muốn chèn nó một lần nữa.
I could go above that and decide, okay, now it's equal to false, so I don't want to put an entry in here.
Tôi có thể đi lên cao hơn nữa và thấy rằng, được rồi, giờ nó bằng false, nên tôi không muốn đặt một mục nào ở đây.
Right? So for this key here, we're going to put something in here. So we know it has to go in this location.
Đúng không? Vậy với khóa này, chúng ta sẽ đặt một thứ gì đó ở đây. Vậy chúng ta biết nó phải nằm ở vị trí này.
So the way it's going to work is I'm going to first insert the keys where I want them to be, but without connecting the rest of the data structure to them.
Cách nó hoạt động là trước tiên tôi sẽ chèn các khóa vào những vị trí tôi muốn, nhưng chưa nối phần còn lại của cấu trúc dữ liệu vào chúng.
So it's simplicity, so assume it's in memory. Right? So I'm going to create these, the key value records for these guys.
Cho đơn giản, hãy giả sử nó nằm trong bộ nhớ. Được chứ? Vậy tôi sẽ tạo các bản ghi khóa-giá trị cho những khóa này.
So the ones at the top, the values are just going to be pointers to the next level below me. Right? In skip list parlance, they would call these towers. Right?
Với những khóa ở phía trên, giá trị chỉ là các con trỏ trỏ tới tầng ngay bên dưới tôi. Đúng không? Theo thuật ngữ của skip list, người ta gọi chúng là các tháp (tower). Đúng không?
So at the root level I have the value, at the upper levels I'll have pointers to the level below me in my tower going down.
Vậy ở tầng gốc tôi có giá trị, còn ở các tầng trên tôi có con trỏ trỏ xuống tầng bên dưới trong tháp của mình.
Right? So then now I need to connect this to the rest of the data structure. Right?
Đúng không? Giờ tôi cần nối cái này với phần còn lại của cấu trúc dữ liệu. Đúng không?
So I'm going to have pointers coming out to whatever the next one, the next location should be in my data structure. Right?
Vậy tôi sẽ có các con trỏ đi ra, trỏ tới khóa kế tiếp, tức là vị trí kế tiếp trong cấu trúc dữ liệu của tôi. Đúng không?
In this case here, the bottom one, key five should go before key six, so it's going to point to key six.
Trong trường hợp này, ở tầng dưới cùng, khóa 5 nên nằm trước khóa 6, nên nó sẽ trỏ tới khóa 6.
The key five at the other levels, there isn't another key after that, so they're just going to point to the end markers, which is just infinity.
Khóa 5 ở các tầng khác thì không có khóa nào đứng sau nó, nên chúng chỉ trỏ tới các điểm đánh dấu kết thúc, chính là vô cực.
And then now, starting at the bottom, I'm going to then reconnect it into the rest of the data structure by changing this pointer here now to point to my new key.
Và bây giờ, bắt đầu từ dưới cùng, tôi sẽ nối nó trở lại vào phần còn lại của cấu trúc dữ liệu bằng cách đổi con trỏ này để nó trỏ tới khóa mới của tôi.
And at this point, the key is safely now in the data structure. So even if nobody follows those guide posts up above, I'll still be able to find the key, this key here.
Và tại thời điểm này, khóa đã nằm an toàn trong cấu trúc dữ liệu. Vậy dù không ai đi theo các cột mốc dẫn đường ở phía trên, tôi vẫn có thể tìm thấy khóa này, khóa ở đây.
But I'm going to then add those keys at the top, at the other levels, because then, again, they're guide posts to help me find what I want.
Nhưng sau đó tôi sẽ thêm các khóa ở phía trên, ở các tầng khác, vì như đã nói, chúng là các cột mốc dẫn đường giúp tôi tìm thứ mình muốn.
So then I do the same thing: go to the next level, change that pointer now to point to me; go to the next level, change that pointer now to point to me.
Vậy tôi làm tương tự: đi lên tầng kế tiếp, đổi con trỏ đó để nó trỏ tới tôi; đi lên tầng kế tiếp, đổi con trỏ đó để nó trỏ tới tôi.
Right? And now my key is fully integrated with all the towers. So now if I want to do a lookup, I want to find key three.
Đúng không? Và giờ khóa của tôi đã được tích hợp đầy đủ với tất cả các tháp. Bây giờ nếu tôi muốn tra cứu, tôi muốn tìm khóa 3.
So I start at the very top, and I'm going to look ahead on the pointer to what the key is pointing at in this top level. In this case here, it's five.
Tôi bắt đầu từ trên cùng, và tôi sẽ nhìn trước con trỏ xem khóa ở tầng trên cùng này đang trỏ tới cái gì. Trong trường hợp này, đó là 5.
But because we know that three is less than five, I don't want to follow this pointer. I want to go down a level.
Nhưng vì chúng ta biết 3 nhỏ hơn 5, tôi không muốn đi theo con trỏ này. Tôi muốn đi xuống một tầng.
Because this is basically saying key five is, that any value that comes after this, where key five is located at the top level, is going to be greater than or equal to five.
Vì về cơ bản điều này nói rằng khóa 5, rằng bất kỳ giá trị nào đứng sau cái này, tức là nơi khóa 5 nằm ở tầng trên cùng, sẽ lớn hơn hoặc bằng 5.
So if I'm looking for three, which is less than five, then I know I don't want to go to the right of it, I've got to go before it.
Vậy nếu tôi đang tìm 3, nhỏ hơn 5, thì tôi biết mình không muốn đi sang bên phải nó, mà phải đi về phía trước nó.
So then I go down to the next level, do the same thing. I compare key three with key two.
Rồi tôi đi xuống tầng tiếp theo và làm tương tự. Tôi so sánh key 3 với key 2.
Key three is greater than two, or three is greater than two, so I know I want to follow this pointer to jump to this location.
Key 3 lớn hơn 2, hay 3 lớn hơn 2, nên tôi biết mình muốn đi theo con trỏ này để nhảy tới vị trí này.
Then do the same thing: check the next node along this level.
Rồi lại làm tương tự: kiểm tra nút tiếp theo trên tầng này.
Key three is less than the key four, so I know the thing that I want has to be down and to the right of me, rather than going across to key four.
Key 3 nhỏ hơn key 4, nên tôi biết thứ tôi cần phải nằm ở dưới và bên phải tôi, thay vì đi ngang sang key 4.
So then I move down here and then scan along the leaf nodes as I would in any linked list, and then I'll find the thing that I want.
Vậy tôi đi xuống đây rồi quét dọc các nút lá như với bất kỳ danh sách liên kết nào, và rồi tôi sẽ tìm thấy thứ mình cần.
In the back, yes. Yes.
Bạn ở phía cuối, vâng. Vâng.
Yeah, his question is, going back here on these levels here, it's basically like the bucket array just tells me where to jump into, so I know how to jump to the starting point at each level.
Vâng, câu hỏi của bạn ấy là, quay lại các tầng ở đây, mảng bucket về cơ bản chỉ cho tôi biết nhảy vào đâu, để tôi biết cách nhảy tới điểm bắt đầu ở mỗi tầng.
Yeah. Yes. Yeah. So I'm not showing the lines going down; you would have them as well.
Vâng. Đúng vậy. Tôi không vẽ các đường đi xuống, nhưng thực tế chúng cũng có.
Okay. So let's quickly talk about how to handle deletes.
Được rồi. Giờ nói nhanh về cách xử lý thao tác xóa.
So again, without talking about multi-threading stuff yet, that'll be next week.
Một lần nữa, chưa nói đến chuyện đa luồng, để tuần sau.
The way it basically works is that every key is going to have a little marker to say, is this thing deleted, yes or no?
Cách hoạt động về cơ bản là mỗi key sẽ có một dấu nhỏ để cho biết, thứ này đã bị xóa hay chưa?
And then without me having to go physically remove it, because that's actually an expensive operation, because I got to go remove the towers, I got to go change one of the pointers, so I'll have sort of the thread that wants to delete the key just first mark this thing as being deleted, and then like compaction in log-structured merge trees, there'll be a separate background worker, background process, that comes along and cleans things up at a regular interval.
Và tôi không cần phải xóa nó đi về mặt vật lý, vì đó thực ra là một thao tác tốn kém, vì tôi phải xóa các tháp, phải đổi một số con trỏ, nên luồng muốn xóa key chỉ đánh dấu trước là nó đã bị xóa, và rồi giống như compaction trong log-structured merge tree, sẽ có một worker nền riêng, một tiến trình nền, chạy tới và dọn dẹp định kỳ.
So again, along all the leaf nodes, again, I'm going to have this byte value or boolean that says, is this thing deleted, yes or no?
Vậy, ở tất cả các nút lá, tôi sẽ có một giá trị byte hoặc boolean cho biết, thứ này đã bị xóa hay chưa?
So if I want to go ahead now and delete key 5, I'll do that traversal as I did before.
Giờ nếu tôi muốn xóa key 5, tôi sẽ duyệt như trước.
So I would run along the top level, see that I have key 5, and then go down and then set it to deleted as true.
Tôi chạy dọc tầng trên cùng, thấy có key 5, rồi đi xuống và đặt deleted thành true.
So now again, any other thread that comes along and wants to do a lookup on key 5, they may see this leaf node here, or this bottom node in the linked list, that it's been, you know, that it would find the actual key, but then it would check the bit and see That it's been marked as deleted, so nodes would just ignore it.
Giờ nếu có luồng khác chạy tới và muốn tra cứu key 5, nó có thể thấy nút lá này, hay nút dưới cùng trong danh sách liên kết, tức là nó sẽ tìm thấy chính key đó, nhưng rồi nó kiểm tra bit và thấy nó đã bị đánh dấu là đã xóa, nên các nút sẽ bỏ qua nó.
So now I want to go clean up the tower.
Giờ tôi muốn dọn dẹp cái tháp.
Basically, I'm going to do this in reverse, where I'm going to want to change the pointer at the top first and then work my way down.
Về cơ bản, tôi sẽ làm ngược lại, tức là tôi muốn đổi con trỏ ở trên cùng trước rồi mới đi dần xuống.
When we inserted it, we changed the pointers at the bottom and then worked our way up to it. This is the opposite.
Khi chèn nó vào, chúng ta thay đổi các con trỏ ở dưới cùng rồi đi dần lên trên. Còn đây thì ngược lại.
So again, I'll go over to the starting point at the levels, change that pointer, now instead of pointing to key 5, have it point to the end.
Vậy nên, tôi sẽ quay lại điểm bắt đầu ở các tầng, thay đổi con trỏ đó, giờ thay vì trỏ tới khóa 5, cho nó trỏ tới phần cuối.
And at this point here, anybody comes along after me won't be able to see key 5. Same thing, go to the next level, flip that pointer.
Và tới đây, ai đến sau tôi sẽ không thể thấy khóa 5 nữa. Tương tự, đi tới tầng tiếp theo, đổi con trỏ đó.
Then once I have that, change that pointer at the bottom.
Sau đó, khi đã xong, đổi con trỏ ở dưới cùng.
At this point here, assuming I'm single threaded for simplicity reasons, I know that there isn't another thread hanging out here that wants to follow something that goes nowhere.
Tới đây, giả sử vì cho đơn giản mà tôi chỉ chạy đơn luồng, thì tôi biết không có luồng nào khác đang loanh quanh ở đây muốn đi theo một thứ dẫn tới hư không.
There's some additional guarantees I can provide to make sure that nobody's actually reading this, then it's safe for me to go ahead and delete it, and I completely remove the key from the data structure.
Có thêm một số đảm bảo tôi có thể cung cấp để chắc chắn rằng không ai thực sự đang đọc nó, thì tôi có thể yên tâm xóa nó đi, và loại bỏ hoàn toàn khóa đó khỏi cấu trúc dữ liệu.
So I mean, skip lists are kind of cool. It's a nifty little thing.
Vậy skip list khá hay đấy. Là một thứ nhỏ gọn khéo léo.
Again, if you just think of it as sort of being rotated, it's like a B+tree, but I have, instead of these guide posts being determined on how I'm doing splits and merges, it's flipping a coin to decide where things are.
Một lần nữa, nếu bạn coi nó như được xoay đi, thì nó giống B+tree, nhưng thay vì các cột mốc dẫn đường này được xác định dựa trên cách tôi tách và gộp, thì ở đây là tung đồng xu để quyết định vị trí của chúng.
And again, there's no free lunch, it's still going to be a log n.
Và lại nữa, không có bữa trưa miễn phí, độ phức tạp vẫn là log n.
So the other thing I also point out is, in my example here, I showed a one-direction linked list, whereas in the B+tree we said we could have sibling pointers going in both directions.
Một điều nữa tôi cũng muốn nêu là, trong ví dụ này, tôi cho thấy một danh sách liên kết một chiều, trong khi ở B+tree chúng ta nói có thể có con trỏ anh em theo cả hai hướng.
So if you want to have pointers go in both directions, it kind of complicates things. It complicates some of the operations to make things thread safe.
Nên nếu bạn muốn con trỏ đi cả hai hướng, mọi thứ sẽ phức tạp hơn. Nó làm phức tạp một số thao tác để đảm bảo an toàn luồng.
If you have a single thread in it, no big deal.
Nếu chỉ có một luồng thì không sao.
Multi-threads makes a problem because you could have one guy come in one way, another guy come in another way, and you'll be able to handle that.
Đa luồng gây ra vấn đề vì có thể một luồng đi vào từ hướng này, luồng khác đi vào từ hướng khác, và bạn phải xử lý được điều đó.
Unlike B plus trees, skip lists don't require any rebalancing or splits or merges, because it's just removing towers.
Không như B+tree, skip list không cần cân bằng lại hay tách hoặc gộp, vì chỉ là gỡ bỏ các tháp.
Then when you remove a tower, when you delete a key, or when I insert a key, I'm adding new towers.
Khi bạn gỡ một tháp, tức là khi xóa một khóa, hoặc khi tôi chèn một khóa, tôi thêm các tháp mới.
It doesn't change the location or doesn't change the layout of the rest of the keys in the data structure. But again, I'm showing this on PowerPoint.
Nó không thay đổi vị trí hay bố cục của các khóa còn lại trong cấu trúc dữ liệu. Nhưng lại nữa, tôi đang minh họa việc này trên PowerPoint.
If it's in memory, no big deal, you could pack multiple keys in a chunk of memory.
Nếu ở trong bộ nhớ thì không sao, bạn có thể gói nhiều khóa vào một khối bộ nhớ.
But now if I am backed by disk pages, then you end up, you end up doing more IO than you would in a B plus tree, right?
Nhưng nếu giờ nó được lưu trên các trang đĩa, thì cuối cùng bạn phải thực hiện nhiều IO hơn so với B+tree, đúng không?
So again, you typically see these only for in-memory data structures.
Vì vậy, thường bạn chỉ thấy chúng dùng cho các cấu trúc dữ liệu trong bộ nhớ.
So the SingleStore people I talked about a few weeks ago, they were all in on the skip lists, and that's the main data structure they use for the row store.
Những người ở SingleStore mà tôi đã nói cách đây vài tuần đã dồn toàn lực vào skip list, và đó là cấu trúc dữ liệu chính họ dùng cho row store.
In some log-structured merge trees like RocksDB, the memtable is going to be a skip list. I think WiredTiger for the log-structured merge tree, it's a skip list.
Trong một số cây log-structured merge như RocksDB, memtable là một skip list. Tôi nghĩ WiredTiger, với cây log-structured merge, cũng dùng skip list.
So for in-memory stuff, it's often a really easy thing to implement, and a lot of systems choose to do that.
Vì vậy với các hệ thống lưu trữ trong bộ nhớ, đây thường là thứ rất dễ cài đặt, và rất nhiều hệ thống chọn cách đó.
Okay, so now another thing to point out also too with B plus trees is that the inner nodes are being used as, again, guideposts that tell us how to get to the bottom.
Được rồi, bây giờ một điều khác cũng cần lưu ý với B+tree là các nút trong được dùng như, một lần nữa, những cột mốc chỉ cho ta cách đi xuống tận dưới đáy.
Remember in the last class we talked about, and we said that I may end up deleting a key, well, it'll get removed from the leaf nodes.
Hãy nhớ trong buổi học trước chúng ta đã nói, rằng tôi có thể xóa một khóa, thì nó sẽ bị loại khỏi các nút lá.
But then I may keep it around as one of the guide posts because it's a good discriminator, and I don't want to rebalance things, right? Because I don't need to.
Nhưng sau đó tôi có thể vẫn giữ nó lại làm một cột mốc vì nó là một thứ phân biệt tốt, và tôi không muốn cân bằng lại cây, đúng không? Vì tôi không cần phải làm vậy.
And so if I'm traversing down the B+tree and I see a key in an inner node, I can't be guaranteed that the key actually exists, because I always got to get to the leaf node, all right?
Và nếu tôi đang duyệt xuống B+tree và thấy một khóa ở nút trong, tôi không thể chắc chắn rằng khóa đó thật sự tồn tại, vì tôi luôn phải đi đến nút lá, được chứ?
And so what'll happen is I always have to be able to traverse to the bottom of the tree in order to tell you whether a key exists or not in a B+tree.
Và do đó điều xảy ra là tôi luôn phải duyệt được xuống đáy của cây để cho bạn biết một khóa có tồn tại hay không trong B+tree.
In the case of the B epsilon tree we talked about in the last class, if I'm lucky and I land on the first node, I look in this mod log and I see the key I want has been deleted, I don't have to traverse the rest of the way.
Với trường hợp B epsilon tree mà chúng ta đã nói ở buổi trước, nếu tôi may mắn và đến được nút đầu tiên, tôi nhìn vào mod log này và thấy khóa tôi muốn đã bị xóa, thì tôi không cần duyệt tiếp phần còn lại.
But again, for large key spaces there's no guarantee to do that.
Nhưng một lần nữa, với không gian khóa lớn thì không có gì đảm bảo làm được vậy.
So an alternative to doing a sort of tree search in a B+tree, or in a skip list as well, is to do what's called a trie.
Vậy một giải pháp thay thế cho kiểu tìm kiếm trên cây trong B+tree, hoặc trong skip list, là dùng cái gọi là trie.
And the basic idea here is that instead of storing at every sort of level in the tree an entire key, I'm going to store a portion of the key, or a digit of it.
Và ý tưởng cơ bản ở đây là thay vì lưu toàn bộ khóa ở mỗi tầng của cây, tôi sẽ lưu một phần của khóa, hay một chữ số của nó.
And so now as I'm traversing the key, or as I'm traversing the tree, the path I'm taking down the tree can be used to then reconstruct the key that I'm looking for.
Và như vậy khi tôi duyệt khóa, hay khi tôi duyệt cây, đường đi tôi đi xuống cây có thể được dùng để dựng lại khóa mà tôi đang tìm.
So if I'm looking for a particular key and I don't see it in the first node, I don't see maybe the first character, the first bit that I want, in the first node, then I know it can't exist in the rest of the tree and I can stop right away.
Nên nếu tôi tìm một khóa cụ thể và không thấy nó ở nút đầu tiên, có thể tôi không thấy ký tự đầu tiên, bit đầu tiên mà tôi muốn, ở nút đầu tiên, thì tôi biết nó không thể tồn tại trong phần còn lại của cây và tôi có thể dừng ngay.
So tries are older. Tries are from like the late 1950s. It was invented by some French guy. Again, B+trees are 1970s, tries are like 1959, '58.
Trie ra đời sớm hơn. Trie có từ khoảng cuối những năm 1950. Nó được một người Pháp nào đó phát minh. Một lần nữa, B+tree là những năm 1970, còn trie khoảng 1959, 1958.
The term "trie" was actually invented by somebody here at CMU. I think he died last year, but he coined the term in the '60s. Yes, question?
Thuật ngữ "trie" thực ra do một người ở đây tại CMU đặt ra. Tôi nghĩ ông ấy mất năm ngoái, nhưng ông đã đặt ra thuật ngữ này vào những năm 60. Vâng, bạn có câu hỏi?
Is what if one of the keys is a subword of another key? Yes, yes, you just add it.
Thế nếu một khóa là từ con của một khóa khác thì sao? Vâng, vâng, bạn cứ thêm nó vào.
Oh, his question is how would you resolve it? We'll go through examples, but like you have H, A, T, and you would add, and then pointers coming out.
À, câu hỏi của bạn ấy là giải quyết việc đó thế nào? Chúng ta sẽ đi qua các ví dụ, nhưng ví dụ bạn có H, A, T, và bạn sẽ thêm vào, rồi các con trỏ đi ra.
Oh, how to resolve like where something's a subset of another key? You would have both a T to A and then T to E. Yes, yeah.
À, làm sao giải quyết trường hợp một thứ là tập con của khóa khác? Bạn sẽ có cả hai T tới A và rồi T tới E. Vâng, đúng vậy.
Yeah, so keys, he basically asked me like, how do I handle the case where a key is a subset of another key? How do I make, how do I know whether the keys exist?
Vâng, về các khóa, về cơ bản bạn ấy hỏi tôi là, tôi xử lý thế nào trường hợp một khóa là tập con của một khóa khác? Làm sao tôi biết các khóa có tồn tại hay không?
Because again, I'm going to be, I'm going to be using these tries for, for a given key, find the thing that I want.
Bởi vì, một lần nữa, tôi sẽ dùng các trie này để, với một khóa cho trước, tìm ra thứ mà tôi muốn.
Range scan is a bit more tricky because you have to bounce off and back, but we're ignoring that for now.
Range scan thì phức tạp hơn một chút vì phải đi qua đi lại, nhưng bây giờ chúng ta bỏ qua phần đó.
But the use case you're talking about, we handle this fine, because if I know for a hat it's H, A, T, I don't follow what are pointed down to the next, the next letters, the digits, I just stop.
Nhưng trường hợp bạn nói thì chúng ta xử lý ổn, vì nếu tôi biết với hat thì đó là H, A, T, tôi sẽ không đi theo các con trỏ xuống các chữ cái, các chữ số tiếp theo, tôi chỉ dừng lại.
If there's a pointer, I say I know there's something that's exactly this key. Yes, question? The question is how does this work for strings and ints? Give me a second.
Nếu có con trỏ, tôi biết là có một thứ khớp chính xác với khóa này. Vâng, bạn hỏi đi? Câu hỏi là điều này hoạt động thế nào với chuỗi và số nguyên? Cho tôi một chút.
Just fine, no problem, right? What is, what is a string? Assume it's ASCII. What is it?
Hoàn toàn ổn, không vấn đề gì, đúng không? Chuỗi là gì? Giả sử là ASCII. Nó là gì?
Yeah, if it's ASCII, they're always eight bytes, it's just an integer, so there's, yeah, there's no big deal. Other data types, I don't have slides for this, other data types are more tricky.
Vâng, nếu là ASCII thì luôn là tám byte, nó chỉ là một số nguyên, nên không có gì to tát cả. Các kiểu dữ liệu khác, tôi không có slide cho phần này, thì phức tạp hơn.
Like floats can be tricky because it depends on endianness as well. We'll ignore that; we're ignoring all that. Assume it's ASCII. It's ASCII, so 8-bit characters.
Ví dụ số thực dấu phẩy động có thể phức tạp vì còn phụ thuộc vào endianness. Chúng ta sẽ bỏ qua, bỏ qua hết. Giả sử là ASCII. Là ASCII, tức là các ký tự 8 bit.
Okay, so what's really cool about tries is that they don't require rebalancing.
Được rồi, điều thật sự hay ở trie là chúng không cần cân bằng lại.
Not always, but the other cool thing is that the data structure, like the layout of the actual nodes within our data structure, doesn't depend on the order in which you insert things or delete things.
Không phải lúc nào cũng vậy, nhưng điều hay khác là cấu trúc dữ liệu này, tức cách bố trí của các nút trong cấu trúc dữ liệu của chúng ta, không phụ thuộc vào thứ tự bạn chèn hay xóa các phần tử.
It just depends on the keys.
Nó chỉ phụ thuộc vào các khóa.
So no matter what order you insert the keys into your data structure, you're always going to end up with the same sort of layout, and this can then guarantee that any lookup is always going to be O(k) in time, where k is the length of the key that you're looking for.
Vì vậy dù bạn chèn các khóa vào cấu trúc dữ liệu theo thứ tự nào, bạn luôn thu được cùng một kiểu bố trí, và điều này đảm bảo mọi lần tra cứu luôn mất thời gian O(k), trong đó k là độ dài của khóa mà bạn đang tìm.
So if I'm looking for, you know, for hello, right, that has five characters.
Ví dụ nếu tôi tìm hello, chuỗi này có năm ký tự.
In my example here, I know I'm gonna have to look for at least five characters to find the thing, whether the thing exists or not, right?
Trong ví dụ của tôi ở đây, tôi biết mình sẽ phải xét ít nhất năm ký tự để tìm ra nó, dù nó có tồn tại hay không, đúng không?
And the way you traverse, every time you go down a level, you just look for the next character or digit that you want, and if it's not there, then no, it's not there.
Và cách duyệt là, mỗi lần đi xuống một mức, bạn chỉ tìm ký tự hoặc chữ số tiếp theo mà bạn muốn, và nếu nó không có ở đó thì không, nó không tồn tại.
If it is there, then you follow the pointer to find the thing you want.
Nếu có thì bạn đi theo con trỏ để tìm thứ bạn muốn.
So in the same way we define B+trees, it's sort of the m-way data structure, where m is the number of pointers coming out of it.
Tương tự cách chúng ta định nghĩa B+tree, là cấu trúc dữ liệu m-way, trong đó m là số con trỏ đi ra từ nó.
In a trie, you would say the span of the trie is the number of bits or digits we're going to represent in every level of the trie, right?
Với trie, bạn sẽ nói span của trie là số bit hoặc chữ số mà chúng ta biểu diễn ở mỗi mức của trie, đúng không?
And then if the digit exists in the corpus or the keys that we're trying to maintain in our data structure, then we have to have a pointer to the next level.
Và nếu chữ số đó tồn tại trong tập dữ liệu hoặc các khóa mà chúng ta muốn lưu trong cấu trúc dữ liệu, thì chúng ta phải có một con trỏ tới mức tiếp theo.
Otherwise we just say it's null; we don't want to represent it.
Nếu không thì ta để là null; ta không muốn biểu diễn nó.
And then the fan-out would be, at every node, how many things are coming out of it, and then that also then determines what the height of the physical tree is.
Và fan-out sẽ là, tại mỗi nút, có bao nhiêu thứ đi ra từ nó, và điều đó cũng quyết định chiều cao của cây vật lý.
So let's look at a really trivial example. What they were asking for, how would you represent integers in this? Let's say we want to insert three keys: 10, 25, and 31.
Vậy hãy xem một ví dụ thật đơn giản. Câu hỏi họ đặt ra là: làm sao biểu diễn các số nguyên trong cấu trúc này? Giả sử ta muốn chèn ba khóa: 10, 25 và 31.
So for this one we're going to store this in a one-bit span trie.
Với ví dụ này, ta sẽ lưu chúng trong một trie có độ rộng một bit.
So it means that every single level or every node in our trie is going to represent one bit in the value you want to store.
Nghĩa là mỗi tầng hay mỗi nút trong trie của ta sẽ biểu diễn một bit trong giá trị mà bạn muốn lưu.
In a real system you wouldn't go by bits, you'd go by bytes or something maybe larger, but for simplicity we'll go with this.
Trong một hệ thống thực tế, bạn sẽ không đi theo từng bit, mà đi theo từng byte hoặc có thể là đơn vị lớn hơn, nhưng cho đơn giản thì ta dùng cách này.
So to insert these records, to insert these keys in this trie, would essentially look like this.
Vậy để chèn các bản ghi này, tức là chèn các khóa này vào trie, về cơ bản sẽ trông như thế này.
Again, where every single level in our trie represents just one bit position in the keys that we're trying to store.
Một lần nữa, mỗi tầng trong trie của ta chỉ biểu diễn một vị trí bit trong các khóa mà ta cố gắng lưu.
So these are the bit representations of keys 10, 25, 31, and then for simplicity, instead of drawing all the bits out, I just put repeat 10.
Đây là biểu diễn bit của các khóa 10, 25, 31, và để cho đơn giản, thay vì vẽ ra tất cả các bit, tôi chỉ ghi là lặp lại 10 lần.
You would have a bunch of extra nodes without it. So now the first level of the trie is bit position 0.
Nếu không thì sẽ có cả đống nút thừa. Giờ tầng đầu tiên của trie là vị trí bit 0.
They're all 0s, so we just have a pointer at the 0 position in our node, jump down to the next level, whereas for the position 1, the bit 1, it just goes to null.
Tất cả đều là 0, nên ta chỉ có một con trỏ ở vị trí 0 trong nút, nhảy xuống tầng kế tiếp, còn với vị trí 1, tức bit 1, thì nó chỉ trỏ tới null.
So if anybody's looking for a key where the first bit is set to 1, I would jump into the first node, see that 1 is mapped to null, and therefore I know the key doesn't exist.
Nên nếu ai đó tìm một khóa có bit đầu tiên bằng 1, tôi sẽ nhảy vào nút đầu tiên, thấy 1 được ánh xạ tới null, và do đó tôi biết khóa đó không tồn tại.
I can stop my search. Again, the next level, they're all 0s, and repeat this 10 times for simplicity.
Tôi có thể dừng việc tìm kiếm. Tương tự, tầng tiếp theo đều là 0, và lặp lại 10 lần cho đơn giản.
Then we now get down to this level here, where now we actually have Different differentiating values, so we have some of the keys set to 0 at this position, some of the keys set to 1.
Rồi ta xuống đến tầng này, nơi giờ ta thực sự có các giá trị khác nhau, tức là một số khóa có bit 0 ở vị trí này, một số khóa có bit 1.
So I have, again, pointers coming out of both of them. So now let's say I go down here.
Vậy nên lại có con trỏ đi ra từ cả hai. Giờ giả sử tôi đi xuống đây.
Now I see I have 1, 0, 1, 0, and then same thing: I have different levels of these bit positions in this mapping down.
Giờ tôi thấy có 1, 0, 1, 0, và cũng tương tự: ta có các tầng khác nhau của những vị trí bit này trong ánh xạ đi xuống.
And then when I get to the bottom, right, it'll be a record ID or a pointer to something, like this is the value that we're trying to then represent in this trie.
Và khi xuống đến đáy, đó sẽ là một record ID hoặc một con trỏ tới thứ gì đó, tức là giá trị mà ta muốn biểu diễn trong trie này.
So let me jump ahead. This is actually kind of inefficient, right? Jumping ahead, sorry.
Để tôi nhảy lên trước. Thật ra cách này khá kém hiệu quả, đúng không? Nhảy lên trước, xin lỗi.
Ignoring the fact we're storing 0 and 1, we can just represent that as just one bit instead of two bits, right?
Bỏ qua việc ta đang lưu cả 0 và 1, ta có thể biểu diễn chỉ bằng một bit thay vì hai bit, đúng không?
Because if you had characters, you wouldn't be able to easily do that, or storing bytes, wouldn't be able to easily do that.
Vì nếu là các ký tự thì bạn không thể dễ dàng làm vậy, hoặc nếu lưu các byte thì cũng không dễ làm vậy.
But in this case here, we see that we have a bunch of these nodes where we're not actually storing any differentiating information, right?
Nhưng trong trường hợp này, ta thấy có nhiều nút như vậy mà thực ra không lưu thông tin phân biệt nào, đúng không?
Like, we don't need to store that we have one of the bits set to 1 and one of the, like, one of the bits is set, the other one is not set, or one is null, one is not null.
Ví dụ, ta không cần lưu rằng có một bit được đặt là 1 và một bit, kiểu như, một bit được đặt, bit kia thì không, hoặc một cái là null, một cái không null.
So instead we can do sort of a horizontal compression with each level: just remove the values that we don't care about and only store those, right?
Vì vậy thay vào đó, ta có thể nén theo chiều ngang ở mỗi tầng: chỉ cần bỏ đi những giá trị ta không quan tâm và chỉ lưu những giá trị còn lại, đúng không?
We don't have a key, we don't have a bunch of keys. We have someone set to 1, someone set to 0 at any given level.
Ta không có một khóa, cũng không có cả loạt khóa. Ta có một số bit được đặt là 1, một số bit là 0 ở mỗi tầng.
We just store whatever the value actually is at that bit, and we just point it to the next level.
Ta chỉ lưu giá trị thực sự của bit đó, và chỉ cần trỏ nó tới tầng tiếp theo.
But then we can compress this even further, because we see on this case over here on the side, or the bottom ones, it's kind of a straight path to the leaf nodes.
Nhưng ta còn có thể nén thêm nữa, vì ta thấy ở trường hợp bên cạnh đây, hay những nhánh phía dưới, nó gần như là một đường thẳng tới các nút lá.
Right, like for this one over here, 0 set 0 0 0 and going forth, right? We don't need to record anything, information, extra information about this.
Đúng không, như nhánh bên này, 0 được đặt, rồi 0 0 0 và cứ thế tiếp tục. Ta không cần ghi lại bất kỳ thông tin nào, thông tin thừa nào về nhánh này.
So instead, we can do what's called vertical compression and just truncate the trie and say the key that you want exists here, or the key that you're looking for, what exists here, but rather than me storing the entire key, I'm just going to stop the branch going down and just have a pointer immediately to the record that I want.
Vì vậy, ta có thể làm cái gọi là nén theo chiều dọc và cắt ngắn trie, rồi nói rằng khóa mà bạn muốn có tồn tại ở đây, hay khóa mà bạn đang tìm thì tồn tại ở đây, nhưng thay vì lưu toàn bộ khóa, tôi sẽ dừng nhánh đi xuống ở đây và chỉ đặt một con trỏ trực tiếp tới bản ghi mà tôi muốn.
So if you do this, this is called a radix tree. A radix tree is this compressed form of a trie where you're doing vertical compression.
Nếu làm như vậy, nó được gọi là radix tree. Radix tree là dạng nén của trie trong đó bạn thực hiện nén theo chiều dọc.
Now, if you truncate those branches, it's going to end up being a probabilistic data structure in that you may get actually false positives, because it may tell you the key exists when it doesn't actually, does not, because you don't have the full key embedded in the trie.
Bây giờ, nếu bạn cắt ngắn các nhánh đó, nó sẽ trở thành một cấu trúc dữ liệu xác suất vì bạn thực sự có thể gặp dương tính giả, bởi nó có thể báo khóa tồn tại trong khi thực tế là không, vì bạn không có toàn bộ khóa nhúng trong trie.
So you got to follow the pointer to go then go look up and see whether the key that you want is actually there or not, right?
Vậy bạn phải đi theo con trỏ để tra cứu và xem khóa mình muốn có thực sự ở đó hay không, đúng không?
Or you could use this, again, as a filter and say yeah, it's there or not there or might be there, but most systems will use this as the actual index, not a filter.
Hoặc bạn cũng có thể dùng nó như một bộ lọc và nói rằng nó có ở đó, không có ở đó, hoặc có thể có ở đó, nhưng hầu hết các hệ thống sẽ dùng nó làm chỉ mục thực sự, chứ không phải bộ lọc.
So when systems say they're using tries, 99% of the time they're using a radix tree, all right, because again it's a compressed form of trie without having to store all possible combinations of a key at every single level.
Vì vậy khi các hệ thống nói rằng họ đang dùng trie, thì 99% trường hợp họ đang dùng radix tree, vì như đã nói, đó là dạng nén của trie mà không cần lưu mọi tổ hợp có thể của một khóa ở từng tầng.
There's a bunch of systems that use this, and what's interesting is that even though the trie is really old, there's been a sort of resurgence in the last 10 years of a bunch of systems saying, hey look, tries are actually a good idea, we should be doing this instead of B+trees in some cases.
Có khá nhiều hệ thống dùng cấu trúc này, và điều thú vị là dù trie đã rất cũ, nhưng trong khoảng 10 năm qua đã có một sự hồi sinh khi nhiều hệ thống nói rằng: này, trie thực ra là một ý tưởng hay, trong một số trường hợp ta nên dùng nó thay cho B+tree.
Or instead of skip lists, like Cassandra was using skip lists for their memtable, for their, you know, LSM tree, and got rid of that and switched to a radix tree.
Hoặc thay cho skip list, như Cassandra từng dùng skip list cho memtable của họ, cho LSM tree của họ, rồi bỏ nó đi và chuyển sang radix tree.
Yes, the question is, before I did this compression, was it deterministic, and then when I did this compression it made it probabilistic?
Vâng, câu hỏi là trước khi tôi nén như thế này, nó có mang tính tất định không, và khi tôi nén thì nó trở thành xác suất phải không?
More like, it's deterministic, the structure itself is deterministic.
Nói đúng hơn, nó vẫn tất định, bản thân cấu trúc là tất định.
No matter what order I insert the keys, it's always going to have sort of the same, this level has this, this level has that, and so forth.
Dù tôi chèn các khóa theo thứ tự nào, nó luôn có cùng một dạng, tầng này có cái này, tầng kia có cái kia, và cứ thế.
The probabilistic part comes to be like, if I do this truncation, I may do a lookup and find a match for the key that takes me to the bottom, and then I follow the pointer to see whether it actually exists or not.
Phần xác suất xuất hiện ở chỗ, nếu tôi cắt bớt (truncation) như thế này, thì khi tra cứu, tôi có thể tìm thấy một khóa khớp và đi xuống tận đáy, rồi tôi lần theo con trỏ để xem khóa đó thực sự có tồn tại hay không.
It's basically giving me a false positive on saying the key exists when it doesn't actually, because I'm throwing away information when I do this truncation.
Về cơ bản nó cho tôi một kết quả dương tính giả khi báo rằng khóa tồn tại trong khi thực tế thì không, vì tôi đã vứt bỏ thông tin khi thực hiện việc cắt bớt này.
So the truncation part is where you get the false positive. The compression doesn't give you that. So going back here, like for this path here, I have, it's a straight line down.
Vậy phần cắt bớt chính là nơi sinh ra dương tính giả. Còn phần nén thì không gây ra điều đó. Quay lại đây, ví dụ với đường đi này, nó là một đường thẳng đi xuống.
So if I didn't do that compression over here, then I end up with, like, I don't know whether the key exists, even though I landed at the, I think the key might exist even though I landed at a leaf node in the trie.
Nên nếu tôi không nén ở chỗ này thì cuối cùng tôi sẽ, không biết khóa có tồn tại hay không, dù tôi đã đến được, tôi nghĩ là khóa có thể tồn tại, dù tôi đã đến một nút lá trong trie.
So then I have to follow the pointer to figure out whether it actually does exist or not. Yes, question is, is this a data structure you're inserting keys into? Yes.
Vì vậy tôi phải lần theo con trỏ để xác định xem nó thực sự có tồn tại hay không. Vâng, câu hỏi là đây có phải cấu trúc dữ liệu mà bạn chèn khóa vào không? Đúng vậy.
Yes, question is, what happens if you start inserting a key that then follows along, you have to expand that? Two slides, we'll handle that. Yes.
Vâng, câu hỏi là, điều gì xảy ra nếu bạn bắt đầu chèn một khóa mà đi theo đường đó, và bạn phải mở rộng nó? Hai slide nữa, chúng ta sẽ xử lý chuyện đó. Vâng.
Yes, question is, when I say check the original to see if the key matches, I don't know what the record pointer is. Actually, I don't care what the record pointer is actually pointing to.
Vâng, câu hỏi là, khi tôi nói kiểm tra bản gốc xem khóa có khớp không, tôi không biết con trỏ bản ghi là gì. Thật ra tôi không quan tâm con trỏ bản ghi đang trỏ tới đâu.
It may be a table heap. I go check that page. The data structure could be storing the tuple, is the B+tree, doesn't matter.
Có thể là một table heap. Tôi đi kiểm tra trang đó. Cấu trúc dữ liệu có thể đang lưu tuple, chẳng hạn B+tree, không quan trọng.
Whatever the final resting place of the tuple is, I gotta go check it to see whether it's actually a match or not.
Dù nơi cuối cùng chứa tuple là ở đâu, tôi cũng phải đến kiểm tra xem nó có thực sự khớp hay không.
Think of, like, when we were doing that linear hashing, linear probe hashing. I hashed my key, I landed somewhere in the hash table.
Hãy nghĩ đến lúc chúng ta làm băm tuyến tính, băm dò tuyến tính. Tôi băm khóa, rồi rơi vào một vị trí nào đó trong bảng băm.
I can't just say I'm done because I landed somewhere in the hash table and that's occupied by something.
Tôi không thể nói là xong chỉ vì tôi rơi vào một vị trí trong bảng băm và chỗ đó đang có thứ gì đó chiếm giữ.
I gotta go check the key in that hash table to see whether it's actually the one I'm actually looking for. Same idea.
Tôi phải kiểm tra khóa trong bảng băm đó xem nó có đúng là khóa tôi đang tìm không. Cùng một ý tưởng.
I gotta go follow something to go look at the original tuple, because I've thrown away some information to compress it.
Tôi phải lần theo một thứ gì đó để xem tuple gốc, vì tôi đã vứt bỏ một phần thông tin để nén nó.
The question is, the complexity of this is the same as what?
Câu hỏi là độ phức tạp của cái này giống với cái gì?
This question is, is the complexity of a compressed trie O(N), or it's still...
Câu hỏi là độ phức tạp của trie nén có phải O(N), hay vẫn là...
I mean, so like, so if it's, if it's an index, if it's a unique index, then whatever I'm pointing to, it's either gonna be the key I want or not the key I want.
Ý tôi là, nếu như đó là một chỉ mục, một chỉ mục duy nhất, thì dù tôi đang trỏ tới thứ gì, nó hoặc là khóa tôi muốn hoặc không phải khóa tôi muốn.
So that's a one lookup. To your other point of, like, if it's a non-unique index, what's that?
Vậy đó là một lần tra cứu. Còn ý kia của bạn, nếu là chỉ mục không duy nhất thì sao?
You have to match where's the key? Yeah, so it's okay, plus one.
Bạn phải so khớp xem khóa ở đâu? Vâng, thì được, cộng thêm một.
It'll be what? Will be faster?
Nó sẽ thế nào? Sẽ nhanh hơn à?
Sorry, I think, sorry, I think what you're saying is that if it's, we're talking about compressed trie or non-compressed trie, it doesn't matter.
Xin lỗi, tôi nghĩ, xin lỗi, tôi nghĩ ý em là nếu nó là, dù ta nói về trie nén hay trie không nén thì cũng không quan trọng.
Non-compressed trie, I look at my key, and so the number of things I gotta look down is the length of the key.
Với trie không nén, tôi nhìn vào khóa của mình, và số bước tôi phải đi xuống chính là độ dài của khóa.
Yes, there are different implications, it's not the same in each block typically.
Đúng, có những tác động khác nhau, thường thì mỗi block không giống nhau.
Yes, so what he's saying here, if I compress it down, this is like a really trivial example, but I compress this down, then everything will be inside a single block.
Đúng, vậy điều bạn ấy đang nói ở đây là, nếu tôi nén nó lại, đây là một ví dụ rất đơn giản, nhưng nếu tôi nén nó xuống thì mọi thứ sẽ nằm trong một block duy nhất.
Sorry, say that, say that last one again, sorry. Yes, the key's somewhere else. Sorry, the original tuple's somewhere else.
Xin lỗi, em nói lại câu cuối đó một lần nữa nhé. Đúng, khóa nằm ở một nơi khác. Xin lỗi, tuple gốc nằm ở một nơi khác.
So whether it's compressed or not, sorry, if it is compressed, then I gotta go follow the pointer to go see whether the key actually does match or not.
Vậy dù nó có nén hay không, xin lỗi, nếu nó được nén, thì tôi phải đi theo con trỏ để xem khóa đó thực sự có khớp hay không.
If it is not compressed, the key might not exist, I get the bottom of the trie and I'm done.
Nếu nó không được nén, khóa có thể không tồn tại, tôi xuống tới đáy của trie là xong.
If I get to the bottom of the trie and it is a match, then I still gotta go follow the pointer to get the tuple.
Nếu tôi xuống tới đáy của trie và nó khớp, thì tôi vẫn phải đi theo con trỏ để lấy tuple.
Follow the record, I need to get the tuple. You good or no? So you're doing all this work.
Đi theo bản ghi, tôi cần lấy tuple. Em hiểu chưa? Vậy là bạn làm tất cả những việc này.
The whole point of an index is just for not to do a sequential scan on everything. You gotta say, for a given key, does this thing exist or not?
Toàn bộ mục đích của một chỉ mục chỉ là để không phải quét tuần tự toàn bộ dữ liệu. Bạn phải trả lời: với một khóa cho trước, thứ này có tồn tại hay không?
And if it does, tell me exactly where to go get it, because I want to avoid a sequential scan of the tables.
Và nếu có, hãy cho tôi biết chính xác phải đến đâu để lấy nó, vì tôi muốn tránh việc quét tuần tự các bảng.
Again, think of extremes: if I have a billion tuples, I don't want to scan a billion tuples to go find the record that I want.
Một lần nữa, hãy nghĩ đến các trường hợp cực đoan: nếu tôi có một tỉ tuple, tôi không muốn quét một tỉ tuple để tìm bản ghi mình cần.
If I have a data structure that's a little larger, sorry, it's an extra space, extra computational cost to maintain this thing, but I'm avoiding that sequential scan, that's usually going to be a good trade-off.
Nếu tôi có một cấu trúc dữ liệu lớn hơn một chút, xin lỗi, tức là tốn thêm không gian và thêm chi phí tính toán để duy trì nó, nhưng tôi tránh được việc quét tuần tự đó, thì thường đó sẽ là một sự đánh đổi tốt.
Alright, so tries, again, they're an old data structure, but there's been a resurgence in the last 10 years.
Được rồi, vậy trie, như đã nói, là một cấu trúc dữ liệu cũ, nhưng nó đã hồi sinh trong 10 năm qua.
A bunch of systems are actually using it, and it all comes from the Germans who built the system called HyPer.
Rất nhiều hệ thống đang thực sự sử dụng nó, và tất cả bắt nguồn từ những người Đức đã xây dựng hệ thống có tên HyPer.
And then DuckDB uses a version of their trie, because DuckDB saw their papers and wrote the same thing.
Sau đó DuckDB dùng một phiên bản trie của họ, vì DuckDB đọc các bài báo của họ và viết lại giống như vậy.
And then the HyPer guys sold his data system to Tableau, which got bought by Salesforce, and then he rewrote a new system called Umbra that also uses this trie index, but then Umbra got forked off as a commercial product called CedarDB.
Rồi nhóm HyPer bán hệ thống dữ liệu của anh ấy cho Tableau, công ty này sau đó bị Salesforce mua lại, và anh ấy viết một hệ thống mới tên là Umbra cũng dùng chỉ mục trie này, nhưng sau đó Umbra được tách nhánh thành một sản phẩm thương mại gọi là CedarDB.
But Redis and SQLite and a bunch of other systems use this internally. You sometimes see this literature called Patricia Trees.
Nhưng Redis, SQLite và nhiều hệ thống khác cũng dùng nó bên trong. Đôi khi bạn thấy tài liệu gọi cái này là Patricia Tree.
I looked this up and it's actually from like Don Knuth's books, from like all computer science in the 1970s.
Tôi đã tra cứu và nó thực ra có từ sách của Don Knuth, từ khoa học máy tính những năm 1970.
And there's a data structure, there's a version of this called Practical Algorithm to Retrieve Information Encoded in Alphanumeric, and so Patricia Trees come from that acronym.
Và có một cấu trúc dữ liệu, có một phiên bản của nó gọi là Practical Algorithm to Retrieve Information Encoded in Alphanumeric, và Patricia Tree xuất phát từ từ viết tắt đó.
Again, sometimes you see it's called Radix Trees, or there's Tries or Patricia Trees. They're all, they're all roughly the same thing. All right, let's quickly talk about how we want to handle modifications.
Một lần nữa, đôi khi bạn thấy nó được gọi là Radix Tree, hoặc Trie hay Patricia Tree. Tất cả đều gần như là một thứ giống nhau. Được rồi, ta hãy nói nhanh về cách xử lý các thao tác sửa đổi.
Say now we have a trie that looks like this, and now within every node I can actually store multiple keys inside them.
Giả sử bây giờ ta có một trie trông như thế này, và trong mỗi nút, ta thực sự có thể lưu nhiều khóa.
They're, they're, they're variable length, but we know how to handle that using sort of roughly the slotted page architecture that we saw before.
Các khóa này có độ dài thay đổi, nhưng ta biết cách xử lý việc đó, đại khái bằng kiến trúc slotted page mà ta đã thấy trước đây.
So if I want to insert HAIR, right, I know it should go here, so I just follow the pointers down, find a free slot in this node here and insert my entry.
Vậy nếu tôi muốn chèn HAIR, tôi biết nó phải nằm ở đây, nên chỉ cần đi theo các con trỏ xuống, tìm một slot trống trong nút này và chèn mục của mình vào.
If I want to delete HAT, right, follow the pointer down to H A T, find T, go ahead and delete that, that's fine.
Nếu tôi muốn xóa HAT, thì đi theo con trỏ xuống H A T, tìm T, rồi cứ thế xóa nó đi, vậy là xong.
But then now we can decide that if we delete HAT, now we only have one entry in this bottom node here.
Nhưng bây giờ ta có thể quyết định rằng nếu xóa HAT, thì giờ nút dưới cùng này chỉ còn một mục.
So in some implementations of tries, or called Adaptive Radix Trees, ARTs, they can decide, okay, well, I don't want to have this guy hanging out by himself, because then there's a straight path from A down to I R.
Vì vậy trong một số cách cài đặt trie, hay còn gọi là Adaptive Radix Tree, ART, chúng có thể quyết định: được rồi, tôi không muốn để nút này đứng một mình như vậy, vì khi đó có một đường thẳng từ A xuống I R.
Again, I can do that vertical compression and move I R up and everything's just fine.
Một lần nữa, tôi có thể nén theo chiều dọc và đưa I R lên trên, và mọi thứ vẫn ổn.
I'm glossing over the details of this quite a bit, but that's roughly how these algorithms work. So I quickly wanted to mention that there's a bunch of implementations.
Tôi đang lướt qua khá nhiều chi tiết của phần này, nhưng đại khái đó là cách các thuật toán này hoạt động. Tôi muốn nhắc nhanh rằng có khá nhiều cách cài đặt.
One implementation of this, again, I think I mentioned before, the ART index is the one from HyPer that DuckDB uses as well.
Một cách cài đặt, tôi nghĩ tôi đã nhắc trước đây, là chỉ mục ART của HyPer, mà DuckDB cũng dùng.
There's another one called Judy Arrays, which is sort of the first Radix Tree that allowed this sort of the adaptive nodes, moving things up and down.
Còn một cái khác gọi là Judy Arrays, có thể coi là Radix Tree đầu tiên cho phép các nút thích ứng, tức là di chuyển mọi thứ lên xuống.
This is invented by HP, but they wrote a patent on it, and so for years it would show up on Hacker News saying like, "Hey, there's this cool thing called Judy Arrays.
Nó do HP phát minh, nhưng họ đã đăng ký bằng sáng chế cho nó, nên suốt nhiều năm trên Hacker News luôn có người nói kiểu như: "Này, có một thứ hay ho gọi là Judy Arrays.
It'd be nice if we could implement this, but there's this patent."
Sẽ rất tốt nếu ta cài đặt được nó, nhưng có bằng sáng chế đó."
And then even though the authors of the actual Judy Arrays said, "Oh, HP won't sue you, trust us," nobody actually ended up implementing it.
Và dù các tác giả của Judy Arrays đã nói: "Ồ, HP sẽ không kiện bạn đâu, tin chúng tôi đi", rốt cuộc cũng chẳng ai cài đặt nó.
It's off patent as of like two years ago, but as far as I know, I'm not aware of any other system using it.
Bằng sáng chế đã hết hạn từ khoảng hai năm trước, nhưng theo tôi biết thì tôi không thấy hệ thống nào khác dùng nó.
Instead, they're all using the ART index, but basically, roughly, the idea is the same thing, but you can have these adaptive node layouts and you can move, you can resize them based on what the keys you want to store.
Thay vào đó, tất cả đều dùng chỉ mục ART, nhưng về cơ bản, ý tưởng đại khái là giống nhau, là bạn có thể có các cách bố trí nút thích ứng và có thể di chuyển, có thể thay đổi kích thước chúng dựa trên các khóa bạn muốn lưu.
All right, so in the last half an hour, I want to go through full text search indexes and vector indexes. Yes, question?
Được rồi, trong nửa giờ cuối, tôi muốn trình bày về chỉ mục tìm kiếm toàn văn và chỉ mục vectơ. Vâng, bạn có câu hỏi?
Question is, in what scenarios would a radix tree be better than a B+tree for range scans? B+trees are gonna be better for large keys. Tries were typically better because they're more compressed.
Câu hỏi là, trong trường hợp nào thì radix tree tốt hơn B+tree cho quét theo khoảng? B+tree sẽ tốt hơn với các khóa lớn. Trie thường tốt hơn vì chúng được nén nhiều hơn.
Um, for what's that? Like point, like point lookups? Yeah, like I'm looking for a single key, tries would probably be better.
Ừm, bạn nói gì? Như tra cứu điểm, tra cứu điểm à? Vâng, ví dụ như khi tôi tìm một khóa duy nhất, thì trie có lẽ sẽ tốt hơn.
If the tries aren't, like, if the keys are really big, again, it's a cop-out, I'm saying it depends.
Còn nếu các khóa thực sự rất lớn thì trie không... một lần nữa, đây là câu trả lời né tránh, tôi nói là tùy trường hợp.
Like if I'm doing like a bunch of lookups on keys that don't exist, a trie is gonna be way faster because, like, if I don't see it in the first node, I'm done.
Ví dụ nếu tôi thực hiện hàng loạt lượt tra cứu các khóa không tồn tại, thì trie sẽ nhanh hơn nhiều, vì nếu tôi không thấy nó ở nút đầu tiên là tôi xong luôn.
But if I do range scans, the B+trees would be better. Yeah, and typically in most data systems, they'll implement either B+trees or the radix trees for, as in, table indexes.
Nhưng nếu tôi quét theo khoảng thì B+tree sẽ tốt hơn. Vâng, và thông thường ở hầu hết các hệ thống dữ liệu, họ sẽ cài đặt B+tree hoặc radix tree cho các chỉ mục của bảng.
They won't do both, whereas, like, some systems, they'll have the hash table indexes plus the B+trees, but they won't have two, they won't usually implement two data structures.
Họ sẽ không làm cả hai, trong khi một số hệ thống có chỉ mục bảng băm cộng với B+tree, nhưng họ sẽ không có hai loại, thường họ không cài đặt hai cấu trúc dữ liệu.
Um, okay. So all the indexes we talked about, all the data structures we talked about so far, are fantastic for doing what, again, are called point queries.
Ừm, được rồi. Vậy tất cả các chỉ mục chúng ta đã nói tới, tất cả các cấu trúc dữ liệu chúng ta đã nói đến cho tới giờ, đều rất tuyệt cho những gì được gọi là truy vấn điểm (point query).
Go find Andy's bank account, or, you know, go get your single user account, and for range scans, right, find all the people within, you know, that were born within some date range.
Tìm tài khoản ngân hàng của Andy, hoặc lấy tài khoản của một người dùng duy nhất, và với quét theo khoảng, tức là tìm tất cả những người sinh ra trong một khoảng ngày nào đó.
Right? What they're not good at are sort of keyword searches. So meaning like, find all the articles where the term or the word Pavlo appears.
Đúng không? Thứ chúng không giỏi là tìm kiếm theo từ khóa. Ý tôi là, ví dụ tìm tất cả các bài viết có chứa thuật ngữ hay từ Pavlo.
Because think about how would you do that in your B+tree? Because the key has to be the entire, of the index has to be whatever the entire value is for a given column.
Vì hãy nghĩ xem bạn sẽ làm việc đó thế nào trong B+tree? Bởi vì khóa phải là toàn bộ giá trị của cột đã cho trong chỉ mục.
So if I just sort of show a simple example like Wikipedia, we had this sort of revision table.
Nên nếu tôi lấy một ví dụ đơn giản như Wikipedia, chúng ta có bảng revision này.
There was this column called content that was just the text field of whatever somebody entered in when they wrote the Wikipedia article.
Có một cột tên là content, chỉ là trường văn bản chứa bất cứ gì mà ai đó nhập vào khi viết bài Wikipedia.
So if I build an index on this, like a B+tree or trie, it doesn't matter, then I'm not picking out the individual keys, or sorry, individual words of the column.
Nếu tôi xây dựng chỉ mục trên cột này, như B+tree hay trie, loại nào cũng vậy, thì tôi không lấy ra từng khóa riêng lẻ, xin lỗi, từng từ riêng lẻ của cột.
It's the entire column.
Mà là toàn bộ cột.
So I can't do a query like this, like on an index, like find all the records where the content contains the keyword Pavlo, because the B+tree doesn't know how to pick apart the individual words.
Nên tôi không thể thực hiện một truy vấn như thế này trên chỉ mục, như tìm tất cả bản ghi có content chứa từ khóa Pavlo, vì B+tree không biết cách tách riêng từng từ.
It's going to see, try to do a match on the entire thing. So this is always going to end up being a sequential scan in a system, right?
Nó sẽ cố khớp với toàn bộ giá trị. Vì vậy trong hệ thống, việc này luôn kết thúc bằng quét tuần tự, đúng không?
It's actually an incorrect query anyway, because the wildcard at the end could match, like, someone, like there's a Russian scientist Pavlov with the v at the end.
Thực ra dù sao đó cũng là một truy vấn không đúng, vì ký tự đại diện ở cuối có thể khớp với ví dụ nhà khoa học người Nga Pavlov có chữ v ở cuối.
It would match them, not maybe exactly what I'm looking for. So this is what an inverted index is going to solve for us, and sometimes called a full text search index.
Nó sẽ khớp với họ, có thể không đúng thứ tôi đang tìm. Đây chính là điều chỉ mục đảo (inverted index) sẽ giải quyết cho chúng ta, đôi khi còn gọi là chỉ mục tìm kiếm toàn văn (full text search).
And the basic idea is that for a given column or attribute within a table we want to build this index on, we're going to pull out the individual words or terms in the data and build an index on those things, rather than the entire value.
Ý tưởng cơ bản là với một cột đã cho hay thuộc tính trong bảng mà ta muốn xây dựng chỉ mục, ta sẽ tách ra từng từ hay thuật ngữ trong dữ liệu và xây dựng chỉ mục trên các thứ đó, thay vì trên toàn bộ giá trị.
Right, so this is, again, sometimes called full text search indexes. In, like, medieval times they were called concordances.
Vâng, đây là cái đôi khi được gọi là chỉ mục tìm kiếm toàn văn. Vào thời trung cổ, người ta gọi chúng là concordance (bảng tra từ).
Like, there were some monks back in the 1200s that went, like, some guy had a bunch of people read the Bible and create a mapping list of, like, here's every word in the Bible, the glossary, what pages it appears on.
Hồi thế kỷ 13, có một số tu sĩ có ông nọ cho một nhóm người đọc Kinh Thánh rồi lập một danh sách ánh xạ, ghi mỗi từ trong Kinh Thánh, như một bảng chú giải, xuất hiện ở những trang nào.
The same idea, right? And then a bunch of database systems are now going to support these.
Cùng một ý tưởng, đúng không? Và giờ có khá nhiều hệ cơ sở dữ liệu hỗ trợ loại chỉ mục này.
Uh, they're not always great, and the SQL syntax of how to use them is going to vary widely between one system to the next, but the general idea of how they're going to work is going to be the same.
Ừm, chúng không phải lúc nào cũng tốt, và cú pháp SQL để dùng chúng khác nhau rất nhiều giữa hệ này với hệ khác, nhưng ý tưởng chung về cách chúng hoạt động thì giống nhau.
So we take this, again, the content field here of this table, and we're going to pull out all the individual terms. We'll talk in a second how we actually do that.
Vậy ta lấy trường content này của bảng, và tách ra tất cả các từ riêng lẻ. Lát nữa ta sẽ nói cụ thể làm việc đó thế nào.
And then we'll have this thing, this dictionary data structure, where for every single term we'll keep a counter of how many times we've seen the term, and then it'll then have a pointer to what we call a posting list, which is going to be the record IDs of the tuples that had this particular term in the data structure,
Rồi ta sẽ có cấu trúc dữ liệu từ điển này, trong đó với mỗi từ ta giữ một bộ đếm cho biết ta đã thấy từ đó bao nhiêu lần, và nó có một con trỏ tới thứ ta gọi là posting list, tức là danh sách các record ID của những tuple có chứa từ này trong cấu trúc dữ liệu,
or sorry, term in the column we built the index on. Right, so term frequency and so forth.
à xin lỗi, có từ này trong cột mà ta xây chỉ mục. Vâng, tức là tần suất của từ, v.v.
So there's a bunch of these sort of specialized storage engines or storage managers that'll give you these sort of full, these inverted indexes, and that's pretty much all they do, is just do the inverted Index, like, but not meant to be the primary storage of your database, uh, right?
Có khá nhiều công cụ lưu trữ chuyên biệt hay trình quản lý lưu trữ cung cấp các chỉ mục đảo ngược (inverted index) này, và về cơ bản chúng chỉ làm đúng việc là inverted index, chứ không nhằm làm nơi lưu trữ chính của cơ sở dữ liệu, đúng không?
But like, you can build a larger system on top of that. So Lucene is probably the most famous one of all these.
Nhưng bạn có thể xây một hệ thống lớn hơn trên nền đó. Lucene có lẽ là cái nổi tiếng nhất trong số này.
All right, it's written in Java, it's widely used. Xapian is one of C++. The new hot one now is Tantivy, which is basically Lucene but written in Rust.
Nó viết bằng Java và được dùng rộng rãi. Xapian là một cái viết bằng C++. Cái mới đang hot hiện nay là Tantivy, về cơ bản là Lucene nhưng viết bằng Rust.
And again, they're basically building these things and they have various uh ways to tokenize them and split things up and other things.
Và về cơ bản họ xây dựng những thứ này, và chúng có nhiều cách để tokenize và tách dữ liệu, cùng các thứ khác.
And then there's larger systems built on top of this, uh, that have these, uh, again, that expose sometimes a SQL interface, expose a custom API, that then allows you to do queries on top of uh these inverted indexes.
Rồi có những hệ thống lớn hơn xây trên nền này, mà, ừm, đôi khi cung cấp giao diện SQL, hoặc một API riêng, cho phép bạn truy vấn trên các chỉ mục đảo ngược này.
And this space is super powerful.
Và mảng này cực kỳ mạnh.
Elasticsearch is probably, they're a public company, they're probably the biggest one in the space, but then they changed the license and people didn't like that, so then Amazon forked it and it became OpenSearch.
Elasticsearch có lẽ, họ là công ty niêm yết, có lẽ là bên lớn nhất trong mảng này, nhưng rồi họ đổi giấy phép và mọi người không thích, nên Amazon đã fork nó và thành OpenSearch.
Um, Splunk is a really old one. They got bought by Cisco last year. Quit, quit, just got bought by Datadog in January, right?
Splunk là một cái rất lâu đời. Năm ngoái họ bị Cisco mua lại. Còn Quit, Quit vừa bị Datadog mua hồi tháng Một, đúng không?
So these things are widely used and they're pretty popular, even though, again, your, you know, your favorite relational database system like Postgres and others will have this kind of functionality built in.
Vậy những hệ này được dùng rộng rãi và khá phổ biến, dù rằng, hệ cơ sở dữ liệu quan hệ yêu thích của bạn như Postgres và các hệ khác cũng có sẵn chức năng kiểu này.
They're not going to be as sophisticated as the specialized engines like Lucene and Tantivy.
Chúng sẽ không tinh vi bằng các engine chuyên biệt như Lucene và Tantivy.
All right, so let me show what an inverted index looks like for Lucene and then I'll show what the Postgres one looks like.
Được rồi, để tôi cho xem inverted index của Lucene trông thế nào rồi tôi sẽ cho xem bản của Postgres.
So in Lucene, the basic data structure I'm going to use is called a finite state transducer, and it's basically going to be like a trie where we're going to break apart the digits within the keys we want to represent, uh, the terms we want to represent.
Vậy trong Lucene, cấu trúc dữ liệu cơ bản mà tôi sẽ dùng gọi là finite state transducer, và về cơ bản nó giống như một trie, trong đó chúng ta sẽ tách các ký tự bên trong những khóa mà ta muốn biểu diễn, ừm, tức là các thuật ngữ (term) mà ta muốn biểu diễn.
But then rather than being a pointer to where the record actually exists, we're actually going to use the weights in the data structure to determine the offset in this sort of dictionary of keys or terms so it looks sort of like this so say i want to look up and find find the key pav p -a -v
Nhưng thay vì là con trỏ tới nơi bản ghi thực sự tồn tại, ta sẽ dùng các trọng số trong cấu trúc dữ liệu để xác định vị trí offset trong một dạng từ điển các khóa hay các term, nên nó trông đại khái như thế này, giả sử tôi muốn tra cứu và tìm khóa pav, p -a -v
so i i have my key pav p -a
vậy tôi có khóa pav là p -a
-v p -a -v p -a -v p
-v p -a -v p -a -v p
-a -v p -a -v p -a -v p -a -v p -a -v p
-a -v p -a -v p -a -v p -a -v p -a -v p
-a -v p -a -v p -a -v p -a
-a -v p -a -v p -a -v p -a
-v p -a -v p -a -v p -a -v p -a -v
-v p -a -v p -a -v p -a -v p -a -v
p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v
p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v
p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a
p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a -v p -a
-v p -a -v p -a -v p -a -v maintaining the sort of list of the posting IDs. Now, maintaining this, again, is going to be expensive.
-v p -a -v p -a -v p -a -v duy trì danh sách có thứ tự các posting ID. Giờ, việc duy trì cái này, một lần nữa, sẽ rất tốn kém.
So to avoid the overhead of doing that every single time you do an insert update or delete, they're going to bring in a mod log, just like we saw many times before this semester, where all my updates will get absorbed into that mod log.
Vì vậy, để tránh chi phí phải làm việc đó mỗi lần bạn chèn, cập nhật hoặc xóa, họ sẽ đưa vào một mod log, giống như chúng ta đã thấy nhiều lần trong học kỳ này, nơi mọi cập nhật của tôi sẽ được hấp thụ vào mod log đó.
And then there's a background job that runs through and compacts it and merges everything into the main dictionary.
Sau đó có một tác vụ chạy nền sẽ chạy qua và nén gọn nó, rồi hợp nhất mọi thứ vào từ điển chính.
So beyond just doing a given term, find me all the records that have this term in it, some other things you can do with these full -text search indexes that are really cool, you can use them for ranking.
Vậy ngoài việc với một term cho trước, tìm cho tôi tất cả các bản ghi có chứa term này, thì một số việc khác bạn có thể làm với các chỉ mục tìm kiếm toàn văn này, và rất thú vị, là bạn có thể dùng chúng để xếp hạng.
So instead of just saying, "Find me all the records where this term exists," you want to know what's the importance of the different records that match.
Tức là thay vì chỉ nói "Tìm cho tôi tất cả các bản ghi có term này", bạn muốn biết mức độ quan trọng của các bản ghi khớp khác nhau là bao nhiêu.
So again, if I'm doing a lookup on the word wu-tang, I could potentially get a lot of articles on Wikipedia that match that.
Vậy một lần nữa, nếu tôi tra cứu từ wu-tang, Có thể tôi sẽ nhận được rất nhiều bài viết trên Wikipedia khớp với từ đó.
But the one that's probably the most important is the one where wu-tang appears the most, likely the article about the wu-tang clan.
Nhưng bài quan trọng nhất có lẽ là bài mà wu-tang xuất hiện nhiều nhất, nhiều khả năng là bài về wu-tang clan.
And that'll have a higher importance if I just use a simple ranking algorithm that says, what's the frequency of this term appearing in a given record relative to the appearance in all the other records?
Và bài đó sẽ có độ quan trọng cao hơn nếu tôi dùng một thuật toán xếp hạng đơn giản, trong đó hỏi rằng: tần suất xuất hiện của từ này trong một bản ghi so với mức xuất hiện trong tất cả các bản ghi khác là bao nhiêu?
This helps you out to avoid things like the word "the" that's going to appear everywhere, and so that you don't end up with weird rankings because that term appears everywhere as well.
Cách này giúp bạn tránh những trường hợp như từ "the", vốn xuất hiện ở khắp nơi, và để bạn không nhận được những bảng xếp hạng kỳ cục chỉ vì từ đó cũng xuất hiện ở khắp nơi.
So tf-idf is the basic one that things like Postgres do.
Vậy tf-idf là phương pháp cơ bản mà các hệ thống như Postgres sử dụng.
But then the Lucene and the other specialized search engine systems with full-text search indexes, they can do bm25, which is an enhanced version of this.
Còn Lucene và các hệ thống công cụ tìm kiếm chuyên dụng khác có chỉ mục tìm kiếm toàn văn bản thì có thể dùng bm25, là một phiên bản nâng cao của phương pháp này.
Basically, if you have a key that's repeated, a term that's repeated over and over again, at some point its weight decays because it's not over-flooded with that term over and over again.
Về cơ bản, nếu có một khóa bị lặp lại, một từ bị lặp đi lặp lại nhiều lần, thì đến một lúc nào đó trọng số của nó sẽ giảm dần vì bản ghi không bị tràn ngập bởi từ đó lặp đi lặp lại.
Like, if an article has nothing but the word wu-tang in it, with no other words in it, you don't want that thing to always be the most important thing because it's kind of full of garbage.
Ví dụ, nếu một bài viết chẳng có gì ngoài từ wu-tang, không có từ nào khác, bạn không muốn bài đó luôn là bài quan trọng nhất vì nó toàn là rác.
So again, not all the relational data systems that support full-text inverted indexes can do the more sophisticated things.
Vậy nên, không phải mọi hệ thống dữ liệu quan hệ hỗ trợ chỉ mục đảo toàn văn bản đều làm được những việc phức tạp hơn.
Like, Postgres only does tf-idf. You have to use extensions and add-ons to get bm25. I don't know what Oracle and SQL Server do.
Chẳng hạn, Postgres chỉ có tf-idf. Bạn phải dùng tiện ích mở rộng và add-on để có bm25. Tôi không biết Oracle và SQL Server làm gì.
The other thing you can also do to improve search is to run these things through tokenizers.
Một việc khác bạn cũng có thể làm để cải thiện tìm kiếm là cho dữ liệu đi qua các bộ tách từ (tokenizer).
So in my simple example, I just said, "All right, I'll split the column attribute based on the space."
Trong ví dụ đơn giản của tôi, tôi chỉ nói: "Được rồi, tôi sẽ tách thuộc tính của cột dựa trên dấu cách."
But maybe sometimes where, if I want to do a fuzzy match, find things where people, even though they misspell the words, I can run this through a tokenizer that can rewrite the terms into n-grams or do other things like remove hyphens or map things like u.s.a.
Nhưng đôi khi, nếu tôi muốn so khớp mờ, tìm những thứ mà người ta viết sai chính tả các từ, tôi có thể cho qua một tokenizer để viết lại các từ thành n-gram hoặc làm những việc khác như bỏ dấu gạch nối hoặc ánh xạ những thứ như u.s.a.
It's the same thing as USA without the periods. So there's a bunch of other tricks you can do to improve search. So with an n-gram tokenizer, you basically take the term wu-tang.
Nó giống với USA nhưng không có dấu chấm. Vậy còn rất nhiều mẹo khác bạn có thể dùng để cải thiện tìm kiếm. Với tokenizer n-gram, về cơ bản bạn lấy từ wu-tang.
And then if I want to make trigrams, I just have all combinations of consecutive characters up to the three letters.
Và nếu tôi muốn tạo trigram, tôi chỉ cần lấy mọi tổ hợp các ký tự liên tiếp có độ dài tối đa ba chữ cái.
So now I can do fuzzy matches of someone only writes, someone searches like wu-tang instead of the g. I can still do a match on that.
Như vậy giờ tôi có thể so khớp mờ khi ai đó chỉ viết, ai đó tìm kiếm kiểu wu-tang nhưng thiếu chữ g. Tôi vẫn có thể khớp được với từ đó.
Whereas if I'm just using an inverted index without this tokenization, then I can only do exact matches.
Trong khi nếu tôi chỉ dùng chỉ mục đảo mà không có bước tách từ này, thì tôi chỉ có thể so khớp chính xác.
What's that? Oh, that's a typo. Yeah, the question is, why does UTA appear twice? That's a typo. Thank you. I'll fix that.
Gì cơ? À, đó là lỗi đánh máy. Vâng, câu hỏi là tại sao UTA xuất hiện hai lần? Đó là lỗi đánh máy. Cảm ơn em. Tôi sẽ sửa lại.
All right, so these inverted indexes are useful for, again, looking for contents based on the keywords. But it's kind of like trying to do almost an exact match.
Được rồi, vậy các chỉ mục đảo ngược này hữu ích cho việc tìm nội dung dựa trên các từ khóa. Nhưng nó gần như chỉ là kiểu so khớp chính xác.
Like, does this keyword exist? And you can play some games like, again, wu-tang with a hyphen can be matched to wu-tang without the hyphen or wu-tang without the space.
Kiểu như, từ khóa này có tồn tại không? Và bạn có thể dùng một vài mẹo, chẳng hạn, wu-tang có dấu gạch nối có thể khớp với wu-tang không có dấu gạch nối, hoặc wutang không có khoảng trắng.
The tokenizer can sort of handle that. But what you can't do is do searches based on the meaning of what the data actually represents.
Bộ tách từ (tokenizer) có thể xử lý phần nào việc đó. Nhưng điều bạn không thể làm là tìm kiếm dựa trên ý nghĩa mà dữ liệu thực sự biểu diễn.
So I can't ask my databases with a full-text inverted index and say, find me all the songs that talk about people singing or doing some action unless I can do a lookup exactly in all possible combinations of the synonyms for that action, for that idea.
Vậy tôi không thể hỏi cơ sở dữ liệu có chỉ mục đảo ngược toàn văn rằng: hãy tìm tất cả các bài hát nói về việc người ta hát hoặc thực hiện một hành động nào đó, trừ khi tôi tra cứu chính xác mọi tổ hợp có thể có của các từ đồng nghĩa với hành động đó, với ý tưởng đó.
Because it's just trying to match bits in the index. It can't match in deeper. It doesn't have any deeper meaning about what's actually in your data.
Vì nó chỉ cố khớp các bit trong chỉ mục. Nó không thể khớp sâu hơn. Nó không hiểu ý nghĩa sâu hơn về những gì thực sự có trong dữ liệu của bạn.
So this is what the similarity search that people are doing, or the RAG stuff people are doing in modern AI systems.
Đây chính là thứ mà tìm kiếm theo độ tương đồng mà mọi người đang làm, hay các thứ về RAG mà mọi người đang làm trong các hệ thống AI hiện đại.
And you can just build this directly in your database as we do this. It's just another index. So let's say, again, I have my table of all my albums.
Và bạn có thể xây dựng trực tiếp điều này trong cơ sở dữ liệu của mình. Nó chỉ là một chỉ mục khác. Giả sử tôi lại có bảng chứa tất cả các album.
And for whatever reason, I have a column in there with all the lyrics for all the songs in every album.
Và vì lý do nào đó, tôi có một cột chứa toàn bộ lời bài hát của mọi bài trong mỗi album.
Obviously, you would not want to store it into the entire album; you'd store it per song. We can ignore that.
Rõ ràng bạn sẽ không muốn lưu cho cả album; bạn sẽ lưu theo từng bài hát. Ta có thể bỏ qua điều đó.
So what I'm going to do is I'm going to take all that text column. I'm going to run it through my favorite transformer. OpenAI has one.
Vậy tôi sẽ lấy toàn bộ cột văn bản đó. Tôi sẽ cho nó chạy qua mô hình transformer yêu thích của mình. OpenAI có một mô hình.
There's a bunch of Hugging Faces. There's the original one, Word2Vec. Whatever you want. It's going to convert free-form text into a fixed-length array of floating-point numbers called an embedding.
Có cả loạt mô hình của Hugging Face. Có mô hình gốc là Word2Vec. Bạn thích cái nào cũng được. Nó sẽ chuyển văn bản tự do thành một mảng có độ dài cố định gồm các số dấu phẩy động, gọi là embedding.
And then I can take those embeddings, store this in a vector index. I'm not saying what this is. Yeah, we'll cover that in the next few slides.
Rồi tôi có thể lấy các embedding đó và lưu vào một chỉ mục vectơ. Tôi chưa nói nó là gì. Vâng, ta sẽ học trong vài slide tới.
But there's some way for now for me to do lookups on those embeddings in an efficient manner.
Nhưng hiện giờ có cách nào đó để tôi thực hiện các tra cứu trên những embedding đó một cách hiệu quả.
So now when my query comes along, and here I'm showing free-form text instead of SQL, but you could put whatever the search term in SQL if you wanted, I'm going to say, find me all the lyrics about running from the police.
Vậy khi truy vấn của tôi đến, ở đây tôi hiển thị văn bản tự do thay vì SQL, nhưng bạn có thể đặt từ khóa tìm kiếm vào SQL nếu muốn, tôi sẽ nói: tìm cho tôi tất cả lời bài hát về việc chạy trốn cảnh sát.
So I take that running from the police portion, and I run it through my same transformer. And somehow, magically, it generates an embedding that represents that search term.
Vậy tôi lấy phần chạy trốn cảnh sát đó, và cho chạy qua cùng mô hình transformer đó. Và bằng cách nào đó, thật kỳ diệu, nó tạo ra một embedding biểu diễn cụm từ tìm kiếm đó.
And then now I do an approximate nearest neighbor search in my vector index based on that embedding that I got.
Và rồi bây giờ tôi thực hiện tìm kiếm láng giềng gần nhất xấp xỉ trong chỉ mục vectơ của tôi, dựa trên embedding mà tôi vừa có được.
And it's going to produce a rank list of record IDs that somehow semantically match the thing I'm looking for.
Và nó sẽ tạo ra một danh sách xếp hạng các record ID mà bằng cách nào đó khớp về mặt ngữ nghĩa với thứ tôi đang tìm.
The semantic meaning of the search term running from the police is somehow, through the transformer, imbibed in that, or imbued in that vector of floating point numbers.
Ý nghĩa ngữ nghĩa của cụm tìm kiếm "running from the police" bằng cách nào đó, thông qua transformer, được thấm vào, hay được ngấm vào vectơ các số dấu phẩy động đó.
The floating point numbers aren't meant to be understood by humans. Just the transformer magically does that for it, because that's what it's trained on.
Các số dấu phẩy động đó không được tạo ra để con người hiểu. Chỉ là transformer làm điều đó một cách thần kỳ, vì đó là thứ nó được huấn luyện để làm.
I can also do other things, like store additional metadata that is in my table in my vector index, so that if I have additional queries that want to do lookups on semantic meaning and additional qualifiers, instead of having to do a sequential scan, I can do all the searches inside of the index.
Tôi cũng có thể làm những việc khác, như lưu thêm siêu dữ liệu có trong bảng của tôi vào trong chỉ mục vectơ, để nếu tôi có thêm các truy vấn muốn tra cứu theo ý nghĩa ngữ nghĩa cùng với các điều kiện bổ sung, thay vì phải thực hiện quét tuần tự, tôi có thể thực hiện toàn bộ việc tìm kiếm bên trong chỉ mục.
So if I want to find all the songs that talk about running from the police and released after 2005, I take, again, that search term, run that through my transformer, I get an embedding.
Ví dụ, nếu tôi muốn tìm tất cả các bài hát nói về việc chạy trốn cảnh sát và phát hành sau năm 2005, thì tôi lại lấy cụm tìm kiếm đó, cho chạy qua transformer và nhận được một embedding.
But then I can also pass along, when I do my lookup, the qualifier year greater than 2005.
Nhưng tôi cũng có thể truyền kèm, khi thực hiện tra cứu, điều kiện year lớn hơn 2005.
So now, as I'm doing my approximate nearest neighbor search inside this thing, I can also throw away entries that don't match that second qualifier.
Như vậy, khi tôi thực hiện tìm kiếm láng giềng gần nhất xấp xỉ bên trong cấu trúc này, tôi cũng có thể loại bỏ các mục không khớp với điều kiện thứ hai đó.
And there's a question like, do you do the year filter first or after you do the embedding lookup? There's no good answer on how to do that.
Và có một câu hỏi là, bạn lọc theo năm trước hay sau khi tra cứu embedding? Không có câu trả lời nào là tốt nhất cho việc đó.
So the magic of this makes this all work. It's called a vector index.
Thứ giúp tất cả điều này hoạt động được gọi là chỉ mục vectơ.
And this is a specialized data structure that's specifically designed to do nearest neighbor or approximate nearest neighbor searches on these embeddings. We're just going to be a one-dimensional array of floating-point numbers.
Đây là một cấu trúc dữ liệu chuyên biệt, được thiết kế riêng để thực hiện tìm kiếm láng giềng gần nhất hoặc láng giềng gần nhất xấp xỉ trên các embedding này. Chúng chỉ là một mảng một chiều các số dấu phẩy động.
And the arrays always have to be fixed.
Và các mảng này luôn phải cố định.
It's always fixed length, meaning like the size of one embedding from one record to the next record is always going to be the same, because that's what the transformer generates.
Chúng luôn có độ dài cố định, nghĩa là kích thước của một embedding ở một record so với record tiếp theo luôn luôn bằng nhau, vì đó là thứ transformer tạo ra.
So the challenge in this is that, just like we talk about ranking, like how do I get a bunch of results and then rank them in order of importance?
Thách thức ở đây là, giống như khi ta nói về xếp hạng, làm sao lấy một loạt kết quả rồi xếp hạng chúng theo mức độ quan trọng?
In semantic search, it gets kind of really fuzzy, because there's no, Because the transformer is doing this magic to convert free-form text, or whatever it is we want to look up on, into this embedding, and somehow the embedding represents some higher-level meaning that we've extracted from the data we're trying to look up on or store.
Trong tìm kiếm ngữ nghĩa, chuyện này trở nên khá mơ hồ, vì không có, Vì transformer làm điều thần kỳ này để chuyển văn bản tự do, hay bất cứ thứ gì ta muốn tra cứu, thành embedding này, và bằng cách nào đó embedding biểu diễn một ý nghĩa ở mức cao hơn mà ta đã trích xuất từ dữ liệu cần tra cứu hoặc lưu trữ.
There's no guarantee that we're going to find exactly the results that we want. So you kind of just go by what feels good enough, what feels OK, right?
Không có gì đảm bảo rằng ta sẽ tìm đúng chính xác những kết quả mình muốn. Nên ta cứ dựa vào cảm giác thế nào là đủ tốt, thế nào là ổn, đúng không?
So there's a bunch of different data structures you can use.
Có rất nhiều cấu trúc dữ liệu khác nhau mà bạn có thể dùng.
Sorry, a bunch of different specialized database systems that you can use to do these things, like Pinecone, Weaviate, Milvus are probably the main ones.
Xin lỗi, rất nhiều hệ quản trị cơ sở dữ liệu chuyên biệt khác nhau mà bạn có thể dùng để làm những việc này, như Pinecone, Weaviate, Milvus có lẽ là các hệ chính.
But pretty much every relational data system that people are actively using today and actively maintain has their own vector index. Postgres has pgVector, Oracle, MySQL. Actually, MySQL, I don't know.
Nhưng hầu như mọi hệ quản trị cơ sở dữ liệu quan hệ đang được người ta tích cực sử dụng hiện nay và đang tích cực bảo trì đều có chỉ mục vectơ riêng. Postgres có pgVector, rồi Oracle, MySQL. Thật ra, MySQL thì tôi không biết.
Oracle, SQL Server, everyone has a vector index now.
Oracle, SQL Server, giờ ai cũng có chỉ mục vectơ.
And the two main data structures you're going to use are either going to be an inverted index, like we just talked about, or a graph index. I'll go through both of those.
Và hai cấu trúc dữ liệu chính mà các bạn sẽ dùng sẽ là một chỉ mục đảo ngược, như chúng ta vừa nói, hoặc một chỉ mục đồ thị. Tôi sẽ đi qua cả hai.
So an inverted index, the basic idea is that we're going to, we want to maintain a mapping from some location in this high-dimensional space to the records that match, have an embedding that's close to the one that we're trying to do a lookup on,
Vậy với chỉ mục đảo ngược, ý tưởng cơ bản là chúng ta sẽ, chúng ta muốn duy trì một ánh xạ từ một vị trí nào đó trong không gian nhiều chiều này đến các bản ghi khớp, tức có embedding gần với embedding mà chúng ta đang muốn tra cứu,
right? So the basic way it works is you just sort of scan through your data ahead of time.
đúng không? Cách hoạt động cơ bản là bạn quét qua dữ liệu của mình trước.
You're going to run your k-means clustering algorithm, where k's defined whatever, it's black magic how you assign it, but it's usually not quite large.
Bạn sẽ chạy thuật toán phân cụm k-means, trong đó k được định nghĩa tùy ý, cách chọn nó là cả một phép màu đen, nhưng thường thì không quá lớn.
And then you're going to then do lookups by just running the same clustering algorithm to jump into that high-dimensional space and figure out what are all the records that are close to you in the cluster, right?
Sau đó bạn sẽ tra cứu bằng cách chạy cùng thuật toán phân cụm đó để nhảy vào không gian nhiều chiều và xác định tất cả các bản ghi gần bạn trong cụm, đúng không?
So let's look at an example. So say we have all the embeddings we got from the lyrics. And so in the first pass, we want to compute k-means clustering.
Hãy xem một ví dụ. Giả sử chúng ta có tất cả embedding lấy từ lời bài hát. Ở lượt đầu tiên, ta muốn tính phân cụm k-means.
We want to figure out how to cluster these guys into a lower dimensional space that allows us to find things that are similar to each other.
Ta muốn tìm cách gom các điểm này thành cụm trong một không gian chiều thấp hơn để tìm được những thứ giống nhau.
So I'm just going to sequential scan through the data and place clusters on a high dimensional space here. I'm showing two dimensions, but in actuality, it would be much larger.
Tôi sẽ quét tuần tự qua dữ liệu và đặt các cụm lên không gian nhiều chiều ở đây. Tôi đang vẽ hai chiều, nhưng thực tế sẽ lớn hơn nhiều.
And I want to do this for all the other key embeddings I have in my data set. So then now, I'm going to run my clustering algorithm.
Và tôi muốn làm vậy cho tất cả các embedding khóa khác trong tập dữ liệu. Rồi bây giờ tôi sẽ chạy thuật toán phân cụm.
That's going to then generate a bunch of different regions. And then for each cluster, I'm going to compute the centroid.
Nó sẽ tạo ra một loạt vùng khác nhau. Sau đó với mỗi cụm, tôi sẽ tính tâm cụm.
Like, what's the central location that's closest to all of the points in my cluster?
Tức là vị trí trung tâm nào gần nhất với tất cả các điểm trong cụm của tôi?
And then now, once I have my centroids, I'm going to build a basic inverted index that's going to map these centroids to the records that exist in my cluster, right?
Và khi đã có các tâm cụm, tôi sẽ xây một chỉ mục đảo ngược cơ bản ánh xạ các tâm cụm này tới các bản ghi nằm trong cụm của tôi, đúng không?
Because now, what I'm going to be able to do is, for a new embedding key that shows up, I run it through.
Bởi vì bây giờ, khi có một khóa embedding mới xuất hiện, tôi sẽ có thể đưa nó qua mô hình.
Or sorry, for a new key I want to do a lookup on, or a term I want to look up on, I run it through my transformer.
À xin lỗi, với một khóa mới tôi muốn tra cứu, hoặc một từ tôi muốn tra cứu, tôi đưa nó qua transformer.
I end up with, again, this 6.1 dimensional array of embeddings. And then I run the k-means. I just compute where it exists in high dimensional space, what cluster it exists in.
Tôi lại nhận được mảng embedding 6.1 chiều này. Rồi tôi chạy k-means. Tôi chỉ cần tính xem nó nằm ở đâu trong không gian nhiều chiều, tức nằm trong cụm nào.
That's going to give me the centroid. And then the mapping, then, from the posting list is just going to be the records that are closest to this in the space.
Điều đó sẽ cho tôi tâm cụm. Và rồi ánh xạ từ posting list sẽ chính là các bản ghi gần nhất với nó trong không gian.
And somehow, through the embedding, I know these things are similar to each other semantically.
Và bằng cách nào đó, thông qua embedding, tôi biết những thứ này giống nhau về mặt ngữ nghĩa.
Pretty basic, right? Challenge, of course, is how do you maintain this? So if I insert a bunch of new keys, then the clustering may get out of whack.
Khá cơ bản đúng không? Tất nhiên, thách thức là làm sao duy trì cấu trúc này? Nếu tôi chèn một loạt khóa mới, việc phân cụm có thể bị lệch.
And therefore, my results may not be as accurate.
Và do đó, kết quả của tôi có thể không còn chính xác.
So you can either do this in a partition manner, like we did with Lucene, where you build that dictionary list once, make that immutable, and then build another one for new ones to come in, and occasionally combine them and recompute stuff.
Vậy bạn có thể làm theo kiểu phân vùng, như chúng ta đã làm với Lucene, tức là xây dựng danh sách từ điển đó một lần, để nó bất biến, rồi xây một cái khác cho các mục mới đến, và thỉnh thoảng gộp chúng lại rồi tính toán lại.
The basic idea is the same. The alternative approach is to do a graph search.
Ý tưởng cơ bản vẫn như nhau. Cách tiếp cận thay thế là tìm kiếm trên đồ thị.
And the idea here is that we're going to build now a graph of our embeddings, again, in high dimensional space.
Ý tưởng ở đây là bây giờ ta sẽ xây một đồ thị gồm các embedding của mình, một lần nữa, trong không gian nhiều chiều.
And then for each point in the high dimensional space, we're going to compute the utmost and nearest neighbors and maintain the edge between them.
Và với mỗi điểm trong không gian nhiều chiều, ta sẽ tính các láng giềng gần nhất của nó và duy trì cạnh nối giữa chúng.
And this edge is how we're going to traverse along between the different entries until we can narrow down and find the one that we think is the best natural port we're looking for.
Và cạnh này là thứ ta dùng để duyệt giữa các mục khác nhau cho đến khi thu hẹp được phạm vi và tìm ra mục mà ta cho là kết quả phù hợp nhất mà ta đang tìm.
So let's say that the embedding we want to find is this search vector here. Again, it's in my query. I run it through my transformer. I get an embedding.
Giả sử embedding ta muốn tìm là vectơ tìm kiếm này đây. Một lần nữa, nó nằm trong truy vấn của tôi. Tôi cho nó qua transformer và nhận được một embedding.
And then I plop it down in my high dimensional space like this. And so for this graph data structure, I always have to have an entry point. Like, where am I allowed to start?
Rồi tôi đặt nó xuống không gian nhiều chiều như thế này. Và với cấu trúc dữ liệu đồ thị này, tôi luôn phải có một điểm vào. Tức là tôi được phép bắt đầu từ đâu?
Because I have to maintain a pointer of something somewhere that says, how do I start doing traversal into this?
Vì tôi phải duy trì một con trỏ ở đâu đó cho biết làm thế nào để bắt đầu duyệt vào cấu trúc này?
So at this first location here, I'm going to look at all my neighbors that this node is connected to.
Vậy tại vị trí đầu tiên này, tôi sẽ xem tất cả các láng giềng mà nút này kết nối tới.
And for each of those, I'm just basically going to compute their distance according to some function of how close they are to my search vector.
Và với mỗi nút trong số đó, về cơ bản tôi chỉ tính khoảng cách của chúng theo một hàm nào đó để xem chúng gần vectơ tìm kiếm của tôi đến mức nào.
Because I know what my search vector is, so I know what the location I want to get to. But I'm trying to find all the ones that are close to it.
Vì tôi biết vectơ tìm kiếm của mình là gì, nên tôi biết vị trí mình muốn đến. Nhưng tôi đang cố tìm tất cả những nút gần nó.
So in this case here, it's this one at the top.
Trong trường hợp này, đó là nút ở phía trên.
So I'm going to follow that pointer and then do the same thing, look at all the other entries that I'm connected to, figure out who's closer, Jump along to this, and then I land to the one that I want.
Vậy tôi sẽ đi theo con trỏ đó rồi làm điều tương tự, xem tất cả các mục khác mà tôi được kết nối tới, xác định mục nào gần hơn, nhảy sang mục này, và rồi tôi đáp xuống mục mà tôi muốn.
Pretty cool. But again, think in extremes. If I have a trillion records, doing this graph traversal is going to be expensive.
Khá hay. Nhưng một lần nữa, hãy nghĩ đến các trường hợp cực đoan. Nếu tôi có một nghìn tỉ bản ghi, việc duyệt đồ thị này sẽ rất tốn kém.
So the optimization that people use is what's called HNSW, or hierarchical graphs, or hierarchical navigable small worlds, where you basically have multiple layers of graphs.
Vì vậy cách tối ưu mà người ta dùng được gọi là HNSW, hay đồ thị phân cấp, hay hierarchical navigable small worlds, trong đó về cơ bản bạn có nhiều tầng đồ thị.
And you start at the top, and you follow the traversals in a smaller subset of the graph at the top. And then when you exhaust your search at the top level, you go down.
Và bạn bắt đầu từ trên cùng, rồi duyệt trong một tập con nhỏ hơn của đồ thị ở tầng trên cùng. Và khi đã tìm hết ở tầng trên cùng, bạn đi xuống.
So there's pointers going down to the nodes below you. What does it smell like? I think you just said it. Skip list, exactly right. Same idea.
Có các con trỏ đi xuống những nút bên dưới. Nó gợi cho bạn nghĩ đến cái gì? Tôi nghĩ bạn vừa nói rồi. Skip list, đúng vậy. Cùng ý tưởng.
When I build these, I always have my graph at the bottom.
Khi xây dựng các cấu trúc này, tôi luôn đặt đồ thị của mình ở tầng dưới cùng.
When I add the layers at the top, I'll flip a coin to decide whether I want to keep a node there or not.
Khi thêm các tầng ở phía trên, tôi sẽ tung đồng xu để quyết định có giữ một nút ở đó hay không.
And then that way, as I progressively go to the top, the number of nodes is smaller, because then I can do that search more quickly and then narrow down to the result that I want.
Như vậy, càng lên các tầng cao hơn, số lượng nút càng ít đi, vì khi đó tôi có thể tìm kiếm nhanh hơn rồi thu hẹp dần về kết quả mình muốn.
A lot of stuff's not new, even though it's AI. They're borrowing ideas from skip lists from the 1990s. So again, this is the search vector I want. I start at the top level.
Có nhiều thứ không hề mới, dù nó là AI. Họ mượn ý tưởng từ skip list của những năm 1990. Vậy nên, đây là vectơ tìm kiếm mà tôi muốn. Tôi bắt đầu từ tầng trên cùng.
I enter my graph here. In this case here, I only have one neighbor. I know it's closer to my starting points.
Tôi đi vào đồ thị ở đây. Trong trường hợp này, tôi chỉ có một nút lân cận. Tôi biết nó gần điểm xuất phát của mình hơn.
I want to traverse down, come down now to the second level, do the same thing, look at all my neighbors, see that this one at the bottom is closer.
Tôi muốn đi xuống, giờ xuống tầng thứ hai, làm tương tự, xem xét tất cả các nút lân cận, thấy rằng nút ở dưới này gần hơn.
I go there and jump to this one, go there, jump down here, and then my search is done. Yes.
Tôi đến đó rồi nhảy sang nút này, đến đó, nhảy xuống đây, và thế là tìm kiếm xong. Vâng, mời bạn.
Question: how do you store a graph representation in a relational database system? You just have a table for nodes, and then you have a table as the digital matrix for edges.
Câu hỏi: làm sao lưu một biểu diễn đồ thị trong một hệ quản trị cơ sở dữ liệu quan hệ? Bạn chỉ cần có một bảng cho các nút, và một bảng làm ma trận số cho các cạnh.
So the question is, so he's sort of asking, would I store this as a table? You could. The vector index implementations do not.
Vậy câu hỏi là, bạn ấy đang hỏi liệu tôi có lưu cái này dưới dạng bảng không? Có thể. Nhưng các bản cài đặt chỉ mục vectơ thì không.
They would store this as a specialized graph data structure. You're stepping on a landmine here.
Chúng sẽ lưu nó dưới dạng một cấu trúc dữ liệu đồ thị chuyên biệt. Bạn vừa giẫm phải một quả mìn đấy.
So I'm of the opinion that graph databases are a bad idea, and the better way to store graphs is in a relational database system.
Tôi cho rằng cơ sở dữ liệu đồ thị là một ý tưởng tồi, và cách tốt hơn để lưu đồ thị là dùng hệ quản trị cơ sở dữ liệu quan hệ.
And there's a bunch of algorithms that we won't cover so much in this class, but there's optimized algorithms to do graph traversal very efficiently on relational data.
Có một loạt thuật toán mà lớp này sẽ không đề cập nhiều, nhưng có những thuật toán được tối ưu để duyệt đồ thị rất hiệu quả trên dữ liệu quan hệ.
Whereas relational data people, like the Neo4j people, they would say, "Oh, no, you want to store things as node and edges explicitly, and you just follow those pointers in your data structure when you do want to do graph traversals."
Trong khi những người làm cơ sở dữ liệu đồ thị, như người của Neo4j, sẽ nói: "Ồ không, bạn nên lưu rõ ràng dưới dạng nút và cạnh, rồi chỉ cần đi theo các con trỏ đó trong cấu trúc dữ liệu khi bạn muốn duyệt đồ thị."
In a modern relational data system that does a bunch of these enhanced query processing techniques, we'll talk a little about them in a few weeks, but you can rip through that GC matrix very quickly.
Trong một hệ quản trị dữ liệu quan hệ hiện đại có nhiều kỹ thuật xử lý truy vấn nâng cao, vài tuần nữa chúng ta sẽ nói đôi chút về chúng, bạn có thể quét qua ma trận đó rất nhanh.
Think of running through a column store.
Hãy hình dung việc quét qua một column store.
And there's other tricks you can do where, you know, if you're traversing a graph, you can do things more efficiently than you would if it was regular tuples.
Và còn những mẹo khác, chẳng hạn khi bạn duyệt một đồ thị, bạn có thể làm hiệu quả hơn so với khi dùng các tuple thông thường.
Then in SQL 2023, in the standard, they added now property graph queries.
Rồi trong chuẩn SQL 2023, họ đã bổ sung các truy vấn đồ thị thuộc tính.
So now in SQL, you can define graphs over existing tables, and you can do things that look like Cypher graph queries in SQL directly.
Giờ đây trong SQL, bạn có thể định nghĩa đồ thị trên các bảng sẵn có, và làm những việc trông giống truy vấn đồ thị Cypher ngay trong SQL.
Because one of the things that the graph data says will do better than a relational data system is, if I'm doing node traversal, there's got to be a logic to decide, okay, I'm at this node.
Bởi vì một trong những điều mà cơ sở dữ liệu đồ thị cho rằng chúng làm tốt hơn hệ quản trị dữ liệu quan hệ là, nếu tôi đang duyệt các nút, thì phải có một logic để quyết định: được rồi, tôi đang ở nút này.
Where do I go next?
Tiếp theo mình đi đâu?
And if you just do that in the application, now you're going back and forth between the application, the client, and a data server, and a bunch of network round trips, whereas the graph data guys have a single API traversing this graph, and everything runs on the server side.
Và nếu bạn chỉ làm việc đó trong ứng dụng, thì bạn sẽ phải qua lại giữa ứng dụng, tức máy khách, và máy chủ dữ liệu, với cả một loạt lượt đi về qua mạng, trong khi các hệ cơ sở dữ liệu đồ thị có một API duy nhất để duyệt đồ thị này, và mọi thứ chạy ở phía máy chủ.
When they added property graph queries to SQL, Now you can define that traversal logic in SQL, so there's no round trip, and everything's done on the server side.
Khi họ thêm truy vấn đồ thị thuộc tính (property graph) vào SQL, giờ bạn có thể định nghĩa logic duyệt đó ngay trong SQL, nên không có lượt đi về nào, và mọi thứ được thực hiện ở phía máy chủ.
The question is, what do you do to implement that? Only Oracle, at this point. There's an extension for DuckDB to add property graphs.
Câu hỏi là, bạn làm gì để cài đặt điều đó? Hiện giờ thì chỉ có Oracle. Có một phần mở rộng cho DuckDB để thêm đồ thị thuộc tính.
I don't think it made it to the mainline branch, but there's a paper I'm happy to share on Piazza from, like, two years ago. They mopped the floor.
Tôi không nghĩ nó đã được đưa vào nhánh chính, nhưng có một bài báo từ khoảng hai năm trước mà tôi sẵn lòng chia sẻ trên Piazza. Họ đã đánh bại hoàn toàn.
DuckDB crushes Neo4j and all these other systems by adding some of these additional... They don't even add all the enhancements. Just some of them, and it crushes Neo4j.
DuckDB nghiền nát Neo4j và tất cả các hệ thống khác này chỉ bằng cách thêm một vài cải tiến... Họ còn chưa thêm hết các cải tiến. Chỉ một số thôi, mà nó đã nghiền nát Neo4j.
Neo4j is not a good system. Sorry, let me rephrase that. Neo4j is a poorly written system, as if that's better. So yeah, use the graph databases... they'll get...
Neo4j không phải là một hệ thống tốt. Xin lỗi, để tôi nói lại. Neo4j là một hệ thống được viết tệ, như thể nói thế thì khá hơn. Nên là, cứ dùng các cơ sở dữ liệu đồ thị... chúng sẽ...
if a relational database system natively supports graphs, and some of the query processing techniques where you own graphs, they'll crush any graph database. Don't use a graph database. Yes?
nếu một hệ cơ sở dữ liệu quan hệ hỗ trợ đồ thị một cách gốc, cùng với một số kỹ thuật xử lý truy vấn dành riêng cho đồ thị, thì nó sẽ nghiền nát mọi cơ sở dữ liệu đồ thị. Đừng dùng cơ sở dữ liệu đồ thị. Bạn hỏi đi?
As a question, how is PgVector implementing their data structure? So PgVector is, the way they do it is an extension in Postgres that gives you vector search. They have both.
Em hỏi là PgVector cài đặt cấu trúc dữ liệu của họ như thế nào ạ? Vậy PgVector là, cách họ làm là một phần mở rộng trong Postgres cung cấp tìm kiếm vectơ. Họ có cả hai.
They started off with the inverted index, the IVF flat, and then they added HNSW, I think last year, right?
Họ bắt đầu với chỉ mục đảo ngược, IVF flat, rồi thêm HNSW, tôi nghĩ là năm ngoái, đúng không?
It was written by one dude, right? He's just doing it because he wanted to do it, and then the PgVector guy, and then it got a lot of traction.
Nó do một anh chàng viết, đúng không? Anh ấy làm vì anh ấy muốn làm, và rồi anh chàng PgVector đó, và sau đó nó nhận được rất nhiều sự quan tâm.
I think Amazon's thrown some time into it. Like, it's pretty good, and for, I don't know, 90% of the use cases, it's probably good enough for most people.
Tôi nghĩ Amazon cũng đã bỏ thời gian vào đó. Nó khá tốt, và với, tôi không biết, 90% các trường hợp sử dụng, có lẽ nó đủ tốt với hầu hết mọi người.
In the same way that, like, Elasticsearch and Vespa and these other specialized full-text search database systems, they will have more sophisticated algorithms and data structures to do inverted indexes than Postgres and other relational database systems.
Cũng giống như Elasticsearch và Vespa và các hệ cơ sở dữ liệu tìm kiếm toàn văn chuyên biệt khác, chúng sẽ có các thuật toán tinh vi hơn và cấu trúc dữ liệu cho chỉ mục đảo ngược tốt hơn Postgres và các hệ cơ sở dữ liệu quan hệ khác.
These specialized vector databases, like a Pinecone, like a Weaviate, and so forth, they're gonna have a bunch of enhancements that, like, PgVector is gonna have, But for most people, PgVector is probably good enough.
Các cơ sở dữ liệu vectơ chuyên biệt này, như Pinecone, như Weaviate, và vân vân, sẽ có một loạt cải tiến mà, PgVector sẽ có, Nhưng với hầu hết mọi người, PgVector có lẽ là đủ tốt.
Yes? Yes, the question is, like, what am I searching here? It's nearest neighbors.
Vâng? Vâng, câu hỏi là tôi đang tìm kiếm gì ở đây? Đó là các láng giềng gần nhất.
I want to find all the, depending on how many nodes I want to get back or how many entries I want to get back, I want to find which vertices are the closest to me.
Tôi muốn tìm tất cả các, tùy vào việc tôi muốn lấy về bao nhiêu nút hay bao nhiêu mục, tôi muốn tìm những đỉnh nào gần mình nhất.
All the points in the entire graph? No.
Tất cả các điểm trong toàn bộ đồ thị ư? Không.
Like, if my graph has a billion nodes and I want the top 10, I would, you know, if I do this, I can skip a bunch of the rest of the graph and jump, you know, get closer to the location, land in the bottom part here, and then kind of expand out until I find the 10, if I'm looking for 10, find the 10 nodes that match.
Ví dụ, nếu đồ thị của tôi có một tỉ nút và tôi muốn lấy top 10, thì tôi sẽ, bạn biết đấy, nếu làm thế này, tôi có thể bỏ qua phần lớn phần còn lại của đồ thị và nhảy, tiến gần hơn tới vị trí đó, đáp xuống phần dưới ở đây, rồi mở rộng ra xung quanh cho đến khi tìm đủ 10 nút, nếu tôi đang tìm 10, thì tìm 10 nút khớp.
Okay. All right, so I missed this last class, but I do want to talk about it because I think it's just kind of cool.
Được rồi. Được rồi, tôi đã bỏ lỡ phần này ở buổi học trước, nhưng tôi vẫn muốn nói về nó vì tôi nghĩ nó khá hay.
I'm gonna show you one last thing, extra stuff you can do with indexes.
Tôi sẽ cho các bạn xem một điều cuối cùng, những thứ bổ sung bạn có thể làm với chỉ mục.
So regardless of whether you're using a skip list, trie, whatever you want, there's actually some cool things you can add in SQL to make your indexes even better.
Dù bạn dùng skip list, trie hay bất cứ cấu trúc nào, thực ra có vài thứ hay ho bạn có thể thêm vào trong SQL để làm chỉ mục tốt hơn nữa.
So the first one is you can do what's called partial indexes.
Thứ đầu tiên là cái gọi là partial index (chỉ mục một phần).
So every single time when I've declared indexes before, I would call, you know, CREATE INDEX ON table whatever, and without a partial qualifier, it's gonna build the index on the entire, all the tuples in that table.
Mỗi lần trước đây khi tôi khai báo chỉ mục, tôi gọi, bạn biết đấy, CREATE INDEX ON một bảng nào đó, và nếu không có điều kiện một phần, nó sẽ xây dựng chỉ mục trên toàn bộ các tuple trong bảng đó.
But I can add a qualifier like this, like a WHERE clause in my CREATE INDEX statement, to then say only build the indexes on the tuples that match this.
Nhưng tôi có thể thêm một điều kiện như thế này, như một mệnh đề WHERE trong câu lệnh CREATE INDEX, để nói rằng chỉ xây dựng chỉ mục trên những tuple khớp với điều kiện này.
So what this allows me to do is, like, tricks like this, where if now I have a query like SELECT B FROM foo WHERE A equals 1, 2, 3, and C equals Wu-Tang, I can actually just take this first predicate here, look in the catalog and say, oh, this index I want qualifies this.
Điều này cho phép tôi làm những mẹo như thế này, giả sử bây giờ tôi có truy vấn SELECT B FROM foo WHERE A bằng 1, 2, 3, và C bằng Wu-Tang, tôi có thể chỉ lấy vị từ đầu tiên này, tra trong catalog và thấy, à, chỉ mục này đáp ứng điều kiện đó.
And therefore, now when I do my lookup on A, I don't need to actually even check the C values, because I know that if it's in this index, it has to match my WHERE clause.
Và do đó, khi tôi tra cứu trên A, tôi thậm chí không cần kiểm tra các giá trị C, vì tôi biết nếu nó nằm trong chỉ mục này thì chắc chắn khớp với mệnh đề WHERE của tôi.
So it's an extra check I don't have to do. I only have to do it once in the catalog to see whether the index matches for me.
Vậy là bớt được một bước kiểm tra. Tôi chỉ cần làm một lần trong catalog để xem chỉ mục có phù hợp hay không.
Furthermore, now my index is gonna be much smaller, take less space in memory, and be way more efficient because I'm throwing away a bunch of stuff that I don't need.
Hơn nữa, chỉ mục của tôi giờ sẽ nhỏ hơn nhiều, chiếm ít bộ nhớ hơn, và hiệu quả hơn hẳn vì tôi đã loại bỏ nhiều thứ không cần thiết.
So typically you see this in, people create separate indexes for events that occur like per month, per year. So every month you're gonna create a new index.
Thường thì bạn thấy điều này ở chỗ, người ta tạo các chỉ mục riêng cho các sự kiện xảy ra theo từng tháng, từng năm. Vậy mỗi tháng bạn sẽ tạo một chỉ mục mới.
So if I wanna look up all the events that happened, what are all the orders that occurred in the month of September?
Nên nếu tôi muốn tra cứu tất cả các sự kiện đã xảy ra, tức là tất cả các đơn hàng phát sinh trong tháng Chín thì sao?
I'll have my September 25 index, and that's a fast lookup to go get that. So that's cool. The other thing you can do is call it include columns.
Tôi sẽ có chỉ mục tháng 9 năm 25, và tra cứu để lấy chúng sẽ rất nhanh. Vậy là hay rồi. Thứ khác bạn có thể làm là include columns (cột bao gồm).
So again, when we talked about storing data in indexes, again, whether it's B+tree or whatever you want, like all the attributes, whatever's defined as the key, they're gonna be stored within all the nodes in the data structure.
Như vậy, khi chúng ta nói về việc lưu dữ liệu trong chỉ mục, dù là B+tree hay bất cứ cấu trúc nào bạn muốn, tất cả các thuộc tính, bất cứ thứ gì được định nghĩa là khóa, sẽ được lưu trong mọi nút của cấu trúc dữ liệu.
But I can add this INCLUDE qualifier where I say this is not what the key is based on.
Nhưng tôi có thể thêm điều kiện INCLUDE này để nói rằng đây không phải là thứ khóa dựa vào.
So in this case here, the key is still based on A and B, but in the leaf nodes, in the B+tree, I'll throw in C.
Vậy trong trường hợp này, khóa vẫn dựa trên A và B, nhưng ở các nút lá của B+tree, tôi sẽ thêm C vào.
So now if I have queries like this, the same as before, it selects B from foo, where A equals one, two, three, and C equals Wu-Tang.
Vậy bây giờ nếu tôi có các truy vấn như thế này, giống như trước, chọn B từ foo, trong đó A bằng một, hai, ba, và C bằng Wu-Tang.
The B and A part, I'm gonna get from the index. And then when I get to the leaf node, then I just check the C attribute.
Phần B và A thì tôi sẽ lấy từ chỉ mục. Rồi khi tới nút lá, tôi chỉ cần kiểm tra thuộc tính C.
And if it matches, then, actually in this case here, I'm done. I actually don't even need to look at the original tuple. Because it's called a covering index.
Và nếu khớp, thì thật ra trong trường hợp này là xong rồi. Thật ra tôi thậm chí không cần nhìn vào tuple gốc. Vì nó được gọi là covering index.
Everything I need for this query is in the index. I didn't have to go look at the original tuple.
Mọi thứ tôi cần cho truy vấn này đều nằm trong chỉ mục. Tôi không phải đi xem tuple gốc.
Or if it doesn't match on the Wu-Tang, then I don't follow the pointer anyway, right? So again, this is called a covering index, or sometimes called index-only scans.
Hoặc nếu không khớp với Wu-Tang, thì dù sao tôi cũng không đi theo con trỏ, đúng không? Vậy nên, đây gọi là covering index, hay đôi khi gọi là index-only scan.
This is a huge win if you're not storing an index-organized table with your table heaps.
Đây là một lợi thế rất lớn nếu bạn không lưu một index-organized table cùng với các table heap.
If you can pack a bunch of crap in the leaf nodes, you obviously don't wanna put the entire table, then all my queries touch indexes and I never go look at the original tables.
Nếu bạn có thể nhét một đống thứ vào các nút lá, dĩ nhiên bạn không muốn nhét cả bảng vào, thì mọi truy vấn của tôi chỉ chạm vào chỉ mục và không bao giờ phải xem các bảng gốc.
And that's much, much faster. All right, again, I just think it's kinda cool. I think you guys should be aware of it, that you can do this extra stuff.
Và như vậy nhanh hơn rất, rất nhiều. Tôi chỉ thấy nó khá hay. Tôi nghĩ các bạn nên biết rằng mình có thể làm thêm những thứ này.
And Postgres can do this and all the enterprise systems can do this.
Postgres làm được và tất cả các hệ thống doanh nghiệp đều làm được.
So when Postgres says they're the best open-source enterprise data system, it's because they have a bunch of these extra features that MySQL and others don't have.
Vậy khi Postgres nói họ là hệ cơ sở dữ liệu doanh nghiệp mã nguồn mở tốt nhất, đó là vì họ có hàng loạt tính năng bổ sung như thế mà MySQL và các hệ khác không có.
Okay, so as I said, we went through a lot. Again, this is a buffet of cool data structures or databases. We'll see filters again when we talk about joins.
Được rồi, như tôi đã nói, chúng ta đã đi qua rất nhiều nội dung. Đây giống như một bữa tiệc buffet các cấu trúc dữ liệu hay cơ sở dữ liệu thú vị. Chúng ta sẽ gặp lại các bộ lọc khi nói về phép nối.
B+trees are still gonna be the default choice for indexes. If you love inverted indexes, there's a whole course on this in LTI.
B+tree vẫn sẽ là lựa chọn mặc định cho các chỉ mục. Nếu bạn thích inverted index, có cả một khóa học về chủ đề này ở LTI.
And then there's a whole nother data structure we didn't talk about called R-trees or KD-trees, where you think of them as like low-dimensional vector indexes.
Và còn một cấu trúc dữ liệu khác nữa mà chúng ta chưa nói tới, gọi là R-tree hay KD-tree, bạn có thể xem chúng như các chỉ mục vectơ có số chiều thấp.
Like if I wanna, like, bounding boxes within like geospatial stuff, like find me all the, what's the bounding region of zip code 15217, I could represent this in one of these data structures.
Ví dụ nếu tôi muốn các hộp bao trong dữ liệu địa không gian, như tìm cho tôi tất cả, vùng bao của mã bưu chính 15217 là gì, tôi có thể biểu diễn điều này bằng một trong các cấu trúc dữ liệu đó.
There's a whole nother course on that from 15826. I don't know how often that's taught, but they cover those things.
Có cả một khóa học khác về chủ đề đó, là 15826. Tôi không biết bao lâu thì họ dạy một lần, nhưng họ có đề cập những thứ đó.
All right, so next class, We will break the assumption that we've had so far, is that all our data structures are single-threaded.
Được rồi, vậy buổi sau, chúng ta sẽ phá bỏ giả định mà từ đầu đến giờ ta vẫn dùng, đó là mọi cấu trúc dữ liệu của chúng ta đều đơn luồng.
We will make them multi-threaded and talk about how to make them thread-safe, okay? Project two or project one is due this Sunday. We should do that.
Chúng ta sẽ làm cho chúng đa luồng và nói về cách làm cho chúng an toàn luồng, được chứ? Project hai, à project một, hạn nộp là Chủ nhật này. Chúng ta nên làm xong.
And then office hours are on Saturday, okay? Hit it! Jesus, watch me blitz the clips. Time our toots and we chat. Jesus, watch me blitz the clips.
Và giờ làm việc là vào thứ Bảy, nhé? Bắt đầu thôi! Jesus, watch me blitz the clips. Time our toots and we chat. Jesus, watch me blitz the clips.
Time our toots and we chat.
Time our toots and we chat.
Jesus, watch me blitz the clips. Time our toots.
Jesus, watch me blitz the clips. Time our toots.
Get the portrait, motherfuckers dead. Maintain, remember, stand slow in the grave.
Get the portrait, motherfuckers dead. Giữ vững, ghi nhớ, đứng chậm rãi trong nấm mồ.
Đă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.