A new index structure for network constrained moving objects, network-constrained moving objects dynamic trajectory R-Tree (or NDTR-Tree for short), is proposed in this paper. NDTR-Tree can index the whole trajectories of moving objects, including their historical, current, and near future positions. In order to compare the performance of the NDTR-Tree with other index structures for network constrained moving objects, such as MON-Tree and FNR-Tree, a series of experiments have been conducted, and the experimental results show that the NDTR-Tree outperforms the previously proposed network constrained moving objects index methods in dealing with dynamically maintained trajectories of moving objects.