In memory storage of json / xml / vdom / sexp trees

Json, Xml, Virtul Dom, Symbolic Exprs have the following in similar:

  1. they tend to be "tree-like" in structure

  2. there is some enum where we can express it as

enum Foo {
  .. 'non-recursive' arms ...
  .. 'recursive' arms involving Box/Rc/Vec

How are these structures stored in Rust ? The Box/Rc approach seems to involve lots of small allocations on the heap (possibly one per node).

It seems like there aught to be a way to exploit the fact we are storing lots of Foo's.

It is not clear how to solve this problem with Typed-Arena (when we don't 'deallocate everything in phase').

Are there standard ways / toolkits for solving this problem, or does the Box/Rc hit to global allocator just not mater in practice ?

Often documents of these types are append-only, and then it makes sense to store the document in a single allocation using a Vec or a typed Arena. With a Vec, the references to children are indexes. With a typed Arena, they are references.

If you really need to insert and delete nodes of the document, then you have to either Box as you've said, or reuse the space for deleted nodes using something like a slotmap.