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:
- Reiser4's description of Dancing Tree: http://web.archive.org/web/20071024001500/http://www.namesys.com/v4/v4.html#dancing_tree
- The lookup operation of Dancing Tree: http://www.cofault.com/2006/03/reiser4-1-internal-tree.html
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.