In computable structure theory, one usually measures the complexity of a structure by identifying the structure with its atomic diagram. The structure is then computable if so is its atomic diagram. The notion naturally relativises to non-computable oracles. However, for structures without computable presentations, a finer way to measure the complexity is sometimes more natural and suitable. In this talk we discuss different approaches to measure the complexity of non-computable structures and explain several of our recent results.