Monolayer adsorbed water on the beta-cristobalite (100) surface is studied via classical molecular dynamics simulations. The ordered two-dimensional (2D) tessellation ice structure (i.e., the four-membered and the eight-membered rings appear alternatively) is justified at low temperatures in the simulations. The stability of this possible new ice phase is further investigated by heating the system from 5 to 300 K. An order-disorder structural transition is observed between 100 and 200 K, featuring the melting process of the tessellation ice. This process is characterized by the water oxygen-oxygen radial distribution function, the coordination number, the distance vector between the center of mass of the oxygen and the hydrogen atoms in water, the mean square displacement of oxygen in water, and the vibrational density of state. The above techniques show consistency on that the order-disorder transition temperature of the 2D tessellation ice is far below 300 K. The 2D tessellation ice structure is also obtained via density functional calculations with different generalized gradient approximations. By comparing the calculated adsorption and the lateral energies between different methods, we find that the melting temperature of the specific 2D ice structure is strongly method dependent. Therefore, further experimental works are urged to justify this possible new ice phase and probe its stability.