If it's worth saying, but not worth its own post, then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should start on Monday, and end on Sunday.
4. Unflag the two options "Notify me of new top level comments on this article" and "
Good analysis, thanks. I buy the first two points. I'd be shocked to see an implementation that actually makes use of the lower metadata requirements. Are there languages that provide a boolean primitive that uses a single bit of memory instead of a full byte? Also I don't understand what you mean by persistence.
Suppose you're making tree structures in a pure functional language, where there is no mutable state. Then what you need is functions that e.g. take a tree and a new element and return a new tree, sharing as much of its structure as possible with the old for efficiency's sake, that has the new element in it. These are sometimes called persistent data structures because the old versions stick around (or at least might; they might get garbage-collected once the runtime can prove nothing will ever use them).