It has been widely recognised that matchmaking is an important component of heterogeneous multiagent systems. Several researchers have developed powerful techniques for the matchmaking problem in general. There are also specific representation of agent capabilities such as DAML-S which provide a more specific framework for matchmaking. Most approaches to matchmaking have assumed a sequential search for an agent with matching capabilities. This may become intractable when the number of available agents gets large. In this paper, we consider how matchmaking can be developed into agent directories that can be searched and maintained efficiently. Our main contribution is to show how matchmaking with DAML-S specifications can be integrated with efficient methods for searching and maintaining balanced directory trees. We also report on experimental results using an implementation based on generalised search trees.