Abstract: Bayesian network structure learning based on model selection is an NP-hard problem. And none of the presented algorithms is perfectly successful in solving the problem of searching efficiency, especially for complex system learning. Presented in this paper is a new independent-MDL-based approach to learn Bayesian network structures. The proposed algorithm limits the searching space by using a set of lower order independence tests, thus executing the MDL-based searching algorithm B ＆ B-MDL to obtain the final graph. The precision analysis of algorithm is presented. And the problem of parameter design is also concerned. The result of the experiment shows that the new algorithm I-B ＆ B-MDL is more efficient in time consumption than B ＆ B-MDL algorithm.