Information and communication systems for vehicles aregetting significant like ETC (Electronic Toll Collection) andcar navigation systems. In the next generation navigationsystems, each vehicle can not only receive various types ofinformation like maps and traffic but also obtain traffic informationaround the vehicle by using the sensors and sendthem to a navigation center. It is critical to discuss howto store information collected by vehicles in databases andhow vehicles access the information in the database in thepresence of a huge number of vehicles on roads. In thispaper, we propose an enhanced dynamic R-tree (EDR-tree)scheme to store and retrieve traffic data collected by vehiclesin dynamic distributed database systems. In distributedtree-structured indexes like R-tree and B-tree, the root nodeand nodes at upper layers easily get performance bottleneckand points of failure since every query request is transferredfrom root to leaf node. In this paper, we propose a new treestructuredscheme named EDR-tree to store data. A road isrealized as a sequence of road units. A geographical spaceof roads is separated into area units where road units arestored. An area unit is stored in a leaf node and there isa tree-structured index on the leaf nodes like B+-tree andR-tree. Each vehicle first makes an access to a leaf node,not the root, which has information of a road unit where thevehicle is currently moving. Then, a query request is efficientlyand reliably delivered to a target node by using notonly parent-child links but also enhancing links, sibling andadjacent links. We evaluate the EDR-tree in terms of searchtime and insertion time.