Abstract: Bayesian network (BN) is one of the most important theoretical models for uncertainty knowledge expression and reasoning. So far, many BN structure learning algorithms have been proposed. In this paper, a fast algorithm FI-B&B-MDL is developed, which considerably speeds up the original I-B&B-MDL algorithm. Unlike I-B&B-MDL, the new FI-B&B-MDL first uses only order-0 and a small number of order-1 independence tests to obtain an original structure graph so that the number of independence tests and database passes can be decreased, and then takes mutual information between nodes as the heuristic knowledge to lead MDL searches so that the cut-offs of B&B search trees can be increased, and consequently the search process is accelerated. Experimental results show that the new algorithm is effective and efficient in large scale databases, and it is faster than the original algorithm.