Video 7-3: Basic External Memory Data Structures

0:02 There's one more I want to show you which uh addresses this earlier result that B-trees get this log B speed up, but not a B speed up. And um that's maybe not not so satisfying, in a way. Can we do better in some way?

0:23 In the next section, we'll look at buffer trees, which is an alternative to B-trees, uh where you'll maybe feel cheated in a second, but it it's way faster. Now, I told you that's impossible because B-trees there's a lower bound that shows they they can't uh can't be improved. Uh let me point out the following difference between internal memory and external memory. In internal memory, um if you ignore constant factors and uh like uh we're not tuning specific algorithms now, I'm just uh looking at the theta complexity, then any comparison-based algorithm is essentially as good as inserting the elements into a binary search tree and peeling them out in sorted order. You could even do this stupidly. Of course, you could insert them into a search tree and then do an in-order traversal, so at least the second part is linear time. But in terms of the theta class, you could even just do rank one, rank two, rank select one, select go through the um the elements in the tree with the select operations from an ordered dictionary.

1:26 All of this is just a constant factor difference in internal memory. And of course, uh sorting in internal memory is the famous N log N uh comparisons or almost whatever you want to count. And all of this is not true in external memory. You've already seen this. You maybe just didn't um realize the connection or the the difference. Uh we've seen how we can do sorting with multi with this um multi or multi um merge sort multiway merge sort. And the complexity I wrote it in the little n etc. I unfolded it here to make the distinction clearer, but it's the same bound as before. n over b log m over b of n over b. That's the sorting complexity. Whereas B-trees, if I were to to emulate this, insert everything in a B-tree and then read it off, I need n times the insertion cost. And that's it. And so I lose in two ways. I can't divide by b.

2:26 And I also get the base of the log to be only this b instead of m over b. And um uh in terms of just um the speedups we looked at before for essentially scanning based data structures, the dividing by b seems to be the the stronger part. Uh in practice so how the parameters pan out in internal memory, it might be that the second part, losing not getting the right base for the log is the bigger problem. Because m can be very large, whereas b is relatively moderate. But this depends on the level in the memory hierarchy. If you're talking about the level between main memory and disk, then the blocks can be also very big, right? Um uh pages for uh hard disk drives are are easily 4 kilobytes or more, then b is also large. It depends on the level, but certainly there's a big gap. We have two things where we lose.

3:22 Can we do nothing about this? The answer is kind of yes, and the problem isn't even the operations themselves. It's merely the uh online nature of a data structure that we insist to get um for insertions, there's no return value, but I could in this B-tree at any point in time have decided before I keep inserting more things, I want to query a bit. And the B-tree has to arrange data in a way so that I can query in the same log B of N time. And that forces it to use um a more rigid structure that makes it impossible to sort faster. That's the point. It's it's more about the um the movement of data or or keeping elements conveniently in a in a layout in memory than I I the operations themselves that makes this more uh expensive.

4:45 The solution is called a buffer tree, and it's a bit of a weird data structure because it kind of only works in an offline mode. Um before before I say more about how it works, let's let's read what the result is what we can in the end support. If you give it an offline sequence of operations, and it needs to be many operations, you could essentially say I'm uh I'm starting from an initially empty tree, then the number of operations is a bound for the size of the tree, right? Um in the worst case, it's all insertions. But you can mix it with deletions and queries, that's fine. But you get the answers to all queries at the end of serving all the operations. That's why what I mean by offline.

5:39 Or well, this is a bit imprecise. Let me say it better. Uh what the offline thing means is you cannot use the result of the query to influence the next operations. The The entire sequence of operations, all your insertions, deletions, and queries have to be determined from the start. And uh if you insist on waiting for a query, you have to wait for the entire operation to finish, and then you can use the result of the queries. Uh so And of course, what I'm what I'm saying here is a statement about what this theorem says. The data structure supports this. You can say, "Now I want the result of the queries," but you have to pay the time for that. So, the guarantee is only if you do a certain number of operations, then in total the the operation cost for that is like the sorting IO bound. Uh so, you're on on the on the good side here.

6:49 Um not on the slow B-tree side. And you can brush this up if there is some of the operations are scans of ranges, then you can do that optimally, too. But this second part is is a relatively easy extension. It's not the main point. It's a weird data structure. How could you ever make use of that? Where do you really need this that the operations are completely known in advance? I mean, one option is you really want to sort the elements, then you just insert them all, and then after that get them all out. That's an offline sequence. Uh there's a few other um applications that are similar to this. Um they're a tiny bit less uh standard or widespread. There's some geometric problems, a bit like this persistent uh tree um uh point location problem we looked at it ago. Uh sometimes the um the data structure is only used in a sweep line algorithm over a given set of geometric objects. And then all the inserts and queries are actually known up front.

7:53 And there you can use buffer trees as is. How do we build these? How what are they um internally look like? Uh conceptually it's it's a a B+ tree, but with B chosen to be humongous. So, very very wide nodes. Um a fan out of M over B. Um which means the height is very small, but crucially also uh eponymous to the type the name of the data structure, each holds a large buffer. And so, we'll be maximally lazy with all the operations. We don't execute any operations when we when we get them. All operations are just inserted to the root buffer. And yeah, I'll deal with that at some point. No guarantee is made. But um eventually the buffer in the root overflows. Um Let me try to sketch this maybe a little bit.

8:59 This There's two ways how do you imagine this. We can't really have a block that's as big as these B uh these M over B keys. Um but you could you could imagine it being a tiny little B tree.

9:16 But then we treat this as one large unit. So, this is a a B tree of its own with the usual B, right? B is equal B. Uh but then we do this until we have here the pointers coming out of these. That's supposed to be uh beta of M, the little M. And then you have more copies of this below.

9:41 And these all go to some node and I recursively continues. So, internally these super nodes consist of of B-trees to do um searches, but they also have on the side this huge buffer for operations. And whenever someone asks you to do an operation, you're just going to add it to the buffer and do nothing for now. When the buffer is full, you load the entire buffer into internal memory. Note that this um um this buffer has size m, so this just fits in main memory. And then you sort all those uh operations by their key because the key determines which subtree they really need to go to. And it's a B+ tree, so everything data is only in the leaves, so there's nothing actually happening in terms of queries inside here. Um let me move this to the next page so that it's not as cramped.

11:01 Maybe let me say uh a a word about the structure. I said this verbally, but um So, we have these super nodes that are internally B-trees of pending operations that we at some point have to do. Or we delay it. Now, uh the standard case for an operation is do nothing.

11:35 Just append it to the buffer. At some point this will overflow. Then we load the entire buffer. And sort by the key of the operations. And at this point you may also um simplify some operations. For example, if there was an insertion and a deletion for the same key, they might just uh that they annihilate each other. Things like that. Or if there's several insertions or say uh insertions in in a dictionary where you overwrite the value, you may remove the old ones. That's why you keep the timestamp as well.

12:39 But basically you sort them by key to then push them down to your children. Once they are sorted by key, it's clear which child they go to because the children have a subrange of the keys.

12:57 And so all operations are eventually served at the leaves. So you push them down to the right child. Just delegate. And you because you sort these first, you can push this down again in scanning time. So you don't do uh one element at a time. You do this in blocks. And so feed this um And so, um what if you paid in terms of IOs for this flush step?

13:46 Flushing a buffer down costs loading the entire buffer. That's uh order little m IOs. Sorting, oh, internal memory for free. Zero. Cool. And distributing, I mean, splitting it by children is also free, but then you have to write it to the buffer of the children. But because we do that in scanning time, it's again big O of m little m. Okay? And this is where you see where the magic comes from, right? You're you're kind of uh giving yourself the liberty to do this in one bit big batch, and because you that can then load a whole uh a whole batch of operations, each individual one becomes cheaper. >> [snorts] >> Okay. And the rest is essentially following from the structure uh because the because it has this huge fan out is small.

15:01 I have a fan out of roughly m of these n nodes. So, in a way, you get down to your leaves um faster. Now, over the course of an operation, [snorts] it starts in the root buffer. It's eventually flushed down. And uh each time we overall get this cost, if you split this over the operations, then it's um one one IO cost each. Uh so I'm sorry, more 1/B IO cost each. This is little M, and we have capital M operations.

15:38 So, one flush deals with theta M operations. So, the cost is 1/B per operation for one flush. And we have to multiply it by the height because every operation eventually travels down to the children to the leaf, and there it is answered.

16:22 And that's essentially what we claimed. Um the dividing by B inside is is kind of inconsequential. Okay. Um but it's only halfway satisfactory because we can only do this offline sequences, right? But at least that's another way to sort, um and it has more of a quick sort style flavor if you think about it. And there's also a way to do proper quick sort in external memory, but that's for for a different lecture. Uh the real cool thing about buffer trees is that with a little bit of massaging the structure, you can turn them into a priority queue. And that's um of course much more applicable because priority queues, if you can do that with the essentially the same same IO complexity per operation, now you have an optimal priority queue. So, that you can do you can still sort, um but it's kind of the uninteresting use case. Uh, in optimal time. You can use this for graph data, graph algorithms like Dijkstra.

17:24 Or at least say, uh, almost almost the version of Dijkstra without decrease key. Um, what you can do is insert and delete min. Decrease key is a big pain and is a big open problem whether you can do this in better than just log base two of n. So, decrease key seems very hard in external memory to do very well. Uh, if you insert and delete min, um, support only these two, then you can do it in the optimal time. And this is now no strings attached in terms of offline sequence. This is a proper priority queue. And the reason why you can do here that why you can support the delete mins even if they come at random points where you couldn't do it for the general case, is because a minimum is very predictable. You can only ask for one thing. So, the way to do it is to buffer, say, uh, m half smallest elements.

18:32 When you do an insert, you check if your largest of these minimal elements is uh, is larger than the new element goes in here and you evict the largest here into the data structure as an insertion. Okay? Whereas if the new inserted element is larger than this, you just insert it in the data structure with the same buffer trick as before.

19:06 And then, uh, delete mins will eventually delete from the beginning, the smallest. These are always in cash, so they pay nothing for the lead men. Eventually, you've exhausted your cash minima minima. If you're lucky, they get reinserted, uh but in general, they'll be depleted at some point. And then you get the next M elements via an expensive flush of the buffers. But by that time, you've served M delete mins for free. So, this all amortizes to I guess delete min even in constant time.

19:39 Uh you have to flush not just one level, you have to flush all the way down. So, I take that back, delete min is is the time stated. Um but that's also what we claimed. So, you can you can do kind of Dijkstra, just not the version with decrease key, but you can do the version where you reinsert a vertex with the better time. And when you've when you extract a vertex that you've visited before, you just don't visit it again. It's a bit less space-efficient, uh but it works, and that is um still This is kind of the the de facto implementation with further tweaks in practice.