The sparsity and the severe attenuation of millimeter-wave (mmWave) channel imply that highly directional communication is needed. The narrow beam produced by large array requires accurate alignment, which is difficult to achieve when serving fast-moving users. In this paper, we focus on accurate two-dimensional (2D) beam and channel tracking problem aiming at minimizing exploration overhead and tracking error. Using a typical frame structure with periodic exploration and communication, a proven minimum overhead of exploration is provided first. Then tracking algorithms are designed for three types of channels with different dynamic properties. It is proved that the algorithms for quasi-static channels and channels in Dynamic Case I are optimal in approaching the minimum Cramer-Rao lower bound (CRLB). The computational complexity of our algorithms is analyzed showing their efficiency, and simulation results verify their advantages in both tracking error and tracking speed.