2
$\begingroup$

I would be very grateful if someone can clarify a little bit about the Dancing tree data structure that the Reiser4 filesystem uses. It's a presentation topic that I picked, however, there seems to be little resource about it. The only things that I could found are:

I have understood the basic idea of Dancing Tree. As far as I know, it pretty much resembles B+ Tree. However, I can only guess how the insertion and deletion operations are carried out, as follows:

  • Insertion acts like insertion on B+ Tree (insert and possibly split)
  • Deletion operation deletes the entries but without combining if underflow (?) because we don't want to perform optimization every time we modify the tree.

And my third question is: How does the dancing tree actually perform the "squeeze" operation before writing to disk? (as described in the Reiser4's description)

I would really be thankful if someone can shed some light on this! I just hope to get some clarifications as this is pretty confusing to me right now.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.