In order to improve the real-time performance of Brillouin optical-time domain analyzer (BOTDA), a method based on compressed sensing was proposed in this paper. It contained sparse representation, random sampling and signal reconstruction. Firstly, the sparse representation of Brillouin gain spectrum (BGS) was obtained by K-means singular value decomposition algorithm, and then BGS could be reconstructed with Gaussian random matrix and orthogonal matching tracking algorithm. To verify the performance of the proposed method, BGS at different SNR were generated and a 45km BOTDA was built for temperature experiments. Simulation and experiments show that the proposed algorithm improves the signal-to-noise ratio by 6.37dB at a cumulative average of 100 times, which is better than 10.13dB at a cumulative average of 3000 times, and the corresponding measurement time is reduced by 1/30. Besides, using 8MHz step data to reconstruct the Brillouin gain spectrum, the correlation coefficient of the reconstruction result of this method with the 4MHz step data is 0.9992, which makes the sweep time decrease by 1/2. The compressed sensing method not only ensures the measurement accuracy but also improves the real-time performance of BOTDA.