To improve real-time performance of fiber distributed sensing based on Brillouin scattering, and at the same time, ensure high measurement accuracy, the topic about Brillouin frequency shift extraction with high accuracy and less computational burden is investigated. The computer programs about Brillouin frequency shift extraction algorithms are based on quadratic polynomial fit and typical Lorentz, Gaussian, pseudo-Voigt and Voigt models are written. Brillouin spectra in a single-mode fiber are measured by the BOTDR (Brillouin Optical Time Domain Reflectometry). The Brillouin frequency shift about these spectra is extracted by the above algorithms. The results reveal that the computational burden of the algorithm based on quadratic polynomial fit is much less than those of the typical algorithms. Its computation time is only 1.15%, 1.80%, 1.51% and 0.51% of those of the typical algorithms. However, its error is much larger than that of the typical algorithms which will obstruct its application. The above results are consistent with the results of the corresponding numerically generated Brillouin spectra. To improve the accuracy in the quadratic polynomial fit algorithm, the influences of frequency sweep span, number of frequency sweep, signal to noise ratio (SNR), linewidth and deviation of frequency sweep span on the error in the extracted Brillouin frequency shift. The results reveal that if the number of frequency sweep is fixed, the error initially decreases with increasing frequency scanning range. Once the minimum error is reached, it may do the very opposite. The optimal frequency scanning scope equals to linewidth. The error varies as a power of the number of frequency sweep. The error also reduces exponentially with SNR (dB). The error is proportional to linewidth. The error increases with increasing deviation of frequency sweep span. Therefore, the spectra used for Brillouin frequency shift extraction should be symmetric about Brillouin frequency shift. According to the above results, a modified Brillouin frequency shift extraction algorithms based on quadratic polynomial fit is proposed. The algorithm selects Brillouin spectra with one linewidth and symmetric about maximum Brillouin gain and used to extract Brillouin frequency shift. The proposed algorithm can considerably decrease computation time relative to the typical algorithm, and at the same time, the accuracy is similar to that of the typical algorithms. The proposed algorithm is validated by the measured spectra and numerically generated spectra. The proposed algorithm not only can significantly improve real-time performance of fiber distributed sensing based on Brillouin scattering.