Scalability is one of the crucial problems in realizing massively distributed systems such as ubiquitous computing. In this paper, we focus on indexing methods in massively distributed environments. A number of work on indexing in P2P, like CAN and Chord, have been devoted to overcome this problem. The lengths of routing path are
for CAN and
) for Chord, which are in fact the cost of search, where there are
nodes. In this paper, we propose an alternative indexing scheme not only relying on P2P but also on broadcasting environments. The contributions of this paper include firstly the reduction of routing path to nearly
(1) for road-oriented query by using broadcasting, and secondly handling the mobility of nodes on road networks.