The band structure of two-dimensional phononic crystals with complex lattices is analyzed using the plane-wave algorithm in this paper. Phononic crystals composed of two-dimensional arrays of periodic aluminium alloy cylinders in air are calculated. Band structures of two types of complex lattices, the honeycomb and the Kagome lattices, are presented. The band structures of complex lattices and simple lattices are compared. It is concluded that compared with simple lattices, the band-gap of complex lattices are located at lower frequency fields. When the filling fraction is between 0.091 and 0.6046, the complex lattices have larger band gaps and gain an advantage over simple lattices. In addition, the gap map is introduced to illustrate the influences of the filling fraction on the number, the width and the limit frequency of the band-gap.