Video 7-2: Basic External Memory Data Structures

0:04 Let's instead of sorting and other classic external memory algorithms come back to data structures, uh our main focus, and see what what can be done in external memory or uh how we can um kind of profit from this. Um if you just take the raw numbers, the IO cost should usually be smaller than the internal memory cost. Now, of course, the units are um are different.

0:43 But, in a way, uh if you count all instructions on a word RAM, then you also count accesses to main memory. And so, the number of IOs should never be worse than that. Every memory access here also um is counted. But, if the hope is, of course, that this is lower because you have the uh one IO loads B elements at a time.

1:10 So, the the big question is whether this is something like a cell probe bound divided B. Uh this is potentially possible if you're if everything works out perfectly. Uh cell probe only bounds individual accesses to memory. And now I get B at the cost of one if everything aligns perfectly. So, uh that would be the best case. That would be the worst case. There's a in particular this factor B in between those two at the least. And the question for these data structures is where can we save this this factor B? Uh I guess with a question mark, this is always true.

1:53 Uh this is very very small. Um the question mark is where can we get the number of IOs to be less than the RAM instructions divided B?

2:25 Uh, as the kind of um, first first order question, right? Can we somehow profit from this locality and this this more powerful uh, primitive of loading data? And you've seen examples, um, I'm just uh, assuming that you've seen B-trees in some form or another. Uh, whether or not you know the exact rules of how to rebalance them, I it's not so important for this part. Um, interestingly, also historically, the B-tree is from early '70s, uh, with German uh, involvement, um, B for Bayer, and uh, long predates the theoretical model of external memory. So, clearly people were thinking about locality of memory access as well before this was uh, of critical importance. The the difference between random access to main memory and this block level access, um, specifically for hard disks, that difference has only grown. Um, so it became more relevant, not less. Uh, but indeed, uh, the idea here is is much older. And what's a B-tree compared to a binary search tree?

3:28 Uh, the whole the whole goal is to have bigger nodes, so that when you load one node, you touch a larger part from disk, but you also make a progress by using it's not uh, busy work that you're just loading more data to keep the the hard drive busy, but uh, you're making more progress in your search in the search tree with one node.

4:02 Now, do uh B-trees get a factor B speed up compared to binary search trees if you count I/Os versus internal memory uh cost? What's the search cost in a B-tree? Remember?

4:30 The answer is no, because the search cost in a B-tree is only log B of n. It's not log n divided B. So, if you want, you can of course write this as log n divided log B.

4:44 So, in a way, we get an exponentially worse speed up, if you like, right? Instead of dividing by B, we can only divide by log B.

4:55 Uh that's what B-trees get, but maybe because they're such an old idea, maybe this is just uh people's limits of creativity, you know? So, um uh a B-tree, again, um is is like a search tree, but you make the fan out be theta of B. Um I'm always putting here the defensive theta, because, you know, in reality, it's a range. It's between, say, half B and B, or depending on your parameters. I guess for for a B-tree, you want the actual fan out to be between a quarter of B and half B, because you need to store the keys and the pointers to the children. Uh should be fine. Then, you can store twice as many things, the keys and the pointers, assuming that these all have the same size.

5:58 Um it's probably also prudent to put the one here. Uh this log B if if N is tiny, then this log could be negative, and of course the cost is never negative. You have this plus one as a kind of uh base case for very small inputs. But the interesting case is of course when N is is fairly large, and then the dominant part is clearly this logarithmic term. Uh another cute thing that B-trees have exploited from very early on is if you don't just touch a single element, but you want a range of elements. Give me all the people with income between X and Y. Then uh suppose you have a B-tree index, you can find X, you can find Y, and then you have a a linked list that connects the uh values between those uh two extremes, or I mean connects all values in sorted order. So you have your your B-tree, and below it the leaves are also blocks, but they're kind of linked. I'm drawing this as if it was an array, but it's really more like a doubly linked list.

7:06 So if you find your way through the search tree to some starting point, some starting block, then from there on you can you can read sequentially as many elements as you want, and you don't pay the logarithmic slow down for these. Instead, the total cost is this. Um for scanning K elements, you only take pay K divided B roughly IOs, right? Because these are nicely aligned with blocks. Uh plus the first search. That's B-trees. Um brilliant. Now, uh as I said, this is not the same as a factor B speed up. Uh nevertheless, this is the best you can hope for. It turns out B-trees, despite being so old, they are precisely on the on the optimal threshold. If you want queries to be fast, there's nothing really you can do. Um again, we won't really prove this. Um the lower bound that's behind this optimality claim here is is also similar to um the sorting bound that we skipped. It's an information theory argument, it's relatively easy to see.

8:16 Uh if you load B elements and you're searching for one element, you do something like binary search. But now, you will learn B elements at a time. Now, how much does that help you to narrow down your search? In the best case, you're cutting a range of N elements into a range of N divided B. How often do you have to divide N by B before you reach a single element? Well, log base B of N. >> [snorts] >> Probably this argument is also uh was in the folklore well before um it was formalized in the external memory model setting.

9:03 Now, at least the B-trees can do updates at the same cost, that's good. But uh we started this journey saying ah, maybe uh there's a factor B speed up for some things. And we've seen an a boring example, scanning N elements, I can get the factor B speed up. So, sometimes it's possible. Uh but it looks like for B-trees, it's not. So, um is this like uh the typical case? Let's look at some simpler data structures as a warm up. Um how about uh linked list or a linear list-based uh data structures? The simplest might be a queue. So, you have your queue and conceptually it's this this one long thing. You can insert at the end. You can pop things out at the other end. Now, if you want to do this in external memory, what would you do? Well, clearly we want to keep these elements in in blocks. Now, there may be a half empty block here.

9:59 And there may be a partially empty block at this side. I'm going to make sure that I keep these two in internal memory. That way, when I insert into the queue, most of the time I can just occupy the next spot and I'm done. And I do this in cash. It costs zero, right?

10:23 Uh in the external memory model. Um and same for for DQ, I have this red block in here. Most of the time I just delete one more element, costs zero. Now, once in a while I have to bite the bullet and uh if that block is is full or that block is empty, I'm going to go to the next block. Um for now, for NQ, I'm going to allocate a new block and put it at the end of the queue. And here I going to load the next one.

10:56 So, it's already on the slide. Um we only pay one IO for every B NQ respectively DQ operations. So, they nicely amortize and you could say in an amortized sense, each operation costs less than one.

11:10 But, that's just coming from paying sometimes zero, most of the times zero, and sometimes one. That's of course much better and it is a factor B speed up, at least amortized. And clearly you can't do better than this if if a single operation is constant time, the best you can do is is pay one. And amortized just means sometimes zero. You can't do that worst case, of course. So, this is very good. How about um a stack? Almost the same trick works. Now, you could do a stupid thing, which would be you just keep the topmost block of the stack. And then it could happen that you um empty that one. Ah, I need to load the next one. Then I have I fill it. I needed to allocate a new block. So, if you keep just a single block, you might be trapped between just the boundary of that block and allocated deallocating that block all the time.

12:08 But, of course, you don't have to be that stupid. Just take two blocks. Uh and then again, you can guarantee you're always roughly B operations before you hit the block, before you fill it up, or before you empty the second block. So, same game. You need at least B operations before another block IO is needed. And so, same same result for stacks. You just need to uh be a tiny bit more careful, maybe. Um but not that much.

12:43 Um how about the uh general linked lists? If we can do queues and stacks, shouldn't we be able to do general linked lists where you can insert anywhere and delete anywhere? >> [snorts] >> Now, this becomes a little more tricky. Um if I insert in the middle of some block that's not in memory, I clearly have to pay the IO to load that block. That's inevitable um even for reading. So, uh all of what we could potentially save hinges on somehow being lucky or or doing several operations in a row in some position uh so that the block is already in cache. But, that's not so uncommon, right? Um So, we could uh at least, if the block's already in memory, scan the list in 1/B IOs amortized. But, how about uh insertions and deletions? When I try to insert and the block is full, I don't really know what to do. Uh I can't insert.

13:40 So, I somehow need to do something. I can't simply append the elements elsewhere. It's supposed to be a linked list that keeps the order. Um and uh if I were to simply um so, the the simple solution might be here's my linked list of blocks.

14:05 And I want to insert into this block, but it's entirely full. Now, of course, I could say, "Fine, that's easy. It's a linked list of blocks. I'm just going to add this one in between and put the new element here. Now, of course, these also need to point back. And these are gone. That works. However, I might, if I do this across the list many times and do a malicious insertions and deletions, I might end up with essentially all blocks being almost empty.

14:40 That's a bit of wasted space. Should we care? Uh we care because we can no longer scan the elements efficiently. So, sometimes you can maybe tolerate this. But, in general, you don't want the blocks to be almost empty because then you load one block per access and all this amortization is out of the window. So, we don't want the element there. Um what can we do instead? Well, we can try to balance things out a bit locally. We don't have to leave elements precisely in the block where they landed, or maybe turn that on its head. Um we have to live with the fact that elements now get relocated. So, we can pick uh an invariant similar to doubling arrays or these things. Say, we insist that every block has at least a quarter filled. Then we when we insert into a full block, uh we can we can split the elements in the middle into two blocks that are now half full.

15:43 But those satisfy the invariant. So instead of inserting a new empty block, we just take half of the elements with it. And if that block was full, I always have enough.

15:52 Um and uh so each of them has enough slack so that this amortizes. I'm moving a lot of elements. In internal memory, this would cost something. It's actually for free in terms of IOs if you think about it. At least up to this point. But I'm I'm touching this block anyways, and then I'm touching the new block. And how many elements I move between them in terms of IOs is is irrelevant. Uh if we do this, we similarly have to handle deletions, um but you can do a similar trick. So if an element is deleted from a block that's at the boundary of how full it has to be, um then we somehow uh borrow elements from the successor, say. So if there's some element here, less than quarter full, I guess the worst case is that the next element is also just at the threshold. But then these two together aren't very full, so I can turn them into a single block and forget one.

16:53 And then I'm again as safety distance away from being too full or too empty. So this all works. Um and so you can get what's known as a blocked linked list. Pick which title you want. Um it keeps all the n elements in n over b blocks, theta n over b blocks. You can insert and delete at any point in the list that you'd like. And if you already have access to the block, then even um the restructuring can be amortized because you're only going to do this fuse or split once every roughly B operations. So, each operation can contribute a 1/B contribution to the later restructuring. And so, um you could in principle have 1/B amortized cost. Of course, that's assuming that you already have the block that you're that you're inserting into in in cache. If you don't have that, then you need to load it. There's no way around it. In a way, other other than that, it's a perfect linked list in external memory.

18:04 Uh with one tiny caveat. What do we usually want linked lists for? I mean, they're always slower than arrays, and they're kind of less flexible than a binary search tree. Why would we even use a linked list ever? Uh the one thing that I think is often um useful is this notion of referential integrity in internal memory. So, um in internal memory, I can I can maintain a linked list so that when I insert an element, it's assigned a node object, and that node object is never ever changed. It's never moved. All that happens is bending pointers around. But I can keep an external pointer to that node, and that's going to stay valid um as long as the entire Well, the time that the data structure lives.

18:54 In external memory, this seems a fundamental issue because there's no way for me to keep the elements in the blocks without them running too too empty. Uh but as soon as I start moving elements, the old pointers don't go to the right place anymore. Uh and so, um there's no complete solution for this. And annoyingly, there's also no lower bound that I'm aware of. And this is something that has bitten us in our research as well. Um you can talk to Finn Mortman about this. Um there's partial solutions. One The one thing you can do is a back pointer. Every pointer to an element Say this is one block in your linked list. Here's your element that you cared about. And there's someone else from the outside that has a pointer to X. Now, if I store also a pointer from this element back to the location that contains the pointer, then whenever someone in the data structure moves X, I can go there and say, "Ah, I'm now at this new position."

19:58 So, if I'm ever going to move X somewhere else, to the new position. And of course, I take my my red pointer with me. That's a back pointer. Conceptually, a simple idea. Of course, you can um use this in many ways. Uh so, I can always notify my external pointer that I've been moved, and then it's still valid. What's the problem with that? Um if upon some restructuring of the list, I'm not just moving a single element, I'm moving B elements. All right? Remember how we How we did this here, right? We move half of the block's elements around. And so, that means I have to update all their pointers. And each of these pointers that I update may may reside somewhere else in memory, right? I have no control where these are stored. These are external to the data structure. So, for each pointer update, I might pay one IO. So, sadly, um we can get operations to be constant IOs amortized at least by the same amortization argument, but there seems no way to get to 1/B uh amortized IO cost because now the restructuring actually costs B IOs, not as not constant.

21:28 Uh there's even a problem with this if you have many pointers to the same object from various places. What do you do then? Um however, there's a This is easy to solve with the famous um one more level of indirection solves all computer science problems. Um if you have this element X again and there's a gazillion pointers to X, they all want to point to X. Well, we'll insert an intermediary, a handle. These all point to the handle. The handle is some object that never moves. The handle forwards to X and X has a back pointer to its handle, so it can notify the handle where it now lives if it's moved. And now I've just duplicated the access cost for following the pointer. Okay, that's not exactly great. At least you can do it. But of course it has the very same problem as this. Now, the handles I could try to cleverly manage in my data structure so that maybe they are also local.

22:30 Now it depends on how much your data structure changes over time. In principle, in the worst case, again, you'll have the same that all these handles for the elements that I rearrange might live on different blocks, so I pay B IOs for a restructuring operation, hence uh I get again this this constant amortized operations for a list. All of this sucks a bit and it seems that's where we are. Uh um I'm rather frustrated that we know neither an improvement of this scheme get a better guarantee for the restructuring cost nor some lower bound that tells you clearly this is impossible. Then we'd also know what's what's happening. That's where we are. That seems to be the state of the art in this case.