Is there a data-structure for semilattices similar to a tree data-structure?
This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg.
Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

The first two data structures discussed are the adjacency list representation of the transitive reduction graph (=Hasse diagram/cover relation) and transitive closure graph (=poset relation). A remark about the advantages of using a topological sort to label the nodes precedes that discussion. Note that the labels of topological sort would be good enough as "a distance measure to the root", which was one part of the data-structure for a tree in the question.

The other discussed representations are "Skeletal Representation", "Matrix Representation" and "Dimension Based Representation". The "Skeletal Representation" is interesting and useful, but based on a (=any) chain decomposition of the poset. The "Matrix Representation" might seem trivial, but its probably be the best representation for most practical problems. The "Dimension Based Representation" represents the poset as the subset of the Cartesian product of linear orders, but computing the minimal representation of this kind is NP-hard.

In conclusion, the most treelike representation of these is the adjacency list representation of the transitive reduction together with a labeling of the nodes by a topological sort (instead of "a distance measure to the root"). This is actually one of the representations used by Sage (the other is the "Matrix Representation").