Video 4-4: Bounded in-degree linked data structures

0:03 To make progress on making data structures persistent without much overhead, it turns out you need to make more assumptions about the data structure. You cannot do it in full generality as as as we know as far as we know. Um the assumptions are however rather mild and uh many data structures still satisfy this. We've actually seen various examples. Uh so recall we had this access operation access step update operation update step. Um on top of that now we have uh linked data structures only.

0:53 So in a way everything consists of some nodes that uh even here we're restricting it to be the same type of nodes for everything. You could take the union of all them if if you like. So everything consists of a a network of these nodes that may have pointer fields. So here this may point to some other node. Maybe this also points to some other node and could be chaotic ways of how they connect. Maybe some entries are null pointers, so they don't point anywhere. Uh there's no no other assumptions. Um so we have nodes of a single type. They can have pointers among them.

1:53 And they can also have these information fields. So they could be have maybe there's a a third field that stores a number each. Um then the only other thing that we can have is somehow we need an entry point into the data structure. I may have this this uh graph of of nodes sitting somewhere. And I may have special um access pointers which are sitting somewhere. It needn't be just a single one. It could be constant number and they may point to some entry levels into the data structure. Think of these as if it's a binary search tree, we somehow keep a pointer to the root to get started. Or if we have a doubly linked list, maybe we have a pointer to the first and the last element. Something like this.

3:05 Okay, that's all we have. And uh the targets of these axis pointers they're are in the paper called entry nodes. So I'm going to keep that name. Uh so these are these two in this case. But the only significance of these will be to have a name to talk about them. uh if if this is our setup, notice that now an access step is also well defined. What I can do, I can either um I can either read one field, an information field, or I can read a pointer field.

4:11 And so if you think about um how you can get started uh I guess one other option is To be able to read the field of some node, you need to have a pointer to that node. You need to know the node. And so uh in a way you maintain a set of nodes that you're currently uh aware of and initially what what is um the name for that was um accessed nodes. Fine. Okay.

5:12 So again, think about just this is the nodes that you have visited. Initially, it's empty. Initially, you're only allowed to use the access pointers to find new nodes. Then these are added to your access nodes. Once you have an access note, you can read its fields that might via pointer fields teach you about new objects. So you can follow a pointer and learn about more. So you can follow some paths through this graph. That's what it's what it's saying. That's what axises can look like.

6:00 and I have following pointers. You can add more. And I think we've had this on the slide before. an update step can also do essentially these uh something of these three things. I can allocate a new node. I can change an info field or I can change a pointer field. And if I change the pointer field to something well I need to know what I'm changing it to. So an update step um remember update steps are mixed with access steps.

6:45 What are the options for update steps? Let's write it down briefly. Uh I can have a new note that I'm allocating. I can write a field. It could be info and then it needs to be to an access node.

7:14 No, we don't care about space. Um, it's okay if you visit the entire graph and keep that all in your in your head. That's up to you. Good.

7:27 So far, this wasn't really restrictive. Essentially, all data structures we can come up with work like this, except that we don't allow arrays. That's that's all. Right. So far, everything goes except for arrays. Um that's how it is. But this is not strong enough for guaranteeing the existence of these persistent data structures in a in a strict sense of no no overhead. Um on top of that now we make an assumption about how many pointers can point to any node. So here the model is we have a link data structure as defined on the previous slide and we have a a certain number of pointer fields say D per node.

8:34 Remember all the nodes have the same type. And now the new thing is that every node is the target of only uh a fixed number say less or equal pinters in the data structure.

9:05 In other words, if you express the links between the nodes as a graph, it is the in degree that's at most P. The outderee of a vertex is already bounded because it's only allowed a fixed collection of of pointer fields. But in principle, it could be pointed to by an arbitrary number of other nodes. But we're saying, no, this is not okay. The data structures we care about all have this bounded number, a constant upper bound on the number of pointers that point to the element. And note that this is this is true for binary search trees and linked lists. For binary search trees, I actually have one. It's just the pointer from my parent that goes into me.

9:53 Yeah, I'm assuming we don't have parent pointers. And for a doubly linked list, I guess it's two from my predecessor and successor. And that's that's enough. Maybe if you're strict uh if you have these entry pointers on top, maybe it's up to four in a degenerate case. But you can try to avoid that. Maybe three is is maybe two is good enough because uh these outside elements don't have successors. Right? So I have these two but then my uh first and last are two extra. I guess two is fine, right? Okay. Um then in preparation let's fix some notation that maybe I should have uh have had on the slide earlier because we've been using it a bit. Uh the current version has nodes. Um and this for many data structures is linear in the number of elements they store but in principle we don't know that. Uh let's just say it's the number of nodes whatever it is.

11:15 B is the current is a version number for the current version. Uh then M is the number of updates so far. I guess here it's update operations specifically and that's the number of versions.

11:41 So you see from this you increment your version number after a higher level update operation not after every single write operation after every atomic right. Okay. Um I'm not going to use this much but uh let's write T for time for the um the running time of general operation query and update.

12:15 Um more more interesting is repeatedly I'll refer to these things. Uh X is some ephemeral note. So a note as if the data structure was not persistent and then you'll see we'll replace it by a persistent version which will be noted will be denoted by Xbar. Uh effectively XAR is the same as X with some extra fields for storing things. And um yeah, this only pops up later.

13:03 Uh we'll not have just a single persistent node for every ephemeral node, but uh potentially several.