Thank you for the detailed reply. I'll take a look into YAML, I wasn't aware of it until now. If we stick with XML, I was considering to set it up this way:

<Id1 typ="rel" nam="Zwe">
    <Id2 typ="ent" nam="cabab">
        <Id3 typ="typ">
            <Id4 typ="val" nam="Trel">
                <Id5 typ="ite"/>
                <Id6 typ="ite"/>
            </Id4>
        </Id3>
    </Id2>
</Id1>

One thing I forgot to mention is that when giving those 2 names for a search, we'll also receive a type and need to return the Element in the tree which has that type.

This way, if we're given names 'cabab' and 'Trel' for a lookup, and type 'typ' we can check an Index to find the Ids associated with these names and look for paths where both occur (with the help of an index), then retrieve the element in that path which has the desired type (in this case, Id3). Since max depth is 5 and only a single element of a certain type is located within each path, this shouldn't take too much.

I believe the databases would also keep indexes of their own, allowing for faster than sequential search, akin to hash tables, possibly.

Anyway, thanks for the help, I'll look into the alternatives you've outlined.