Microscopic traffic simulation reflects the characteristics of the entire traffic flow by simulating individual vehicles in the transport network. Therefore, in the microscopic simulation, before a vehicle make behavioural changes, it needs to get the information from surroundings (especially information from its adjacent vehicles) in time. In a large-scale traffic simulation system, the query of adjacent vehicles will be very frequent .This directly affects the efficiency of the whole simulation system. To this end, we propose a position thread AVL (PTAVL) tree data structure to store vehicles on a lane. On this basis, we propose an adjacent vehicles query algorithm based on the PTAVL tree and compare it with the existing query algorithms. The query algorithm based on PTAVL has complexity of O(1) when a vehicle queries its former and follows adjacent vehicles on the same lane. It has complexity of O n (log ) when a vehicle queries its adjacent vehicles on the adjacent lane. Our primary experimental results show that the algorithm can improve the speed of query adjacent vehicles and the simulation speed of the microscopic traffic simulation system.