Van Emde Boas (vEB) trees are sequential data structures optimized for extremely fast predecessor and successor queries. These queries are one of the most important incentives to use ordered sets or maps such as vEB trees. All operations in a vEB tree are doubly logarithmic in the universe size. Attempts to implement concurrent vEB trees have either simplified their structure in a way that eliminated their ability to perform fast predecessor and successor queries, or have otherwise compromised on the doubly logarithmic complexity. In this work, we leverage Hardware Transactional Memory (HTM) to implement vEB tree-based sets and maps in which operations are doubly logarithmic in the absence of contention. Our proposed concurrent vEB tree is the first to implement recursive summaries, the key algorithmic component of fast predecessor and successor operations. Through extensive experiments, we demonstrate that our algorithm outperforms state-of-the-art concurrent maps by an average of 5.4x, the C++ standard ordered map by 70% (1 thread), and even its unordered map by about 15% (1 thread). And, it does so while using two orders of magnitude less memory than traditional vEB trees.