Hans Reiser writes: > Matthias Urlichs wrote: > > >Hi, > > > >Oleg Drokin: > > > > > >>>When I tried this, reiserfsck with -S scanned the whole disk, as expected. > >>>Reiserfsck without -S said it would scan roughly half of my disk. That led > >>> > >>> > >>Yes. It scans all the blocks that are marked as "used" in bitmap. > >> > >> > >> > >That's not what I meant when I proposed this new option. The method > >which I proposed would walk the existing tree, both "downwards" and > >"sideways", to find all reachable blocks with nodes, and then do the > >existing rebuild-tree algorithm on the result. > > > > > > > >>>me to conclude that whatever it does, it doesn't just use the blocks which > >>>are actually used for the tree at the moment. > >>> > >>> > >>How can it know? It must find all the lost blocks too. > >> > >> > >> > >... and how can it know that the bitmap represents reality? > > > >Blocks have three pointers which point to them (left neighbour, right > >neighbour, and parent). (That's my understanding of the way people > >usually lay out their B-trees, anyway; apologies if yours is radically > >different.) > > > Is this the way they do it on disk? We just have a link from parent to > child. Maintaining on disk links to siblings would hurt performance as > the links would require updating.
Actually, B-link trees (B-trees with sibling pointers) don't require any additional io for sibling pointers maintenance. Just draw a picture of what is going on during insertion of new node or node deletion and you will see. B-link disadvantages are extra space required in a node to store the sibling pointer and unfriendliness to the "wandered logging". > > > I'd like to assume that blocks don't easily get lost when > >there are so many ways to find them. Three pointers look safer than a > >single bit, anyway. > > > >This method would be a nice compromise between not fixing a problem, > >depending on suspect information, and/or reconnecting every file which > >I've deleted during the last year. > > > > > > > Nikita. > >
