
<HTML>

<HEAD>

<TITLE>Doubly indexed tree / changelogs</TITLE>

</HEAD>

<BODY>

<FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Hi Nikita, Nathan -<BR>

<BR>

After some pondering I have come to two conclusions.<BR>

<BR>

To encode filesets, we need a tree that makes two iterations fast:<BR>

<BR>

</SPAN></FONT><OL><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>list all filesets that contain a certain object

</SPAN></FONT><LI><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>list all objects in a certain fileset<BR>

</SPAN></FONT></OL><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><BR>

Is there a doubly indexed tree for this?<BR>

<BR>

Secondly, to make the changelogs useful and scalable for filesets we will need to be able to list all changelog entries associated with a certain inode efficiently.  I see two ways to do this – one is an auxiliary directory file mapping inodes to many changelog entries, the second is to embed forward and backward pointers in the changelog entries to build a linked list rooted at the inode (using an EA in the inode pointing to the first and last element of the list).  Both have some overheads.  What are your thoughts?<BR>

<BR>

Peter</SPAN></FONT>

</BODY>

</HTML>