The machining feedrate, especially for the tool path presented by the small line segments, is low and fluctuates frequently when the tool path is too short, and this phenomenon increases the machining time and reduces the machining quality. To resolve these problems, a feedrate planning algorithm for small line segments based on B-spline curve is proposed. Firstly, the tool path is smoothed by B-spline curve at the junction of adjacent small line segments to increase the machining velocity and improve the machining quality. Secondly, the tool path is divided into different velocity planning intervals according to the curvature, and the velocity planning intervals are merged into velocity planning units to reduce velocity fluctuation and improve the machining quality. Thirdly, a high-speed and smooth feedrate planning algorithm is proposed to further improve the machining efficiency. Through keeping the acceleration of the velocity profile non-zero at the corners of the tool path, the algorithm can efficiently reduce the machining time. The experiments demonstrate that the proposed algorithm is able to achieve high machining speed and generate fine surface quality.