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.

Improve this question
$\endgroup$

0

Reset to default

Your Answer

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